题目描述
逆波兰表示法是一种表示法,其中每个运算符都在其所有操作数的后面出现。例如,表达式(1+2)×(5+4)可以表示为逆波兰表达式1 2 + 5 4 + ×。逆波兰表示法的优点之一是它没有括号。
编写一个程序,读取逆波兰表示法中的表达式并打印计算结果。
逆波兰表示法中的表达式是使用栈计算的。要计算表达式,程序应按顺序读取符号。如果符号是操作数,则应将相应的值压入栈。另一方面,如果符号是一个运算符,程序应该从堆栈中弹出两个元素,执行相应的操作,然后将结果压入栈。程序应重复此操作。
输入
在一行中给出一个表达式。两个连续符号(操作数或运算符)由空格字符分隔。您可以假设只有 +, - 和 * 作为运算符给出,并且表达式中的数字都是小于10
6
的正整数。
输出
在一行中打印计算结果。
约束
2≤ 表达式中数字的数量 ≤ 100
1≤ 表达式中操作符的数量≤ 99
−10
9
≤ 堆栈中的值 ≤ 10
9
输入样例
1 2 + 3 4 - *
输出样例
-3
算法1
栈
C++ 代码
#include <bits/stdc++.h>
using namespace std;
stack<int> nums;
stack<int> op;
int main()
{
string s;
getline(cin,s);
for(int i=0;s[i];i++)
{
if(isdigit(s[i]))
{
int j=i;
int x=0;
while(s[j]&&isdigit(s[j]))
{
x=x*10+s[j++]-'0';
}
nums.push(x);
i=j-1;
}
else if(s[i]=='+'||s[i]=='-'||s[i]=='*')
{
op.push(s[i]);
if(op.size())
{
int x;
char c=op.top();
int a=nums.top();
nums.pop();
int b=nums.top();
nums.pop();
op.pop();
if(c=='+')
{
x=a+b;
}
if(c=='-')
x=b-a;
if(c=='*')
{
x=a*b;
}
nums.push(x);
}
}
}
cout<<nums.top();
}