include<iostream>
#include <stdio.h>
#include <string.h>
#define MAXSIZE 100
using namespace std;
typedef char SElemType;
typedef struct
{
SElemType *base; //栈底指针
SElemType *top; //栈顶指针
int stacksize; //栈可用最大容量
}SqStack;
int InitStack( SqStack &s ) //初始化
{
s.base=new SElemType[MAXSIZE];
if(!s.base) return 0 ;
s.top=s.base;
s.stacksize=MAXSIZE;
return 1;
}
int StackEmpty( SqStack s ) //判断栈是否为空
{
if(s.base=s.top) return 1;
else return 0;
}
int StackLength( SqStack s )//求栈长度
{
return s.top-s.base;
}
int Push( SqStack &s, SElemType e) //进栈
{
if(s.top-s.base==s.stacksize) return 0;
*s.top++=e;
return 1;
}
int Pop( SqStack &s, SElemType &e) //出栈
{
if(s.top==s.base) return 0;
e=*--s.top;
return 1;
}
SElemType GetTop(SqStack s) //取栈顶元素
{ SElemType e;
if(s.top==s.base) return '0';
e=*(s.top-1);
return e;
}
int In(SElemType ch) //判断输入的是符号还是数字
{
if (ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'=='#')
return 1;
else return 0;
}
SElemType Precede(char n,char ch) //比较优先级
{ char f;
switch(n)
{
case'+':
if(ch=='+'||ch=='-'||ch==')'||ch=='#')
f='>';
else f='<';
break;
case'-':
if(ch=='+'||ch=='-'||ch==')'||ch=='#')
f='>';
else f='<';
break;
case'*':
if(ch==')')
f='<';
else f='>';
break;
case'/':
if(ch==')')
f='<';
else f='>';
break;
case'(':
if(ch==')')
f='=';
else f='<';
break;
case')':
f='>';
break;
case'#':
if(ch=='#')
f='=';
else f='<';
break;
}
return f;
}
SElemType Operate(char a,char theta,char b)
{ char c;
a=a-48;
b=b-48;
switch(theta)
{
switch(theta)
{
case'+':
c=a+b+48;
break;
case'-':
c=(a-b)+48;
break;
case'*':
c=(a*b)+48;
break;
case'/':
c=(a/b)+48;
break;
}
}
return c;
}
SElemType Ev()
{ SqStack OPND;
SqStack OPTR;
char ch,a,b,theta;
InitStack(OPND); //存放数字
InitStack(OPTR); //存放符号
Push(OPTR,'#'); //起始符
cin>>ch;
while(ch!='#'||GetTop(OPTR)!='#') //终止输入标志# 取栈顶元素判断是否为#
{ char x;
if(!In(ch)) //如果输入的不是运算符，存入OPND栈
{
Push(OPND,ch);
cin>>ch;
}
else
switch(Precede(GetTop(OPTR),ch)) //如果是运算符，比较优先级
{
case'<':
Push(OPTR,ch); //栈顶优先级小，将当前字符压入OPTR栈，继续读下一字符
cin>>ch;
break;
case'>': //优先级大,弹出OPTR栈顶运算符和OPND栈顶运算数
Pop(OPTR,theta);
Pop(OPND,b);Pop(OPND,b);
Push(OPND,Operate(a,theta,b)); //进行运算后压入OPND栈
break;
case'=':
Pop(OPTR,x);cin>>ch; //优先级相等，即栈顶为"（ "输入ch为 ") ",则弹出栈顶的左括号，读下一字符
break;
}
}
return GetTop(OPND); //OPND栈顶元素即表达式的求值结果
}
int main()
{
cout<<"请输入算术表达式，以#结束"<<endl;
cout<<Ev()<<endl;
}
