#ifndef _STACK_H_
#define _STACK_H_
#define EmptyTos -1
#define MinStacksize 5

typedef int elementType;
//结构体定义
typedef struct stackRecord
{
	int capacity;
	int stackTop;
	elementType *array;
}STACK;

int isEmpty(STACK *s);  //判空
int isFull(STACK *s);   //判满
STACK *createStack(int maxElements);    //栈的创建
void disposeStack(STACK *s);        //栈的释放
void makeEmpty(STACK *s);       //创建空栈
void push(elementType element, STACK *s);//入栈
elementType top(STACK *s);      //返回栈顶元素
void pop(STACK *s);         //出栈
elementType topAndTop(STACK *s);    //出栈并返回栈顶元素

#endif

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"

//判断为空
int isEmpty(STACK *s){
	return (s->stackTop == EmptyTos);
}
//判断为满
int isFull(STACK *s){
	return (s->stackTop == s->capacity - 1);
}
//控制为空
void makeEmpty(STACK *s){
	if(s!=NULL){
		s->stackTop = EmptyTos;
	}
}
//创建栈
STACK *createStack(int maxElements){
	STACK *s;
	if(maxElements < MinStacksize){
		printf("栈的空间太小了\n");
		return NULL;
	}
	s = (STACK *)malloc(sizeof(struct stackRecord));
	s->array = (elementType *)malloc(sizeof(elementType)*maxElements);
	s->capacity = maxElements;
	makeEmpty(s);
	return s;
}

void disposeStack(STACK *s){
	if(s!=NULL){
		free(s->array);
		free(s);
	}
}
//进栈
void push(elementType element,STACK *s){
	if(!isFull(s)){
		s->stackTop++;
		s->array[s->stackTop] = element;	
	}else{
		printf("栈满了\n");
	}
}	
//读取栈顶数据
elementType top(STACK *s){
	if(!isEmpty(s)){
		return s->array[s->stackTop];
	}else{
		printf("top栈空\n");
		return 0;
	}
}
//出栈
void pop(STACK *s){
	if(!isEmpty(s)){
		s->stackTop--;
	}else{
		printf("pop栈空\n");
	}
}
//读取栈顶数据并出栈
elementType topAndTop(STACK *s){
	if(!isEmpty(s)){
		return s->array[s->stackTop--];
	}else{
		printf("topAndTop栈空\n");
		return 0;
	}
}

#if 0
//测试主界面
void displayMenu(){
	//system("clear");               // 清理屏幕
	printf("-       栈       -\n");
    printf("-      i:增加一个元素 q:删除栈顶元素       -\n");
    printf("-      l:获得栈顶元素 t:获得栈顶下一元素 e:退出     -\n ");
}
测试主函数
int main(int argc, char const *argv[])
{
	STACK *s = (STACK *)malloc(sizeof(struct stackRecord));
	printf("请输入想要建立的空间大小\n");
	int maxElements;
	scanf("%d",&maxElements);
	s = createStack(maxElements);
	while(1){
		displayMenu();
		char ch;
		ch = getchar();
		if(ch == 'i'){
			printf("请输入想增加的数据元素：");
			elementType num;
			scanf("%d",&num);
			push(num,s);
		}
		if(ch == 'q'){
			pop(s);
		}
		if(ch == 'l'){
			elementType num = top(s);
			printf("%d\n", num);
		}
		if(ch == 't'){
			elementType num = topAndTop(s);
			printf("%d\n", num);
		}
		if(ch == 'e'){
			disposeStack(s);
			exit(1);
		}
	}
	return 0;
}
#endif

#include <stdio.h>
// #include <gtk/gtk.h>
#include "stack.h"
int Priority(char ch)
{
	switch(ch)
	{
		case '(':
			return 3;
		case '*':
			return 2;
		case '/':
			return 2;
		case '+':
			return 1;
		case '-':
			return 1;
		default:
			return 0;
	}
}
#if 1
int main(int argc, char const *argv[])
{
	STACK *ch_stack,*num_stack;
	ch_stack = createStack(10);
	num_stack = createStack(10);
	char buf[50]="";
	printf("请输入表达式：\n");
	if(scanf("%s",buf) == 0){
		printf("输入错误\n");
	}
	// int k=scanf("%s",buf);
	char ch[100]="";
	sprintf(ch,"(%s)",buf);//这里有个小bug，就是字符串的开头和结尾必须要使用小括号，所以干脆直接初始化就好了
	// printf("%s\n", ch);
	int tmp,i=0,num1,num2;
	while(ch[i]!='\0'){
		if(ch[i] >= '0' && ch[i] <= '9'){
			tmp = ch[i] - '0';
			i++;
			if(ch[i] >= '0' || ch[i] <= '9'){
				push(tmp,num_stack);
				tmp = 0;
			}
		}else{
			if(isEmpty(ch_stack) !=0 || Priority(ch[i]) > Priority(top(ch_stack)) ||
				 ((top(ch_stack) == '(') && (ch[i] != ')')))
			{
				push(ch[i] , ch_stack);
				i++;
				continue;
			}
			
			if(top(ch_stack) == '(' && ch[i] == ')'){
				topAndTop(ch_stack);
				i++;
				continue;
			}else{
				switch(topAndTop(ch_stack)){
					case '+':
						num1 = topAndTop(num_stack);
						num2 = topAndTop(num_stack);
						push(num1 + num2 , num_stack);
						break;
					case '-':
						num1 = topAndTop(num_stack);
						num2 = topAndTop(num_stack);
						push(num1 - num2 , num_stack);
						break;
					case '*':
						num1 = topAndTop(num_stack);
						num2 = topAndTop(num_stack);
						push(num1 * num2 , num_stack);
						break;
					case '/':
						num1 = topAndTop(num_stack);
						num2 = topAndTop(num_stack);
						push(num1 / num2 , num_stack);
						break;
				}
			}
		}
	}

	printf("%d\n",topAndTop(num_stack));
	return 0;
}
#endif

OBJS=main.o stack.o
CC=gcc
CFLAGS=-Wall -O -g

edit:$(OBJS)
	$(CC) $^ -o $@
stack.o:stack.c stack.h 
main.o: main.c stack.h
clean:
	rm edit $(OBJS)