题目描述
后缀表达式,又称逆波兰式,指的是不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则)。
后缀表达式的计算:
从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 op 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果
例如:后缀表达式为“2 3 + 4 * 5 -”计算过程如下:
(1)从左至右扫描,将 2 和 3 压入堆栈;
(2)遇到 + 运算符,因此弹出 3 和 2( 3 为栈顶元素,2 为次顶元素,注意与前缀表达式做比较),计算出 3+2 的值,得 5,再将 5 入栈;
(3)将 4 入栈;
(4)接下来是 * 运算符,因此弹出 4 和 5,计算出 4 * 5 = 20,将 20 入栈;
(5)将 5 入栈;
(6)最后是-运算符,计算出 20-5 的值,即 15,由此得出最终结果。
从键盘读入一个后缀表达式(字符串),只含有0-9组成的运算数(全部为整数)及加(+)、减(-)、乘(*)、整除(/)四种运算符。每个运算数之间用一个空格隔开,不需要判断给你的表达式是否合法。以@作为结束标志。(注:仅在每个运算数后确保有一个空格分隔,运算符的前后不一定有空格,如“4 5 +9 -10 2 *+@”)
输入格式
一行,一个后缀表达式,长度小于255,以@作为结束标志。
输出格式
一个整数, 表达式的值。
#include
#include
#include
using namespace std;
const int MAX_SIZE = 256;
void evalRPN(char s[MAX_SIZE], int num)
{
stack<int> st;
for (int i = 0; i < num; i++) {
while (s[i] != '@')
{
int m;
if (s[i] >= '0' && s[i] <= '9')
{
int j = i + 1;
if (s[j] >= '0' && s[j] <= '9')
{
int k = j + 1;
if (s[k] >= '0' && s[k] <= '9')
{
m = (s[i] - '0') * 100 + (s[j] - '0') * 10 + (s[k] - '0');
i++;
}
else {
m = (s[i] - '0') * 10 + (s[j] - '0');
i++;
}
}
else m = s[i] - '0';
st.push(m);
}
else
{
switch (s[i])
{
case'+':
{
int a = st.top();
st.pop();
int b = st.top();
st.pop();
st.push(a + b);
break;
}
case'-':
{
int a = st.top();
st.pop();
int b = st.top();
st.pop();
st.push(b - a);
break;
}
case'*':
{
int a = st.top();
st.pop();
int b = st.top();
st.pop();
st.push(a * b);
break;
}
case'/':
{
int a = st.top();
st.pop();
int b = st.top();
st.pop();
if (a != '0')
st.push(b / a);
break;
}
}
}
}
}
cout << st.top();
}
int main()
{
char a[MAX_SIZE];
cin.get(a, MAX_SIZE, '@');
int num = strlen(a);
evalRPN(a, num);
return 0;
}