/***链栈实现表达式求值***/
#include<iostream>
#include <cstring>
using namespace std;

const char oper[7] = {'+','-','*','/','(',')','#'};
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int SElemType;
typedef int Status;
typedef struct SNode{
int data;
struct SNode *next;

{
S = NULL;
return OK;
}
{
if(!S)
return true;
return false;
}
{
SNode *p = new SNode;
if(!p)
{
return OVERFLOW;
}
p->data = e;
p->next = S;
S = p;
return OK;
}
{
SNode *p;
if(!S)
return ERROR;
e = S->data;
p = S;
S = S->next;
delete p;
return OK;
}
{
if(!S)
return ERROR;
e = S->data;
return OK;
}
bool In(char ch)
{//判断ch是否为运算符
for(int i = 0;i < 7; i++)
{
if(ch == oper[i])
{
return true;
}
}
return false;
}
char Precede(char theta1,char theta2)
{//判断运算符优先级
if((theta1 == '('&&theta2 == ')')||(theta1 == '#'&&theta2 == '#'))
{
return '=';
}
else if(theta1 == '('||theta1 == '#'||theta2 == '('
||(theta1 == '+'||theta1 == '-')&&(theta2 == '*'||theta2 == '/'))
{
return '<';
}
else
return '>';
}
int Operate(int first,char theta,int second)
{//计算两数运算结果
switch(theta)
{
case '+':
return first + second ;
case '-':
return first - second ;
case '*':
return first * second;
case '/':
return first / second;
}
return 0;
}

int EvaluateExpression()
{
// 算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和操作数栈，
// OP 为运算符集合
char ch[30];
int a,b,res = 0,x,top=0,thera;
InitStack (OPTR);
Push (OPTR,int('#'));
InitStack (OPND);
cin>>ch;
int i = 0,tmp;
while (ch[i] != '#' || (GetTop(OPTR,top) ,char(top)!= '#') )
{
//cout<<ch[2]<<endl;
if(!In(ch[i]))
{
//cout<<ch[i]<<endl;
tmp = ch[i]-'0';
// cout<<tmp<<endl;
while(!In(ch[++i])){
tmp *= 10;
tmp += ch[i]-'0';
}
Push(OPND, tmp);
//cout<<tmp<<endl;
} // ch不是运算符则进栈
else
{
GetTop(OPTR, top);
// cout<<char(top)<<ch[i]<<endl;
switch (Precede(char(top),ch[i]))
{ //比较OPTR的栈顶元素和ch的优先权
case '<': //当前字符ch压入OPTR栈，读入下一字符ch
Push(OPTR, ch[i]);
//cout<<ch[i]<<endl;
i++;
break;
case '>': //弹出OPTR栈顶的运算符进行相应运算，并将运算结果入栈
Pop(OPTR, thera);
Pop(OPND, b);
Pop(OPND, a);
Push(OPND, Operate(a, char(thera), b));
//cout<<Operate(a, char(thera), b)<<endl;
break;
case '=': //脱括号并接收下一字符
Pop(OPTR, x);
i++;
break;
} // switch
}
} // while
if(GetTop(OPND,res))
return res;
return 0;
} // EvaluateExpression

int main()
{
cout<<"请输入要计算的表达式,以#结束）："<<endl;
int  result = EvaluateExpression();
cout<<"计算结果为"<<result<<endl;
return 0;
}