3-7-5 逆波兰表达式求值 (20 分)
逆波兰表示法是一种将运算符（operator）写在操作数（operand）后面 的描述程序（算式）的方法。举个例子，我们平常用中缀表示法描述的算式（1 + 2）*（5 + 4），改为逆波兰表示法之后则是1 2 + 5 4 + *。相较于中缀表示法，逆波兰表示法的优势在于不需要括号。
请输出以逆波兰表示法输入的算式的计算结果。
输入格式:
在一行中输入1个算式。相邻的符号（操作数或运算符）用1个空格隔开。
输出格式:
在一行中输出计算结果。
限制:
1≤算式中运算符的总数≤99
运算符仅包括“+”、“-”、“*”，操作数、计算过程中的值以及最终的计算结果均在int范围内。```
输入样例1:
4 3 + 2 -
输出样例1:
5
输入样例2:
1 2 + 3 4 - *
输出样例2:
-3
AC代码
#include<iostream>
#include<string.h>
using namespace std;
struct shell
{
int data[10]={0};
int top;
int base;
};
int Init(shell &S)
{
S.top = 0;
S.base = 0;
}
int Push(shell &S,string a,int left,int right)
{
int k = left;
if(left != 0)k++;
for(k;k<right;k++)
{
S.data[S.top] = S.data[S.top]*10+a[k]-'0';
}
S.top++;
return 1;
}
int Compute(shell &S,char a)
{
S.top--;
S.base=S.top-1; //覆盖式计算
switch (a)
{
case '+': S.data[S.base] = S.data[S.base]+S.data[S.top];break;
case '-': S.data[S.base] = S.data[S.base]-S.data[S.top];break;
case '*': S.data[S.base] = S.data[S.base]*S.data[S.top];break;
}
S.data[S.top] = 0;
return 1;
}
main()
{
shell S;
string ch;
Init(S);
getline(cin,ch);
int left=0,right=0;
for(int i = 0;i<ch.length();i++)
{
char p = ch[i];
if(ch[i]==' ')
{
if(!right) right = i;
else {left = right; right = i;}
if(ch[right-1]>='0'&&ch[right-1]<='9'&& left!=right)//把空格间的数入栈
{
Push(S,ch,left,right);
}
else
{
Compute(S,ch[left+1]); 计算符号前2个数
}
}
}
if(right+1<ch.length()){
Compute(S,ch[right+1]);//计算最后一个符号
}
cout<<S.data[S.base];
}
