聊到表达式求值很多人第一反应是逆波兰表达式后缀那种因为各教程里讲得最多。其实还有一个它的“镜像兄弟”——波兰表达式也叫前缀表达式运算符写在两个操作数前面比如* 3 4 2表示(34)*2。C实现波兰表达式求值核心代码可以很短一个栈加一趟从右往左的扫描基本就出来了。但真要写得严谨、耐用、能处理各种非法输入输入格式、负数解析、除零、操作数顺序这些边角问题一个都绕不开。这篇文章会把思路、设计决策、完整代码、测试用例、踩坑经验一次讲清楚。适合正在啃数据结构与算法的同学、准备面试的求职者以及想在项目里塞一个轻量表达式引擎的开发者。哪怕你C还只是入门水平照着文章把代码敲一遍也能得到一个可以实际用的前缀表达式求值器而不是那种只能跑通一个示例就完事的玩具。1. 先把求值逻辑想透为什么前缀表达式不用括号1.1 三种记法摆在一起看先看一张对比表写法例子结果特点中缀(34)*214人类习惯但需要优先级和括号前缀波兰* 3 4 214运算符在前天然嵌套后缀逆波兰3 4 2 *14运算符在后天然嵌套中缀是人类几百年的书写习惯却是计算机处理起来最麻烦的一种。34*2要是没有优先级规则从左往右硬算是(34)*214而大家期望的答案是 11。于是解析器必须维护一张运算符优先级表还要处理括号嵌套。前缀和后缀把“优先级信息”变成了“位置信息”运算符出现在它作用的两个操作数之前或之后谁是谁的操作数由位置直接决定括号自然就多余了。再补一个背景常识这种记法最早是一位波兰逻辑学家在形式逻辑研究中提出的所以叫波兰表达式。后来计算机领域发现它在表达式处理上有天然的简洁性Lisp 这类语言干脆把整个语法建立在“运算符在前”的结构上程序被当作一棵表达式树来处理省掉了大量中缀解析的麻烦。理解了这一点你就会明白这道题的价值远不止“会写个栈循环”。1.2 栈在这里到底充当什么角色让你手算* 3 4 2你大概是这么想的先看到最外层的*它要吃两个操作数第一个是 3 4算出 7第二个是 2最后7*214。这是“自顶向下”的思路对应递归下降解析适合人来理解。栈方案走的是“自底向上”从右往左扫描。为什么方向是反的因为前缀表达式里离运算符最远的位置放着最右边的叶子操作数。从右边开始读最先遇到的全是数字把它们暂存起来碰到运算符时它需要的两个操作数已经在栈里等着了。栈在这个场景中的作用我习惯称之为“延迟登记”。操作数先入栈不是没地方放而是为了等待它的运算符到来运算符一到从栈顶取走最近登记的两个数算完把结果放回栈继续等下一个运算符。因为是 LIFO后压栈的数字正好是最靠近当前运算符的右叶子匹配得严丝合缝。提示弹栈顺序必须对应“左操作数、右操作数”。以- 10 3为例从右往左读3 先入栈10 后入栈碰到-时先弹出 10 再弹出 310-3才是 7。顺序一旦反了答案就是 -7。这种 bug 在代码里极其隐蔽因为加法和乘法交换律会把问题掩盖掉。1.3 用一个完整例子走一遍流程拿* 4 2 3演示含义是(42)*3 18。核心过程如下读3是数字入栈栈为[3]。读2是数字入栈栈为[3, 2]。读4是数字入栈栈为[3, 2, 4]。读弹出 4 和 2计算426入栈栈为[3, 6]。读*弹出 6 和 3计算6*318入栈栈为[18]。扫描结束栈里只剩一个数 18就是结果。整个过程你完全不用管表达式嵌套了多深每步只碰栈顶两个数逻辑是纯机械的重复。这正是用循环而不是递归来实现的底气状态全部体现在栈里不会出现递归爆栈的隐患。2. 写代码前的设计决策输入、负数与除法语义2.1 输入怎么接收token 怎么切分最简单的落地方式是把表达式作为命令行参数传进来或者运行时用getline读一整行然后按空白符切分成 token。用std::istringstream配合就能干净地拿到 token 列表连续空格、Tab、换行都能自动跳过不需要自己写状态机。我也见过有人坚持逐字符扫描每读一个字符就去判断“当前是不是数字中间”“这个符号是运算符还是负号”如果不是在写内存极其受限的嵌入式代码我非常不推荐这么做。逐字符解析会把字符级的状态维护和表达式级的语法判断混在一起代码量翻倍不说还特别容易在边界情况上漏判。切成 token再用 token 序列去解析两个阶段关注点彻底解耦排查问题也更轻松。std::vectorstd::string tokenize(const std::string input) { std::istringstream iss(input); std::vectorstd::string tokens; std::string t; while (iss t) tokens.push_back(t); return tokens; }这段代码没有任何魔法唯一要提醒的是它把连续空白全吃掉了所以空串会得到一个空 vector这一点后面要单独处理。2.2 运算符和操作数的边界负数怎么办判断一个 token 是运算符还是数字最朴素的做法就是查集合bool is_operator(const std::string s) { return s.size() 1 std::string(-*/).find(s) ! std::string::npos; }注意这里必须加上size() 1的限制。否则--、-这种非法 token 会被误判成运算符后续逻辑直接跑偏。真正麻烦的是负数字面量比如 token-5它到底是“减号运算符加 5”还是“负五”这个歧义必须在设计阶段拍板。我的约定是只有单独成词的 - * /才算二元运算符其余 token 一律尝试按整数解析。于是-5会被解析成负数而- 5这种用空格分开的写法里-是运算符5是操作数。这个约定本身没有对错但必须在代码注释里写明让使用方知道规则避免出现“我觉得应该是这样”的误会。如果你的需求真的包含一元负号更稳妥的做法是引入显式的一元操作符比如neg 5表示 -5或者用~5这种不会和二义性冲突的记号。不要试图让-在同一个实现里既当二元运算符又当一元运算符那样表达式稍微复杂一点解析逻辑就会进入“看到减号先猜一猜”的泥潭。2.3 数据类型和整数除法的语义数值类型我用long long而不是int。教学示例用 int 当然能跑但表达式求值很容易出现乘法累计溢出的情况而 int 溢出在 C 里是未定义行为后果包括但不限于出现一个莫名其妙的负数。换成长整型至少把溢出门槛抬高了很多问题也更早暴露出来。除法语义也必须提前钉死。C 整数除法是向零截断7/2得 3-7/2得 -3。这既不是四舍五入也不是向下取整。如果产品需求希望得到 floor 行为就得自己写辅助函数把负数情况单独处理。另一个必须处理的点是除零直接抛带信息的异常远比返回一个魔数强调用方至少知道哪里出了问题。注意不同语言对整数除法的规则并不一致。表达式引擎如果将来要做跨语言移植除法语义一定要写成注释和测试用例钉死在代码里这是最容易在移植时悄悄变味的地方我在实际项目里吃过亏。3. 核心实现从右往左扫描的栈求值器3.1 主循环与操作符处理核心函数不长逻辑就三步从右往左遍历 token。遇到数字就压栈。遇到运算符就弹两个操作数按规则计算结果压回栈。弹栈顺序这里再强调一次先弹出来的是左操作数后弹出来的是右操作数运算结果按“左 OP 右”计算。代码里我会把这一步包装成独立的apply_op好处是运算符扩展、除零检测、后续加一元运算都集中在一个点上不会散落在主循环里。long long apply_op(long long left, long long right, const std::string op) { if (op ) return left right; if (op -) return left - right; if (op *) return left * right; if (op /) { if (right 0) { throw std::runtime_error(division by zero); } return left / right; } throw std::runtime_error(unknown operator: op); }有人会把apply_op写成开关分支或者查表映射也不是不行。但表达式求值只有四种基础运算if-else 链已经足够清晰还不用引入函数指针、lambda 映射这些对初学者不友好的结构。等运算符数量超过八个再考虑重构也不迟。3.2 防御性检查不让非法输入崩掉程序求值过程中最容易被忽略的是防御性检查。常见非法情形有四种运算符出现时栈里凑不齐两个操作数比如 1。整个表达式根本没有运算符比如1 2 3。token 既不是运算符也不是合法整数比如* 4 x 3里的x。栈底剩了不止一个数说明操作数比运算符多。这些情况如果你不检查程序会直接去访问空栈换来一个未定义行为或者干脆崩溃。在所有入口处都加上显式判断把错误以异常的形式抛出去是成本最低的防御。注意 C 的std::stack::top()对空栈调用是未定义行为所以弹栈前必须先看size()。3.3 时间复杂度与空间复杂度别小看这题这个算法的时间复杂度是 O(n)n 是 token 数量每个 token 恰好被处理一次入栈出栈都是常数次操作。空间复杂度是 O(d)d 是操作数栈的最大深度最坏情况下所有数字先入栈、运算符集中在末尾深度等于数字数量但通常在嵌套结构中深度只跟嵌套层数相关。面试的时候能把这个复杂度分析讲清楚是会比“我会用栈”高一个档次的展示。我见过不少人能把代码写对但被问到“最坏情况下栈有多深”就卡住。顺着这个问题还能引出“表达式树高度”的讨论这正好是下一节要讲的递归降级问题。4. 完整可编译代码与测试实录4.1 一份可以直接编译的 C17 实现把前面的决策全部落成代码大概是这个模样。运行环境是任意支持 C17 或以上的编译器平台无关#include iostream #include string #include vector #include stack #include sstream #include stdexcept #include charconv #include cstdint using std::string; using std::vector; bool is_operator(const string s) { return s.size() 1 string(-*/).find(s) ! string::npos; } long long apply_op(long long left, long long right, const string op) { if (op ) return left right; if (op -) return left - right; if (op *) return left * right; if (op /) { if (right 0) { throw std::runtime_error(division by zero); } return left / right; } throw std::runtime_error(unknown operator: op); } long long parse_number(const string s) { long long val 0; const char* begin s.data(); const char* end s.data() s.size(); auto [ptr, ec] std::from_chars(begin, end, val); if (ec ! std::errc() || ptr ! end) { throw std::runtime_error(invalid token: s); } return val; } long long eval_prefix(const vectorstring tokens) { std::stacklong long st; for (auto it tokens.rbegin(); it ! tokens.rend(); it) { const string tok *it; if (is_operator(tok)) { if (st.size() 2) { throw std::runtime_error(not enough operands for operator: tok); } long long left st.top(); st.pop(); long long right st.top(); st.pop(); st.push(apply_op(left, right, tok)); } else { st.push(parse_number(tok)); } } if (st.size() ! 1) { throw std::runtime_error(malformed expression: expected exactly one result); } return st.top(); } vectorstring tokenize(const string input) { std::istringstream iss(input); vectorstring tokens; string t; while (iss t) tokens.push_back(t); return tokens; } int main(int argc, char** argv) { string expr; if (argc 1) { for (int i 1; i argc; i) { expr argv[i]; if (i ! argc - 1) expr ; } } else { std::cout enter prefix expression:; std::getline(std::cin, expr); } try { auto tokens tokenize(expr); if (tokens.empty()) { throw std::runtime_error(empty expression); } long long result eval_prefix(tokens); std::cout result: result \n; } catch (const std::exception e) { std::cerr error: e.what() \n; return 1; } return 0; }两个容易被忽略的细节藏在代码里第一std::from_chars对12abc这种部分匹配会返回成功但ptr不在字符串末尾所以必须同时检查ptr ! end否则12abc会被悄悄当成 12。第二main里把命令行参数用空格重新拼接是为了让./a.out * 4 2 3和./a.out * 4 2 3两种调用方式都能工作不至于因为 shell 通配符或引号问题翻车。4.2 测试用例和运行结果我强烈建议写完代码后别只测一个例子把下面这组用例全部过一遍输入期望实际输出说明* 4 2 318result: 18基本嵌套- 10 37result: 7验证弹栈顺序 1 -5-4result: -4负数字面量/ 7 23result: 3整数除法向零截断/ 1 0异常error: division by zero除零检测 1异常error: not enough operands for operator: 操作数不足1 2 3异常error: malformed expression: expected exactly one result操作数过多* 4 x 3异常error: invalid token: x非法 token空串异常error: empty expression空输入其中 1 -5这个用例特别值得加进回归测试。它同时考验负数解析和减法/加法混合时的边界很多初版实现都会在“把 -5 当成减号和 5”这个问题上翻车。除零和非法 token 的用例也别删它们是你以后重构时的安全网。4.3 代码走读为什么这样组织整个代码被我拆成了 tokenize、parse_number、apply_op、eval_prefix 四个函数外加 main 做胶水。这么拆分不是摆架子而是每层各管一件事tokenize 不管语法apply_op 不管栈结构eval_prefix 不管字符串解析。将来要加一元运算符只需在 apply_op 扩分支并在 eval_prefix 里增加“某个运算符需要几个操作数”的元信息要支持浮点数只需改 parse_number 和 apply_op 的返回值类型要做成库只需让 eval_prefix 抛异常而不是往 stdout 打日志。这种组织方式还有一个隐藏好处每层都可以单独写单元测试。我一个人做项目时也坚持给 eval_prefix 挂测试用例因为表达式求值这玩意儿改一处错一片的现象太常见了没有自动测试兜底你根本不敢动代码。5. 常见问题排查与进阶扩展5.1 常见问题速查表把这段代码从写到调试过程中最容易踩的坑整理如下现象可能原因解决办法减法和除法结果错误弹栈顺序搞反检查先弹出的是左操作数按“左 OP 右”计算加法和乘法偶尔对混合时错操作数顺序靠运气某些样例恰好通过写- 10 3、/ 8 2之类的非对称用例-5解析失败或行为诡异token 切分把负号和数字连在一起解析逻辑没约定按“只有独立成词的符号才算运算符”统一约定传入12abc被当成 12用了stoll或者from_chars没检查 ptr检查是否消费了整个 token空表达式导致段错误没检查 tokens.empty()main 入口显式报错除零返回意外值没在 apply_op 里处理除零抛异常别返回魔法数结果溢出成负数用了 int改用 long long并考虑溢出检测这些坑没有一个是“算法不会写”层面的全是工程细节。我见过不少基本功不错的同学算法思路完全对最后挂在-5的解析上很可惜。5.2 后缀表达式求值一个镜像实现波兰表达式和后缀表达式就像一面镜子的两侧。后缀表达式3 4 2 *从左往右扫描遇到数字入栈遇到运算符弹两个数计算。两者的差别集中在弹栈顺序上后缀场景下先弹出的是右操作数后弹出的是左操作数假设还是3 4 弹出 4 和 3要算34而不是43所以后缀是“second OP first”和前缀刚好相反。把两套代码放在一起对比着看你会觉得“表达式求值”这关彻底过了。遇到任何一个求值问题先看清楚运算符出现在操作数的哪一边再决定扫描方向弹栈顺序自然就对了。这套思维比背任何模板都有用。5.3 再进一步递归解析与构建语法树显式栈方案适合“只要求结果”的场景。另一条路是递归解析从左往右读遇到运算符就递归解析左操作数和右操作数代码更贴合表达式的递归定义long long eval_rec(const vectorstring tokens, size_t pos) { const string tok tokens[pos]; if (is_operator(tok)) { long long left eval_rec(tokens, pos); long long right eval_rec(tokens, pos); return apply_op(left, right, tok); } return parse_number(tok); }这段代码直观、优雅但要注意递归深度等于表达式树的深度。遇到极端嵌套比如几百层括号叠出来的表达式显式栈方案完全不受影响递归方案却很可能爆栈。所以我的实用建议是演示和讲清楚原理时用递归产品代码尽量用显式栈。如果再往前迈一步不直接计算结果而是把弹出的操作数和运算符构造成语法树节点你就拥有了一个真正的解析器内核。语法树比求值结果信息量大得多可以做常量折叠、公共子表达式提取、重写优化这些后续动作。很多脚本语言解释器的算术引擎起步形态就是这么一棵小小的表达式树。最后分享一点我的使用体会这个求值器我从入行开始前前后后写过好几版现在遇到“写一个简单表达式引擎”的需求还是会用显式栈加从右往左扫描这个骨架。它已经是刻进条件反射里的方案了因为在绝大多数场景下它代码量最小、行为最可预测、也最容易测试。最让我记忆深刻的一次翻车恰恰就是我反复提醒的弹栈顺序当时写后缀表达式留下了“先弹右操作数”的肌肉记忆改成前缀后没有同步调整导致减法表达式的结果大面积飘负号还一度以为是解析器坏了。最后是拿非对称用例一行行打日志才定位到问题。如果你也想彻底记住这个点不妨自己在纸上把- 10 3的前缀和后缀各算一遍再对照代码里的注释印象会深得多。动手跑通这套代码之后你还可以顺手做两个扩展给apply_op加%取模运算以及把整数类型替换成浮点数。这两步做完你对“表达式求值”这个知识点的掌握就已经超过大多数只看过理论的人了。