逆波兰表达式，英文为 Reverse Polish notation，跟波兰表达式（Polish notation）相对应。
之所以叫波兰表达式和逆波兰表达式，是为了纪念波兰的数理科学家 Jan Łukasiewicz的创意。
- 平时我们习惯将表达式写成 (1 + 2) * (3 + 4)，加减乘除等运算符写在中间，因此称呼为中缀表达式。
- 而波兰表达式的写法为 (* (+ 1 2) (+ 3 4))，将运算符写在前面，因而也称为前缀表达式。
- 逆波兰表达式的写法为 ((1 2 +) (3 4 +) *)，将运算符写在后面，因而也称为后缀表达式。
波兰表达式和逆波兰表达式有个好处，就算将圆括号去掉也没有歧义。上述的波兰表达式去掉圆括号，变为* + 1 2 + 3 4。逆波兰表达式去掉圆括号，变成1 2 + 3 4 + *也是无歧义并可以计算的。事实上我们通常说的波兰表达式和逆波兰表达式就是去掉圆括号的。而中缀表达式，假如去掉圆括号，将 (1 + 2)(3 + 4) 写成 1 + 23 + 4，就改变原来意思了。
(2 + 3) * 4的波兰表示法为* + 2 3 4
1. 前缀
最后进栈的运算符(栈顶)与最近的两个操作数进行运算。//符合递归规律
//stof可以将字符串转换为双精度
#include<iostream>
#include<cstring>
using namespace std;
double p(){
string str;
cin >> str;
switch (str[0]){
case '+': return p() + p();
case '-': return p() - p();
case '*': return p() * p();
case '/': return p() / p();
default:
return stof(str);
}
}
int main(){
printf("%f\n", p());
return 0;
}2.中缀
用栈来实现。
undered_map来设定运算符的优先级。
碰到右括号就运算。
当有两个运算符时，将当前的运算符与栈顶的进行比较，当前优先级比较低则运算先前的，否则先压进栈。
运算结果要入栈。
循环结束后还要处理栈中剩余的运算符和数字，这时候从顶至底处理就行了。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack> //栈的头文件
#include<unordered_map> //判断优先级
using namespace std;
stack<int> num; //用来放数字
stack<char> op; //用来放符号
void eval(){
auto b = (); ();
auto a = (); ();
auto c = (); (); //取出进行运算的栈顶元素并弹出
int x;
if(c == '+') x = a + b;
else if(c == '-') x = a - b;
else if(c == '*') x = a * b;
else x = a / b;
(x); //新的结果入栈
return;
}
int main(){
unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}}; //设置优先级
string str;
cin >> str;
for(int i=0; i<(); i++){
auto c = str[i];
if(isdigit(c)){ //如果是数字
int x = 0, j = i;
while(j < () && isdigit(str[j])){ //注意边界条件
x = x * 10 + str[j++] - '0';
} //数字的输入
i = j - 1; //循环结束i会+1 这里i要重新定位到数字的最后一位
(x); //数字的存储
}
else if(c == '(') (c); //是左括号则入栈
else if(c == ')'){
while(() != '(') eval(); //是右括号且栈顶不是左括号则运算
(); //弹出栈顶符号（左括号）
}
else{ //是运算符
while(() && () != '(' && pr[()] >= pr[c]) eval(); //符号栈不为空且栈顶不是左括号时 若当前运算符优先级低则进行运算(之前存的) 高则先压入栈
(c); //入栈
}
}
while(()) eval(); //一直从上至下运算到符号用完
cout << () << endl; //栈顶数字即为最终结果
return 0;
}