1. 前缀表达式藏在波兰表达式里的计算密码第一次接触波兰表达式时我盯着那个* 2 3 4愣了半天——这玩意儿怎么算后来才知道这就是传说中的前缀表达式运算符永远跑在操作数前面。这种反人类的写法其实是计算机的最爱它彻底消除了括号的烦恼让表达式求值变得像流水线作业一样规整。在信息学奥赛的战场上OpenJudge和NOI题库里频繁出现的波兰表达式题目比如经典的1696题本质上都在考察我们对这种特殊表达式的拆解能力。不同于日常见到的中缀表达式234前缀表达式把运算符往前一丢变成 2 3 4计算顺序就完全明确了。这种结构特别适合用栈和递归来处理就像玩俄罗斯方块我们需要按照特定规则把运算符和数字一个个消掉。实际解题时会遇到几个典型陷阱负数的识别那个负号到底是运算符还是数字符号、除零错误处理、浮点数精度问题。有次我提交代码总是WA调试半天才发现是把-3.14误判成了减运算符和数字3.14。后来学乖了现在处理输入时会严格检查字符串长度和字符组成。2. 栈解法逆向扫描的暴力美学2.1 从右往左的魔法栈解法最反直觉的就是这个从右向左扫描的设定。为什么不能从左往右我当初在草稿纸上画了十几遍才想通前缀表达式* 2 3 4的实际计算顺序是(23)4如果从左往右扫遇到第一个运算符时根本不知道后面跟着哪两个操作数。而从右往左扫时总能保证先遇到操作数。具体操作就像玩叠叠乐遇到数字直接入栈比如先碰到4再碰到3遇到运算符就弹出栈顶两个元素当碰到时弹出3和4计算后将结果压栈347入栈继续扫描直到栈里只剩最终结果def prefix_stack(expr): stack [] for token in reversed(expr.split()): if token in -*/: a stack.pop() b stack.pop() stack.append(eval(f{a}{token}{b})) else: stack.append(float(token)) return stack[0]2.2 边界情况实战指南在OpenJudge 1696题中有几个刁钻的测试用例专门针对边界条件单数字表达式42应该直接返回42连续运算符* / 1 2 3 4要正确处理运算顺序浮点运算/ 5 2应该输出2.5而非2有次比赛我忘了处理除零错误直接让程序崩溃。现在我的标准处理流程会加上double calc(double a, double b, char op) { if (op / fabs(b) 1e-6) { cerr Division by zero!; return NAN; } // ...其他运算 }3. 表达式树把公式变成二叉树3.1 构建树的艺术表达式树就像给公式拍X光片把运算关系看得一清二楚。每个运算符都是分支节点操作数就是叶子节点。构建过程依然要用到栈但这次我们存的是节点指针读到数字创建叶子节点入栈读到运算符创建分支节点弹出两个子节点挂上去最后栈里剩下的就是树根class ExprNode { char op; double val; ExprNode left, right; } ExprNode buildTree(String[] tokens) { StackExprNode stack new Stack(); for (int i tokens.length - 1; i 0; i--) { ExprNode node new ExprNode(); if (isOperator(tokens[i])) { node.op tokens[i].charAt(0); node.left stack.pop(); node.right stack.pop(); } else { node.val Double.parseDouble(tokens[i]); } stack.push(node); } return stack.pop(); }3.2 树的遍历玄机建完树后求值就是个简单的后序遍历def eval_tree(node): if not node.left and not node.right: return node.val left_val eval_tree(node.left) right_val eval_tree(node.right) return calculate(left_val, right_val, node.op)这种方法的优势在于可以重复利用表达式树。比如要计算表达式在x1,2,3时的值建一次树就能多次求值。在动态规划类题目中特别有用我曾经用这个技巧把某个O(n²)的算法优化到了O(nlogn)。4. 递归解法最符合直觉的拆解4.1 递归三要素递归解法就像剥洋葱把前缀表达式一层层拆解终止条件当前元素是数字递归过程遇到运算符就递归计算后续两个操作数返回值运算符作用在两个递归结果上double solve(vectorstring tokens, int idx) { string token tokens[idx]; if (isdigit(token[0]) || (token[0] - token.size() 1)) { return stod(token); } double a solve(tokens, idx); double b solve(tokens, idx); return calc(a, b, token[0]); }4.2 下标控制的陷阱递归最头疼的就是这个移动的索引。我第一次写的时候没传引用导致所有递归调用都在啃第一个token。正确的做法一定要用引用传递idx或者用全局变量虽然不太优雅。在NOI的严格环境中递归深度可能是个问题对于超长表达式可能需要改成显式栈实现。实测对比三种方法栈解法代码最简洁但不易扩展表达式树内存占用大但可复用性强递归最好理解但有栈溢出风险在信息学奥赛的实战中我通常会先写递归版本确保逻辑正确再视情况优化为栈解法。遇到需要多次计算的场景比如某些动态规划题目表达式树就成了不二之选。