前缀表达式求值：从右往左扫描的栈式算法详解

这是一道很经典的数据结构题目，很多朋友在学栈和递归的时候都会遇到。我当年第一次做这题也卡了一阵子，倒不是代码写不出来，而是方向搞反了，一直在想怎么从左往右处理。后来想通前缀表达式的本质之后，代码其实就几行。这篇就把整个思路拆开揉碎了讲，从“为什么从右往左”到“负数怎么处理”，再到完整代码和踩坑记录，一次性讲透。

1. 前缀表达式是什么：先从题目背景说起

1.1 中缀、前缀、后缀三种写法

日常写数学表达式，习惯用的是中缀形式，比如5 + 2 * 3，运算符在中间，还要靠优先级和括号来消除歧义。但机器不喜欢这种写法。计算机真正容易处理的是不需要括号、不需要优先级的线性表达式，也就是前缀和后缀形式。

前缀表达式也叫做波兰表达式，运算符写在操作数前面。同一个算式可以用下面三种方式表达：

• 中缀：(5 + 2) * 3
• 后缀：5 2 + 3 *
• 前缀：* + 5 2 3

其中* + 5 2 3的意思是：先计算5 + 2，再把结果乘以3，对应中缀的(5 + 2) * 3。

后缀表达式大家接触得比较多，就是编译原理里常见的逆波兰式，只需要一个栈从左到右扫描即可完成求值。中缀转后缀的调度场算法也有很多人写过。前缀表达式则相对少一些，但本质上是同一个东西，只是方向反了。本题就是直接给一个前缀表达式，要求求出它的值。

提示：前缀和后缀都是一种“扁平化”的树形结构。表达式本身就对应一棵表达式树，前缀是树的先序遍历，后缀是树的后序遍历，中缀是树的中序遍历。理解这一点，很多思路就顺了。

1.2 这道题到底要做什么

题目输入是一行用空格分隔的表达式，里面包含整数、运算符+ - * /，也可能出现小数。要求计算出前缀表达式的值，输出时保留两位小数。典型的输入就像：

* + 11.0 12.0 + 24.0 35.0

对应中缀是(11 + 12) * (24 + 35)，结果应该是23.0 * 59.0 = 1357.0。

拿到题目先别急着写代码，要看清楚几个关键信息：

• 操作数可能是整数，也可能是小数，比如11.0
• 符号包括+ - * /四种
• 输出要求保留两位小数
• 表达式可能以负数开头，比如- 5 3表示5 - 3，而负数操作数本身也可能出现，比如-5

这几个信息点，每一个都对应一个实现细节。后面会逐个拆开。

2. 求值思路：为什么从右往左扫

2.1 从右往左的栈式算法

后缀表达式是从左往右扫描的。遇到操作数就压栈，遇到运算符就弹出两个数运算，再把结果压回栈里。前缀表达式恰好是后缀表达式的镜像，所以只要把方向反过来，从右往左扫描，规则就完全一样了。

具体流程是这样的：

1. 把表达式按空格拆成列表。
2. 从列表末尾往前扫描。
3. 如果当前元素是操作数，直接压栈。
4. 如果当前元素是运算符，从栈中弹出两个操作数，按照出栈顺序进行计算。
5. 把计算结果压回栈中。
6. 全部处理完后，栈顶元素就是表达式的值。

这个算法的时间复杂度是 O(n)，空间复杂度是 O(n)，其中 n 是表达式中元素个数。每一步只做常数次操作，效率很高，完全满足 25 分题目的性能要求。

试一下：表达式* + 11.0 12.0 + 24.0 35.0。

从右往左读：

• 遇到35.0，压栈。栈：35.0
• 遇到24.0，压栈。栈：35.0, 24.0
• 遇到+，弹出24.0和35.0，计算24.0 + 35.0 = 59.0，压栈。栈：59.0
• 遇到12.0，压栈。栈：59.0, 12.0
• 遇到11.0，压栈。栈：59.0, 12.0, 11.0
• 遇到+，弹出11.0和12.0，计算11.0 + 12.0 = 23.0，压栈。栈：59.0, 23.0
• 遇到*，弹出23.0和59.0，计算23.0 * 59.0 = 1357.0，压栈。栈：1357.0

结果就是1357.0。

这个模拟过程看起来很简单，但有一个非常容易踩坑的地方：出栈的两个操作数，到底谁在前谁在后？这直接决定了减法和除法算不算得对。

2.2 操作数顺序的细节

先给结论：从右往左扫描时，遇到运算符，先弹出的是左操作数，后弹出的是右操作数。

什么意思？以- 5 2为例，它表示中缀的5 - 2。从右往左扫描：

• 先读2，压栈
• 再读5，压栈
• 遇到-，弹出第一个数是5，第二个数是2

此时正确的运算应该是5 - 2 = 3。也就是说，先弹出的5放在运算符左边，后弹出的2放在运算符右边。

反过来，如果你写成second - first，就会得到2 - 5 = -3，整个表达式就错了。加法和乘法因为满足交换律，顺序错了也不容易发现，但减法和除法一错就全错了。

所以代码里一定要写成：

double first = stk.top(); stk.pop(); double second = stk.top(); stk.pop(); result = first / second;

注意这里的first是原表达式里靠左的操作数，不是靠右的。用一个具体的除法式子验证一下：/ 6 3表示6 / 3。从右往左扫描，先读3压栈，再读6压栈，遇到/，弹出6和3，计算6 / 3 = 2。说明先弹出的6是左操作数。

2.3 递归视角统一理解

除了栈的思路，也可以从递归的角度理解这道题。前缀表达式的结构是“运算符 + 左操作数 + 右操作数”，其中左操作数和右操作数本身也可能是子表达式。因此可以写一个递归下降的解析器：

parse(): token = 从前往后取下一个元素 如果 token 是运算符: 左值 = parse() 右值 = parse() 返回 左值 op 右值 否则: 返回 数字(token)

这个方法是从前往后递归解析，和从右往左的栈式方法最终逻辑完全一致。栈式方法本质上是递归的迭代版本，只不过递归用的是系统栈，迭代用的是显式栈，方向正好相反。

两种思路都要理解。递归写法在某些题目里更方便，比如题目要求输出表达式树结构时；而栈式写法更贴近本题的求值需求，代码也更紧凑。我用栈式写法实现。

3. 关键实现细节

3.1 分词与负数的坑

输入是按空格分隔的，所以第一步就是拆分。C++ 里可以用stringstream直接按空格读取，Java 里可以用split(" ")，Python 里直接用input().split()就行。

但真正需要注意的，是如何区分负数和减号。

看这样一个前缀表达式：+ -5 3，它表示(-5) + 3，第一个操作数是负数-5。如果只按第一个字符是不是-来判断，就会把它误判成运算符，导致流程出错。

踏实做法是：先判断当前 token 的长度。如果长度是 1，并且字符是+ - * /之一，就当成运算符处理。否则不管 token 是不是以负号开头，都当成操作数解析。

bool isOperator(const string &token) { return token.size() == 1 && token.find_first_of("+-*/") != string::npos; }

这里有个很实用的原则：判断运算符优先级不是“当前字符是不是运算符号”，而是“当前 token 是否恰好等于某个运算符号”。因为负数操作数长这样：-5，长度是 2，不会被误判；而减号运算符长这样：-，长度是 1。

3.2 除法与除零

四则运算里，除法有一个额外的边界问题：除数为零。

如果表达式是/ 5 0，直接计算5 / 0会导致程序崩溃。题目里说了“除数不为0”，或者有时会说保证表达式合法。但为了稳妥，最好在代码里加一层判断：

if (fabs(second) < 1e-9) { cout << "ERROR" << endl; return 0; }

不需要真用second == 0来判断浮点数是否为零，因为浮点数在计算过程中可能出现极小误差。用绝对值小于一个极小阈值来判断更稳妥。当然如果题目保证输入合法，这段代码可以不写，但写上也不影响通过，而且能避免本地测试时直接崩掉。

3.3 运算过程中的类型选择

操作数可能是整数，也可能是小数。所以不能把所有值都存成int，否则5 / 2会得到2而不是2.5。应该统一用double存储栈中的操作数和计算结果。

stack<double> stk;

把字符串转换成double时，C++ 里直接用stod，C 里用atof，Python 里直接float()。注意别用atoi，那个会丢掉小数部分。

输出格式也有讲究。题目要求保留两位小数，C++ 用：

cout << fixed << setprecision(2) << stk.top() << endl;

Python 用：

print(f"{value:.2f}")

如果不加fixed，像1357.0可能会被输出成1357.000000或者1357。加上fixed和setprecision(2)再输出，格式就固定了。

3.4 栈弹出时别忘了检查

写代码时很容易忘记一个细节：每弹出一个元素，栈的尺寸就少一。如果表达式非法，比如操作数不够，或者表达式根本不是一个完整的前缀表达式，那么可能在某个运算符执行时栈顶已经为空，继续pop()会直接越界或报错。

有没有必要做这个检查？如果题目保证输入合法，考试环境下可以省略。但本地测试一些奇怪数据时，加上检查可以帮助你快速发现问题。我一般会在代码里保留一个弹栈函数：

double popValue(stack<double> &stk) { if (stk.empty()) { cout << "expression error" << endl; exit(0); } double val = stk.top(); stk.pop(); return val; }

3.5 关于表达式本身的长度

前缀表达式的长度不会很长，题目中给的 n 一般不超过 100 个 token。用栈没有任何问题。但如果你在做其他变种题，比如表达式长达百万级，就要考虑把栈换成数组模拟，避免递归调用过深导致栈溢出。栈式方法天然不会递归，所以这是它的优势之一。

4. 完整代码与样例推演

4.1 C++ 参考实现

下面是我实际提交过的写法，去掉了不必要的封装，只保留核心逻辑：

#include <iostream> #include <stack> #include <string> #include <sstream> #include <iomanip> #include <cmath> using namespace std; bool isOperator(const string &token) { return token.size() == 1 && token.find_first_of("+-*/") != string::npos; } double applyOp(double first, double second, char op) { switch (op) { case '+': return first + second; case '-': return first - second; case '*': return first * second; case '/': return first / second; default: return 0; } } int main() { string line; getline(cin, line); stringstream ss(line); vector<string> tokens; string token; while (ss >> token) { tokens.push_back(token); } stack<double> stk; for (int i = (int)tokens.size() - 1; i >= 0; i--) { const string &cur = tokens[i]; if (!isOperator(cur)) { stk.push(stod(cur)); } else { if (stk.size() < 2) { cout << "ERROR" << endl; return 0; } double first = stk.top(); stk.pop(); double second = stk.top(); stk.pop(); if (cur == "/" && fabs(second) < 1e-9) { cout << "ERROR" << endl; return 0; } double result = applyOp(first, second, cur[0]); stk.push(result); } } cout << fixed << setprecision(2) << stk.top() << endl; return 0; }

这个版本有几个字段需要解释。

applyOp函数把运算逻辑单独抽出来，主循环只负责从栈里取数、运算、压回结果，逻辑清晰，调试也方便。applyOp里没有单独处理除零，因为除零判断提前在外面做了。你也可以把除零判断直接写进applyOp，看个人习惯。

isOperator中的find_first_of("+-*/")用了字符串查找，因为token长度为 1，所以这个查找结果只有两个可能性：找到了，或者没找到。find_first_of返回的是下标，如果没有匹配字符会返回string::npos，这里的判断是对的。

stod是 C++11 里把字符串转成double的函数，输入"11.0"会得到11.0。它还可以处理"-5"，所以负数操作数可以直接解析。需要注意stod如果解析失败会抛出异常，但题目保证输入合法，这里就不额外包try-catch了。

4.2 Python 参考实现

有些同学可能主攻 Python，我也写了一份对照版，思路完全一致：

import sys def is_operator(token): return len(token) == 1 and token in "+-*/" def main(): data = sys.stdin.read().strip().split() stk = [] for token in reversed(data): if is_operator(token): if len(stk) < 2: print("ERROR") return first = stk.pop() second = stk.pop() if token == '/' and abs(second) < 1e-9: print("ERROR") return if token == '+': stk.append(first + second) elif token == '-': stk.append(first - second) elif token == '*': stk.append(first * second) elif token == '/': stk.append(first / second) else: stk.append(float(token)) print(f"{stk[-1]:.2f}") if __name__ == "__main__": main()

Python 里float("-5")可以直接把负数转成浮点数，跟 C++ 的stod一样。data是拆好的 token 列表，reversed(data)从后往前遍历，等价于 C++ 的倒序 for 循环。

4.3 样例一步一步推演

拿题目的标准样例* + 11.0 12.0 + 24.0 35.0来演示程序每一步的执行过程：

初始栈：空

最终栈顶是1357.0，输出1357.00。

再看一个带减法和除法，容易算错的例子：

输入：- / + 10 5 3 2

先翻译成表达式树：

• 最外层是-，左操作数是/ (+ 10 5) 3，右操作数是2
• 也就是(10 + 5) / 3 - 2

中缀值：15 / 3 - 2 = 5 - 2 = 3

用程序模拟：

• 从右往左读2，压栈：[2]
• 读3，压栈：[2, 3]
• 读5，压栈：[2, 3, 5]
• 读10，压栈：[2, 3, 5, 10]
• 读+，弹出10和5，10 + 5 = 15，压栈：[2, 3, 15]
• 读/，弹出15和3，15 / 3 = 5，压栈：[2, 5]
• 读-，弹出5和2，5 - 2 = 3，压栈：[3]

结果为3.00。

如果你没有遵守“先弹出的是左操作数”的顺序，把减法写成了2 - 5 = -3，这一步就错了。所以说，顺序真的不是小问题。

5. 常见问题与测试用例

5.1 常见错误整理

其中操作数顺序和负数判断是我见过出现频率最高的两个坑，也是这道 25 分题最容易丢分的点。

5.2 边界测试用例

多准备几组数据，排查的时候一条条跑。

第一组，普通加减法：

+ 1 2

期望输出：3.00

第二组，只含一个数字：

5

期望输出：5.00

这种情况扫描一个元素就结束了，栈里只有一个数，直接输出。很多人会忽略这种极端输入。

第三组，连续除法：

/ / 100 5 4

对应中缀是100 / 5 / 4 = 5，期望输出5.00

第四组，带负数操作数：

+ * 2 -3 4

对应中缀是2 * (-3) + 4，结果是-2，期望输出根据标准的四舍五入应为-2.00

这里也是很多人容易犯错的地方。-3作为独立 token，长度是 2，不会和运算符-混淆。

第五组，优先级靠嵌套体现的复杂表达式：

- / + 10 5 3 2

期望输出：3.00

第六组，小数参与运算：

* 1.5 2.5

期望输出：3.75

5.3 调试时的一个实用技巧

如果某个用例跑出来结果不对，又不知道是哪一步出了问题，可以在主循环里临时加一行输出，把每一步的 token 和栈内容打出来。比如在 C++ 代码里加：

cout << "trace token: " << cur << ", stack size: " << stk.size() << endl;

跑一遍之后就很容易定位：是哪个运算符的组合出了问题，是操作数压栈顺序不对，还是某一步运算和预期结果不一致。排查完再删掉这些调试语句。如果题目是在线评测，记得提交前把调试输出清干净，不然会算作输出格式错误。

5.4 关于题目分数的想法

这道题分值 25 分，在整套题里属于中等难度的基础题。之所以给这么高的分数，不是因为算法本身复杂，而是因为它同时考察了栈的使用、表达式的理解、字符串处理和浮点数输出格式几个基础能力。任何一个环节掉链子，都可能丢分。

作为备考的人来说，这道题至少要能做到：拿到任意前缀表达式，能快速用笔模拟出求值过程，能不看模板写出正确代码。如果连笔算都不会，写代码的时候就会一团乱麻。所以我建议在动键盘之前，先在纸上画几个例子，把栈的变化过程画清楚，再动手写代码。

先画出表达式树也行。比如对于* + 11.0 12.0 + 24.0 35.0，画出树之后，树的叶子是操作数，根和内部节点是运算符。求值过程就是从叶子向根逐层合并，这恰好对应从右往左扫描的栈式操作。表达式树的视角还能帮助判断一个表达式是否合法：整棵树的运算符数量一定比操作数数量少一。如果违反这个规律，说明表达式一定有问题。

6. 变体与扩展思路

6.1 把前缀表达式转成中缀

当递归或栈的方式很熟练之后，可以考虑这个扩展方向：让程序输出一个添加了括号的中缀表达式。做法是维护一个字符串栈，遇到操作数时压入数字字符串，遇到运算符时先从栈里弹出两个字符串，组合成(左表达式 op 右表达式)再压回。最后栈顶就是完整的中缀表达式。

6.2 后缀表达式求值

后缀表达式的求值是本题的直接镜像。把从右往左改成从左往右，操作数顺序改成“先弹出的是右操作数”，代码基本就出来了。我建议把两种求值都写一遍，对比着看，印象会非常深刻。

6.3 表达式合法性的完整校验

题目通常保证输入格式正确，但如果要写一个更严谨的解析器，就要在求值之前或求值过程中增加以下校验：

• 操作数数量与运算符数量是否满足操作数 = 运算符 + 1
• 栈是否在某一步出现下溢
• 最终栈中是否刚好剩下一个元素

这个校验代码量不大，但能有效防止各种崩溃或静默出错。实际项目里的表达式解析器往往比这复杂很多，要考虑变量名、函数调用、括号嵌套、优先级等，但基础原理始终是这部分内容。

7. 最后的总结与经验分享

这道题我从拿到题目到完全做对，中间走了不少弯路。第一版代码就是因为减法被搞反了，样例里恰好全是加法和乘法，直接提交被扣了分。后来学乖了，在本地多测了几个带减法和除法的表达式，才发现问题出在操作数顺序上。

分享两个实用的经验吧。

第一个经验：看到这种栈题目，先把规则写死在注释里，再写代码。比如我在写代码前，会在注释里写清楚“从右往左扫描，遇到运算符，先弹出的是左操作数，后弹出的是右操作数”。有了这行注释，代码里的first / second顺序就不容易搞混。

第二个经验：不管题目保证输入多合法，自己本地测试一定要覆盖边界输入。只测题目样例远远不够，至少要测一个单数字输入、一个负数操作数输入、一个连续除法的输入。这些极端情况能提前暴露代码中最脆弱的地方。

其实这道题从来不是为了考“会不会算前缀表达式”，而是要通过这道题，把“栈这种数据结构到底是怎么处理表达式的”彻底理解清楚。当你把前缀、后缀、中缀三种表达式都亲手实现过一遍之后，后面遇到任何表达式计算相关的题目都会从容很多。