信息学奥赛解题精讲：从栈到表达式树，三种方法玩转后缀表达式求值

1. 后缀表达式从陌生到熟悉第一次接触后缀表达式时我盯着3 4 5 *这样的符号组合看了半天——这玩意儿怎么算直到老师用一摞餐盘演示栈的操作我才恍然大悟。后缀表达式又称逆波兰表达式是一种不需要括号就能明确运算顺序的数学表示法它的核心规则就两条运算符在操作数后面运算顺序从左到右。举个生活中的例子做三明治时你会先拿面包操作数再放火腿操作数最后挤沙拉酱运算符。后缀表达式就像这个动作的书面记录面包 火腿 沙拉酱。在信息学奥赛中这类题目常以给定后缀表达式求值的形式出现比如经典的《信息学奥赛一本通》例题1331。2. 栈模拟法最直观的解题姿势2.1 算法原理栈模拟是处理后缀表达式的标配解法。想象你面前有一叠盘子栈遇到数字就往里放push遇到运算符就拿出最上面两个盘子pop进行操作再把结果放回去。整个过程就像快餐店配餐汉堡和薯条操作数先放托盘里遇到番茄酱运算符就把它们组合成套餐。def eval_rpn(tokens): stack [] for token in tokens: if token not in -*/: stack.append(int(token)) else: b stack.pop() a stack.pop() if token : stack.append(a b) elif token -: stack.append(a - b) elif token *: stack.append(a * b) else: stack.append(int(a / b)) # 注意整除处理 return stack[0]2.2 时空复杂度分析时间复杂度O(n)每个元素只入栈出栈一次空间复杂度O(n)最坏情况下需要存储所有数字2.3 避坑指南在实际比赛中我踩过两个坑运算顺序问题减法和除法要注意操作数顺序后弹出的数是第二个操作数大数处理题目说结果在2^64范围内记得用long long类型Python无需担心3. 表达式树化表达式为二叉树3.1 构建表达式树表达式树就像把公式拆解成树状结构。每个运算符是分支节点操作数是叶子节点。构建过程类似栈模拟只是栈里存的是节点指针。以3 4 5 *为例遇到3、4创建数字节点入栈遇到弹出4、3节点创建节点作为父节点遇到5创建数字节点入栈 4.遇到*弹出节点和5节点创建*节点作为新根struct Node { char op; long long val; Node *left, *right; }; Node* build_tree(vectorstring tokens) { stackNode* s; for(auto t : tokens) { if(isdigit(t[0])) { s.push(new Node{\0, stoll(t), nullptr, nullptr}); } else { Node* right s.top(); s.pop(); Node* left s.top(); s.pop(); s.push(new Node{t[0], 0, left, right}); } } return s.top(); }3.2 树的遍历求值用后序遍历左右根计算表达式树def evaluate(root): if not root.op: # 叶子节点 return root.val left evaluate(root.left) right evaluate(root.right) if root.op : return left right elif root.op -: return left - right elif root.op *: return left * right else: return left // right4. 递归解法分而治之的智慧4.1 递归思路把后缀表达式看作操作数 操作数 运算符的组合。从右向左处理遇到数字直接返回遇到运算符递归计算右侧两个表达式以3 4 5 *为例看到*需要计算3 4 和5计算3 4 看到先计算3和4返回7用7和5进行*运算4.2 代码实现long long eval(vectorstring tokens, int pos) { string s tokens[pos--]; if(isdigit(s.back())) return stoll(s); long long b eval(tokens, pos); long long a eval(tokens, pos); if(s ) return a b; if(s -) return a - b; if(s *) return a * b; return a / b; }5. 三种方法对比与实战选择方法优点缺点适用场景栈模拟直观高效O(n)复杂度难以处理复杂表达式分析单纯求值题表达式树可扩展性强构建稍复杂需要表达式转换的题目递归代码简洁栈空间消耗大特殊结构的表达式在NOIP比赛中我推荐优先使用栈模拟法——就像去年遇到的一道变形题要求在处理后缀表达式时记录中间结果。用栈可以轻松维护计算状态而其他方法则需要额外数据结构。6. 进阶技巧与优化策略当表达式包含更多运算符时需要注意优先级处理乘除优先于加减结合性相同优先级时左结合还是右结合错误处理遇到非法表达式时的容错对于超长表达式如1e5长度可以使用数组模拟栈减少STL开销采用并行计算分块处理仅限允许并行编程的比赛记得去年省赛有一道题需要同时处理多个后缀表达式我用了预处理表达式树LRU缓存的方法将时间复杂度从O(n^2)降到了O(n log n)。