尝试证明
中缀表达式求值的本质是对「表达式树中序遍历的结果」进行解析的过程。因此我们有必要先了解一下表达式树的建立与解析的过程。
对于建立表达式树,显然的,在一棵表达式树中所有的分支结点都是操作符,所有的叶子结点都是操作数。对于求解表达式树,最好理解的是后缀表达式求解的逻辑,也就是对表达式树进行后序遍历的求解逻辑,即在分别求出左子树的值 a 和右子树的值 b 后,通过当前分支结点 x 存储的操作符 op 运算出结果 a op b 并向上回溯,传递「以 x 结点为根所在子树」的运算结果。
有了上述表达式树的运算逻辑,再来分析对表达式树中序遍历结果的解析逻辑。显然的我们可以根据中序遍历的结果将这棵表达式树建立起来并用深度优先遍历求解即可。这里我们介绍使用「栈」来模拟递归运算的求解逻辑。需要解决这样几个问题:如何模拟继续递归?什么时候运算?运算的操作数、操作符以及运算后的结果怎么存取?
对于中缀表达式,可以宏观的看做「左子树+根结点+右子树」,如果我们想要计算出最终的结果,那么最后一步一定是「左子树的值和右子树的值通过根结点存储的操作符」运算的结果。如果我们按照从左往右的顺序遍历中缀表达式,那么我们就必须存储根结点对应的操作符,这样才可以后续算出右子树的值后再取出根结点对应的操作符进行运算。这就解释了为什么我们要从左往右遍历中缀表达式来模拟继续递归的过程。
现在我们将左子树扩展为「左子树的左子树+左子树的根+左子树的右子树」,右子树保持不变,仍然看做一个整体。显然的左子树的根对应的运算优先级一定 $\ge$ 根结点的运算优先级,此时一定要先运算左子树的表达式再存储根结点的操作符。如何快速计算左子树表达式的运算结果?我们利用一个操作数栈存储左子树的左子树对应的值和左子树的右子树对应的值,再利用一个操作符栈存储左子树的根对应的操作符。这样就可以 $O(1)$ 的计算左子树表达式的值了。这就解释了为什么用双栈存取所有的操作数、操作符和运算结果,以及运算的时机:当当前操作符的优先级 $\le$ 操作符栈顶的优先级时进行运算。
至于表达式中出现的括号,可以理解为更高一级的运算符。按照上述逻辑维护好操作符栈后,两个括号之间的操作符一定是严格单调递增的,比如 (+/)
、(-*)
等。
双栈模拟
- 操作数栈:遇到数字直接入栈
- 操作符栈:
- 当前操作符等级 $\le$ 操作符栈顶操作符:进行运算。模拟回溯传值。
- 当前操作符等级 $>$ 操作符栈顶操作符:操作符入栈。模拟继续递归。
- 遇到左括号:操作符入栈。模拟更高等级的运算符并继续递归。
- 遇到右括号:不断运算直到遇到左括号。模拟回溯传值。
时间复杂度:$O(n)$
C++
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
void solve() {
string s;
cin >> s;
stack<int> num;
stack<char> op;
unordered_map<char, int> prior = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
auto calc = [&]() -> void {
int b = num.top(); num.pop();
int a = num.top(); num.pop();
char o = op.top(); op.pop();
if (o == '+') num.push(a + b);
else if (o == '-') num.push(a - b);
else if (o == '*') num.push(a * b);
else if (o == '/') num.push(a / b);
};
for (int i = 0; i < s.size(); i++) {
if (isdigit(s[i])) {
int x = 0, j = i;
while (i < s.size() && isdigit(s[j])) {
x = x * 10 + s[j++] - '0';
}
i = j - 1;
num.push(x);
} else if (s[i] == '(') {
op.push(s[i]);
} else if (s[i] == ')') {
while (op.top() != '(') {
calc();
}
op.pop();
} else {
while (op.size() && prior[s[i]] <= prior[op.top()]) {
calc();
}
op.push(s[i]);
}
}
while (op.size()) {
calc();
}
cout << num.top() << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
// std::cin >> T;
while (T--) solve();
return 0;
}
Python
有两个注意点:一个是取整问题,不能直接用 //
运算符,因为这是向下取整用的,我们希望向零取整,可以用 int(a / b)
。还有一个就是枚举的问题,Python 中使用 for 时,其中的循环变量 i 不会受到内部的影响,每次都只会+1。但是 C++ 中 for 中的 i 变量是会受到 for 内部的影响的。这和两种语言的 for 作用域有关。
from collections import defaultdict
from typing import List, Tuple
from itertools import combinations, permutations
import math, heapq
II = lambda: int(input())
FI = lambda: float(input())
MII = lambda: tuple(map(int, input().split()))
LII = lambda: list(map(int, input().split()))
def solve() -> None:
s = input()
num, op = [], []
prior = {'(': 0, '+': 1, '-': 1, '*': 2, '/': 2}
def calc() -> None:
b = num[-1]; num.pop()
a = num[-1]; num.pop()
o = op[-1]; op.pop()
if o == '+': num.append(a + b)
elif o == '-': num.append(a - b)
elif o == '*': num.append(a * b)
elif o == '/': num.append(int(a / b))
i = 0
while i < len(s):
if s[i].isdigit():
x, j = 0, i
while j < len(s) and s[j].isdigit():
x = x * 10 + int(s[j])
j += 1
i = j - 1
num.append(x)
elif s[i] == '(':
op.append(s[i])
elif s[i] == ')':
while op[-1] != '(':
calc()
op.pop()
else:
while len(op) and prior[s[i]] <= prior[op[-1]]:
calc()
op.append(s[i])
i += 1
while len(op): calc()
print(num[-1])
if __name__ == '__main__':
T = 1
# T = II()
while T: solve(); T -= 1