#include <stdio.h>
#include <stdlib.h>
#define OK 0
#define ERROR -1
#define OVERFLOW -2
#define FALSE 0
#define TRUE !(FALSE)
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10
typedef int Status;
typedef int Bool;
typedef int SElemType;
typedef struct
 {
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack;//棧的元素類型
OPTRPrecede[][7]={'>','>','<','<','<','>','>',
				 '>','>','<','<','<','>','>',
				 '>','>','>','>','<','>','>',
				 '>','>','>','>','<','>','>',
				 '<','<','<','<','<','=',' ',
				 '>','>','>','>',' ','>','>',
				 '<','<','<','<','<',' ','='};//運算符優(yōu)先組存儲

Status InitStack(SqStack *s)
{//構(gòu)造一個空棧s
	s->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
	if (!s)
		exit(OVERFLOW);//存儲分配失敗
	s->top=s->base;
	s->stacksize=STACK_INIT_SIZE;
	return OK;
}
Status Push(SqStack *s, SElemType e)
{//插入元素e為新的棧頂元素
	if (s->top-s->base>=s->stacksize){
		s->base=(SElemType*)realloc(s->base, 
			(s->stacksize+STACKINCREMENT)*sizeof(SElemType));
		if (!s->base) 
			exit(OVERFLOW);
		s->top=s->base+s->stacksize;
		s->stacksize+=STACKINCREMENT;
	}
	*s->top++=e;
	return OK;
}//入棧
Status Pop(SqStack *s, SElemType *e)
{//若棧不空，則刪除s的棧頂元素，用e返回其值，并返回OK;否則返回ERROR;
	if (s->top==s->base)
		return ERROR;
	*e=*--s->top;
	return OK;
}
Status StackEmpty(SqStack s)
{
	return (s.top-s.base==0);
}//出棧
Status GetTop(SqStack s, SElemType *e)
{
	if (StackEmpty(s))
		return ERROR;
	*e=*(s.top-1);
	return OK;
}//取棧頂
Bool IsOPTR(int e)
{
	switch (e)
	{
	case '+':case '-':case '*':case '/':
	case '(':case ')':case '#':
		return TRUE;
	}
	return FALSE;
}//判斷是否是運算符
char Precede(int t, int c)
{
	int x, y;
	switch (t)
	{
		case '+': x=0; break;
		case '-': x=1; break;
		case '*': x=2; break;
		case '/': x=3; break;
		case '(': x=4; break;
		case ')': x=5; break;
		case '#': x=6; break;
	}
	switch (c)
	{
		case '+': y=0; break;
		case '-': y=1; break;
		case '*': y=2; break;
		case '/': y=3; break;
		case '(': y=4; break;
		case ')': y=5; break;
		case '#': y=6; break;
	}
	return OPTRPrecede[x][y];
}//判斷優(yōu)先組
int Operate(int a, int theta, int b)
{
	switch (theta){
		case '+': return a+b;
		case '-': return a-b;
		case '*': return a*b;
		case '/': return a/b;
	}
	return ERROR;
}//計算表達(dá)式
int main()
{
	SqStack optr, opnd;
	int a, b, theta;
	int c, t;
	InitStack(&optr);//運算符棧
	InitStack(&opnd);//運算數(shù)棧
	Push(&optr, '#');
	printf("表達(dá)式求值：\n");
	printf("輸入表達(dá)式(輸入元素只能為個位數(shù))：\n");
	c=getchar();
	while (c!='#' || (GetTop(optr, &t), t!='#'))
	{
		if (!IsOPTR(c))
		{
			Push(&opnd, c-'0');	
			printf("%d ",c-48);			
			c=getchar();
		}//不是運算符則進(jìn)棧
		else
		{
			switch (GetTop(optr, &t), Precede(t, c)){
				case '<'://棧頂元素優(yōu)先權(quán)低
					Push(&optr, c);					
					c=getchar();
					break;
				case '='://脫括號并接收下一字符
					Pop(&optr, &c);
					c=getchar();
					break;
				case '>'://退棧并將元素結(jié)果入棧
					Pop(&optr, &theta);
					Pop(&opnd, &b);
					Pop(&opnd, &a);	
					printf("%c ",theta);				
					Push(&opnd, Operate(a, theta, b));					
					break;
			}
		}
	}
	GetTop(opnd, &t);
	printf("\n");
	printf("輸出結(jié)果：\n");
	printf("%d\n", t);
}