#include<iostream>
using namespace std;
#include<stdlib.h>
#define MAXSIZE 100
typedef struct
{
char *base,*top;
int stacksize;
}SqStack;
int InitStack(SqStack &S)
{
S.base=new char[MAXSIZE];
if(!S.base)
exit(0);//存储分配失败
S.top=S.base;//top初始为base,空栈
S.stacksize=MAXSIZE;
return 1;
}
char GetTop(SqStack S)
{
if(S.top!=S.base)
return *(S.top-1);//返回栈顶元素的值,栈顶指针不变
}
int Push(SqStack &S,char e)
{
if(S.stacksize==S.top-S.base)
return 0;//栈满
*S.top++=e;
return 1;
}
int Pop(SqStack &S,char &e)
{
if(S.top==S.base)
return 0;//栈空
e=*--S.top;
return 1;
}
bool In(char ch)//判断读入的字符ch是否为运算符
{
if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')
return true;
else
return false;
}
char Precede(char i,char j)//判断运算符的栈顶元素与读入的运算符之间优先关系的函数
{
switch(i)
{
case'+':
case'-':
if(j=='*'||j=='/'||j=='(')
return '<';
else
return '>';
break;
case'*':
case'/':
if(j=='(')
return '<';
else
return '>';
break;
case'(':
if(j==')')
return '=';
else
return '<';
break;
case'#':
if(j=='#')
return '=';
else
return '<';
break;
}
}
char Operate(char a,char theta,char b)//二元运算
{
switch(theta)
{
case'+':
return a+b;
break;
case'-':
return a-b;
break;
case'*':
return a*b;
break;
case'/':
return a/b;
break;
}
}
char EvaluateExpression()
{
SqStack OPTR,OPND;
char ch,theta,a,b,x;
InitStack(OPTR);
InitStack(OPND);
Push(OPTR,'#');
cout<<"请输入表达式(以#结束):";
cin>>ch;
cout<<"表达式的运算结果为:";
while(ch!='#'||GetTop(OPTR)!='#')//表达式没有扫描完毕或OPTR的栈顶元素不为"#"
{
if(!In(ch))
{
Push(OPND,ch);
cin>>ch;
}
else
{
switch(Precede(GetTop(OPTR),ch))
{
case'<':
Push(OPTR,ch);
cin>>ch;
break;
case'>':
Pop(OPTR,theta);//弹出OPTR栈顶的运算符
Pop(OPND,b);
Pop(OPND,a);//弹出OPND栈顶的两个运算数
Push(OPND,Operate(a,theta,b));
break;
case'=': //OPTR的栈顶元素是'('且ch是')'
Pop(OPTR,x);
cin>>ch;
break;
}
}
return GetTop(OPND);
}
}
int main()
{
cout<<EvaluateExpression()<<endl;
return 0;
}
我想知道你为什么不用std::stack