将中缀表达式转化成后缀表达式存储在队列中，然后利用后缀表达式求表达式的值并输出。
将中缀表达式转化成后缀的思想：
1、创建一空队列，用来存放后缀表达式，建立并初始化操作符栈OPTR，将表达式起始符“#”压入OPTR栈。
2、依次读入表达式中每个字符ch，循环执行（3）至（5），直至求出整个表达式转换完毕。
3、取出OPTR的栈顶元素，当OPTR的栈顶元素和当前读入的字符ch均为“#”时，整个中缀表达式转换完毕。
4、若ch不是运算符，则进队，读入下一字符ch。
5、若ch是运算符，则根据OPTR的栈顶元素和ch的优先权比较结果，做不同的处理。
① 若是小于，则ch压入OPTR栈，读入下一字符ch。
② 若是大于，则弹出OPTR栈顶的运算符，进队。
③ 若是等于，则OPTR的栈顶元素是“(”且ch是“)”，这时弹出OPTR栈顶的“(”，相当于去掉括号，然后读入下一字符ch。
#include
#include
#include
#include
#define OVERFLOW -2
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#include
using namespace std;
typedef int Status;
typedef char SElemType;
typedef struct
{
SElemType *base;
int front;
int rear;
}SqQueue;
Status InitQueue(SqQueue &Q) //初始化
{
Q.base=new SElemType[MAXSIZE];
if(!Q.base) exit(OVERFLOW);
Q.front=Q.rear=0;
return OK;
}
Status EnQueue (SqQueue &Q,SElemType e) //入队
{
if((Q.rear+1)%MAXSIZE==Q.front)
return ERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXSIZE;
return OK;
}
Status DeQueue(SqQueue &Q,SElemType &e) //出队
{
if(Q.front==Q.rear)
return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXSIZE;
return OK;
}
SElemType GetHead(SqQueue Q)//取队头元素
{
if(Q.front!=Q.rear)
return Q.base[Q.front];
}
//--------顺序栈的存储结构------
typedef struct
{
SElemType *base; //栈底指针
SElemType *top; //栈顶指针
int stacksize; //占可用的最大容量
}SqStack;
Status InitStack (SqStack &S)
{//构造一个空栈
S.base=new SElemType[MAXSIZE]; //为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
if (!S.base) exit(OVERFLOW); //动态分配失败
S.top=S.base; //top初始为base，空栈
S.stacksize=MAXSIZE; //stacksize置为栈的最大容量MAXSIZE
return OK;
}
Status Push(SqStack &S,SElemType e)
{//插入元素e为新的栈顶元素
if(S.top-S.base==S.stacksize) return ERROR; //栈满
*S.top++=e; //元素e压入栈顶，栈顶指针加1
return OK;
}
Status Pop(SqStack &S,SElemType &e)
{//删除s的栈顶元素，用e返回其
if (S.top==S.base) return ERROR; //栈顶
e=*--S.top; // 栈顶指针减1，将栈顶元素为e
return OK;
}
SElemType GetTop(SqStack S)
{//返回S的栈顶元素，不修改栈顶指针、
if(S.top!=S.base) //栈非空
return *(S.top-1); //返回栈顶元素的值，栈顶指针不变
}
Status In(SElemType c)
{
switch(c) //判断读入的字符是哪一种运算符，
{
case '+':
return TRUE;
break;
case '-':
return TRUE;
break;
case '*':
return TRUE;
break;
case '/':
return TRUE;
break;
case '(':
return TRUE;
break;
case ')':
return TRUE;
break;
case '#':
return TRUE;
break;
default:
return FALSE;
}
}
SElemType Precede(SElemType t1,SElemType t2)
{
SElemType f;
switch(t2) //判断运算符栈的栈顶元素和读入的运算符之间谁的优先级更高，并返回结果
{
case '+':
if (t1=='('||t1=='#')
f='<';
else
f='>';
break;
case '-':
if (t1=='('||t1=='#')
f='<';
else
f='>';
break;
case '*':
if (t1=='+'||t1=='-'||t1=='('||t1=='#')
f='<';
else
f='>';
break;
case '/':
if (t1=='+'||t1=='-'||t1=='('||t1=='#')
f='<';
else
f='>';
break;
case '(':
if (t1=='+'||t1=='-'||t1=='('||t1=='#'||t1=='*'||t1=='/')
f='<';
break;
case ')':
if (t1=='+'||t1=='-'||t1=='*'||t1=='/'||t1==')')
f='>';
else if (t1=='(')
f='=';
break;
case '#':
if (t1=='#')
f='=';
else
f='>';
break;
default:
cout<<"输入超出范围。。。";
}
return f;
}
SElemType Operate(SElemType a,SElemType theta,SElemType b)
{
SElemType c;
a=a-'0'; //因为a，b均为字符型，所以转化成int型
b=b-'0';
switch(theta)
{
case '+':
c=a+b+'0';break; //再将计算的结果转化为字符型
case '-':
c=a-b+'0';break;
case '*':
c=a*b+'0';break;
case '/':
c=a/b+'0';break;
}
return c; //返回计算结果
}
char EvaluateExpression()
{//算数表达式求值的算符优先算法，设OPTR和 OPND分别为运算符栈和操作数栈
SqStack OPTR;
SqQueue OPND;
char ch,theta,a,b,c,x,w;
InitQueue(OPND); //初始化OPND队列
InitStack(OPTR); //初始化OPTR栈
Push(OPTR,'#'); //将表达式起始符“#”OPTR栈
cin>>ch;
while (ch!='#'||GetTop(OPTR)!='#') //表达式没有扫描完毕或者OPTR的栈顶元素不为“#”
{
if (!In(ch)) //判断ch是不是运算符，不是则入OPND队
{
EnQueue(OPND,ch);
cin>>ch;
}
else
switch(Precede(GetTop(OPTR),ch)) // 比较OPTR的栈顶元素和ch的优先级
{
case '<':
Push(OPTR,ch); //当前字符ch压入OPTR栈 ，读入下一个字符ch
cin>>ch;
break;
case '>':
Pop(OPTR,theta); //弹出OPTR栈顶的运算符
b=GetHead(OPND); //弹出OPND队列的运算数，
a=GetHead(OPND); //弹出OPND队列的运算数，
EnQueue(OPND,Operate(a,theta,b)); //将运算结果入OPND队列
break;
case '=': //OPTR的栈顶元素是“（”且ch是“）”
Pop(OPTR,x); //弹出OPTR栈顶的"(",
cin>>ch; //读入下一个字符ch
break;
}
}
return GetHead(OPND); //OPND队列元素即为表达式求值结果
}
int main()
{
char w;
cout<<"请输入算数表达式，并以#结束\n";
w=EvaluateExpression(); //将运算结果赋值给w
w=w-48; //将字符转换成数字
printf("The result of expression is %d\n",w);
}