波兰数与逆波兰数
波兰数解决的是这样的一个问题：如果操作符与操作数是固定的，则语法上不需要括号仍然能被无歧义地解析。
波兰数又称之为前缀表达式，逆波兰数又称之为后缀表达式。而日常使用的表达式则称为中缀表达式。
中缀表达式
小学老师告诉我们，一个表达式的构成包含操作符（加减乘除）、操作数和括号构成。如何无需括号的参与就能正确无误的解析这个表达式？这就是波兰数要解决的问题。
举个例子，如： ( 15 / 7 − ( 1 + 1 ) ) ∗ 3 − ( 2 + ( 1 + 1 ) ) (15 / 7 - (1 + 1)) * 3 - (2 + (1 + 1)) (15/7−(1+1))∗3−(2+(1+1))
(15 / 7)
(1 + 1)
((15 / 7) - (1 + 1))
((15 / 7) - (1 + 1) * 3)
(1 + 1)
(2 + (1 + 1))
((15 / 7) - (1 + 1) * 3) - (2 + (1 + 1))
这样，上述式子就被正确解析出来了。
不同的人有不同的习惯，步骤是不唯一的。
中缀转后缀
为了使我们获得的后缀表达式唯一，我们规定同级运算是从左到右的。即 15 / 7 15/7 15/7 与 1 + 1 1+1 1+1 必须先 15 / 7 15/7 15/7。（左优先）
操作符的左、右操作数的位置是严格区分的。因为加减乘法具有交换律，所以无关紧要，但是除法是不满足的。而且计算机中只有整型的加减乘是满足交换律的，而浮点数是不满足的，所以我们要严格区分。
根据运算顺序，将符号写到两个操作数之后，构成三元组（左操作数，右操作数，操作符），将构成的三元组再作为操作数。直到所有运算完成，得到的便是一个逆波兰数。
15 7 /
1 1 +
15 7 / 1 1 + -
15 7 / 1 1 + - 3 *
1 1 +
2 1 1 + +
15 7 / 1 1 + - 3 * 2 1 1 + + -
15 7 / 1 1 + − 3 ∗ 2 1 1 + + − 15\text{ }7\text{ }/\text{ }1\text{ }1\text{ }+\text{ }-\text{ }3\text{ }*\text{ }2\text{ }1\text{ }1\text{ }+\text{ }+\text{ }- 15 7 / 1 1 + − 3 ∗ 2 1 1 + + − 便是一个逆波兰数。
后缀转中缀
从左往右扫描，遇到一个操作符，则将其前面两个操作数合并为一个操作数，直到合并整个完整个序列。（左优先）
同样，左右操作数的位置是严格区分的。
(15 / 7)
(1 + 1)
((15 / 7) - (1 + 1))
((15 / 7) - (1 + 1) * 3)
(1 + 1)
(2 + (1 + 1))
((15 / 7) - (1 + 1) * 3) - (2 + (1 + 1))
这样便成功的将后缀表达式解析为了中缀表达式。
后缀的运算
后缀表达式有什么呢？通过栈，很轻松的就能把表达式的结果算出来。
运算规则如下：
- 操作数，直接入栈。
- 操作符，从栈中弹出两个操作数，第一个为右操作数，第二个为左操作，运算后将结果压入栈。
- 直到整个表达式遍历完毕，栈底运算就是表达式的结果。
代码如下：
int evalRPN(vector<string>& tokens) {
stack<int> stk;
for (auto t : tokens) {
if (t.size() > 1 || t[0] >= '0' && t[0] <= '9') {
stk.push(stoi(t));
} else {
int r = stk.top(); stk.pop();
int l = stk.top(); stk.pop();
int res;
if (t[0] == '+') {
res = l + r;
} else if (t[0] == '-') {
res = l - r;
} else if (t[0] == '*') {
res = l * r;
} else if (t[0] == '/') {
res = l / r;
}
stk.push(res);
}
}
return stk.top();
}
后缀表达式
