波兰数与逆波兰数
波兰数解决的是这样的一个问题:如果操作符与操作数是固定的,则语法上不需要括号仍然能被无歧义地解析。
波兰数又称之为前缀表达式,逆波兰数又称之为后缀表达式。而日常使用的表达式则称为中缀表达式。
中缀表达式
小学老师告诉我们,一个表达式的构成包含操作符(加减乘除)、操作数和括号构成。如何无需括号的参与就能正确无误的解析这个表达式?这就是波兰数要解决的问题。
举个例子,如: ( 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();
}
后缀表达式