第一次用C写计算器时我做了一个只支持两个数加减乘除的小程序当时觉得挺得意。直到输入12*3程序干净利落地返回了9我才意识到问题根本不在“算”而在“顺序”。后来一位做过编译器的朋友点了一句你把中缀表达式转成逆波兰表达式也就是后缀表达式再交给程序算事情就顺了。这篇东西就是围绕这条路展开的。我会从“为什么中缀对机器不友好”开始把逆波兰表达式的转换算法、词法分析、求值函数以及一元负号、幂运算、错误恢复这些容易翻车的地方都过一遍。适合正在学C数据结构、想动手写一个真正能处理括号和优先级的计算器的读者也适合准备啃编译原理、想先摸摸“表达式解析”的门道的朋友。看完你可以直接照着我这个思路实现一版代码不复杂但每一步都有值得琢磨的地方。1. 先想清楚为什么中缀表达式对机器不友好人类写12*3眼睛扫一眼就知道先算乘法因为“乘法优先级高于加法”这种规则已经刻在脑回路里了。但计算机从左往右读这个字符串它看到的只是字符序列如果不额外处理优先级按扫描顺序计算就会得到9。括号更麻烦(12)*3和12*3字符只差一对括号结果却完全不同。解决办法有很多种其中一种最直观的思路就是不要让你写的解析代码去“理解”优先级规则而是先把表达式改写成一种没有歧义的格式再计算。后缀表达式也叫逆波兰表达式就是这种格式。什么叫后缀表达式运算符跟在操作数后面。12*3写成后缀是1 2 3 * (12)*3写成后缀是1 2 3 *。后缀表达式有个非常漂亮的性质从左到右扫描碰到数字就压栈碰到运算符就弹出顶部的两个数字做运算再把结果压回去。整个过程根本不需要知道“乘法优先于加法”因为转换阶段已经把先后顺序安排好了。正因为这样计算器的核心难点并不在求值而在“中缀转后缀”。这个转换做得对求值反而是最轻松的一段代码。我见过很多同学上来就写一个巨大的switch循环试图在单个for里同时完成“看字符、查优先级、做运算”最后被括号和负号折磨得怀疑人生。实际上分两步走——先转后缀再算后缀——逻辑会清晰得多。2. 核心转换算法优先级表与调度场规则把一个中缀表达式转换成后缀表达式最经典的做法叫调度场算法。这个名字源自火车调度站想象一个轨道岔口左边的火车皮操作数直接开向输出轨道而需要“等待连接”的运算符先进侧线缓冲区停一下时机合适再开出来。这个“侧线缓冲区”在代码里就是一个运算符栈。2.1 为什么需要一个显式的优先级表转换过程里每次遇到一个运算符都要判断它该直接输出还是该先把栈里等着的某些运算符赶出来。这个判断依赖优先级表。我先把常见运算符的优先级和结合性列出来后面所有逻辑都围绕这张表展开。运算符含义优先级结合性-加减1左结合*/乘除2左结合^幂运算3右结合neg一元负号4右结合结合性这个概念很多人一开始不重视实际上它直接影响弹栈规则。加减乘除都是左结合意思是1-23应当按(1-2)3计算而不是1-(23)。幂运算习惯上是右结合2^3^2应当按2^(3^2)理解。一元负号优先级最高而且也是右结合这会在第5节详细展开。2.2 四类Token的处理规则输入经过词法分析之后会得到一个个Token每个Token只会是操作数、运算符、左括号、右括号四种类型之一。转换主循环针对这四种类型分别处理操作数直接追加到输出序列。左括号压入运算符栈它像一个屏障把括号内的运算符和括号外的隔开。右括号从运算符栈不断弹出运算符到输出序列直到遇到栈顶的左括号为止最后把这个左括号弹出并丢弃。运算符先看栈顶。只要栈顶是运算符并且栈顶运算符的优先级不低于当前运算符——具体还要考虑结合性——就把栈顶弹出到输出序列。重复这个动作直到不满足条件然后把当前运算符压入栈。关于“不低于”的细节很多人在这里翻车。对于左结合运算符遇到相同优先级也要弹出。举个例子1-23扫描到时栈顶是-两者优先级相同。如果此时不把-弹出去直接入栈后缀会变成1 2 3 -求值得到-4而正确结果应该是2。对左结合运算符来说相同优先级必须先弹出才能保证从左到右计算。2.3 完整走查2*(34)-5光讲规则太抽象我用一个具体例子把整个流程走一遍。输入是2*(34)-5我把每一步的Token、动作、输出序列和运算符栈的变化列成下面这张表。步骤当前Token动作输出序列运算符栈状态12输出2空2*栈空直接入栈2*3(入栈2* (43输出2 3* (5栈顶是(不弹出入栈2 3* ( 64输出2 3 4* ( 7)弹出到输出再弹出(丢弃2 3 4 *8-栈顶*优先级2高于-的1弹出*-入栈2 3 4 *-95输出2 3 4 * 5-10结束弹出栈顶-2 3 4 * 5 -空最终后缀表达式是2 3 4 * 5 -。求值过程3472*71414-59。整个转换过程里左括号起到了“暂停弹栈”的作用右括号则负责把括号内积累的运算符一次性清理出来。这也是调度场算法的精髓——用栈的先进后出模拟“优先级高的运算符先被处理但必须等右操作数就位”。3. 词法分析把字符串切成Token而不是一个字符很多新手一开始直接从字符层面处理表达式然后发现到处都是坑123会被拆成三个字符3.14的数字和点会被拆散-到底是负号还是减号也说不清楚。词法分析这个步骤就是先把字符串整体拆成一串有意义的Token之后再谈转换。这个“先切词、再解析”的分层思路不只在计算器里有用几乎所有文本解析场景都用得上。3.1 Token结构与类型定义在C里我用一个enum加一个struct来定义Token。为了后面调试方便struct里同时保存原始文本和解析后的数值。enum class TokenType { Number, // 操作数比如 2、3.14 Operator, // 运算符包括 - * / ^ LeftParen, // 左括号 RightParen, // 右括号 UnaryMinus // 一元负号后面会单独处理 }; struct Token { TokenType type; std::string text; // 原始的字符内容用于调试 double numValue 0.0; // 如果是Number类型这里存数值 };有的实现会把Token直接定义成std::string靠字符串内容去判断类型。对于这个小项目来说也不是不能用但显式类型能让代码的可读性和可维护性都好很多。后面写转换算法时不用到处比较字符串内容直接看type就行。3.2 解析循环的主体逻辑词法分析的主循环不复杂按顺序扫描字符串每步跳过空白然后根据当前字符决定生成什么Token。std::vectorToken tokenize(const std::string expr) { std::vectorToken tokens; size_t i 0; while (i expr.size()) { if (std::isspace(static_castunsigned char(expr[i]))) { i; continue; } if (std::isdigit(static_castunsigned char(expr[i])) || expr[i] .) { size_t start i; bool hasDot false; while (i expr.size() (std::isdigit(static_castunsigned char(expr[i])) || expr[i] .)) { if (expr[i] .) { if (hasDot) { throw std::runtime_error(数字格式错误出现多个小数点); } hasDot true; } i; } std::string numText expr.substr(start, i - start); Token token; token.type TokenType::Number; token.text numText; token.numValue std::stod(numText); tokens.push_back(token); continue; } if (expr[i] () { tokens.push_back({TokenType::LeftParen, (, 0.0}); i; continue; } if (expr[i] )) { tokens.push_back({TokenType::RightParen, ), 0.0}); i; continue; } if (expr[i] || expr[i] - || expr[i] * || expr[i] / || expr[i] ^) { tokens.push_back({TokenType::Operator, std::string(1, expr[i]), 0.0}); i; continue; } throw std::runtime_error(std::string(无法识别的字符: ) expr[i]); } return tokens; }这段代码有几个精心处理的边界。第一支持小数点开头的数字比如.5会被解析成0.5这在stod里是合法的。第二连续判断什么时候停止读取数字必须是既非数字也非小数点否则1.2.3这种错误输入会在第一个循环里被整个吃进去到第二个小数点时抛异常。第三所有无法识别的字符比如%或者英文字母统一抛异常避免程序带着错误状态继续跑。3.3 运算符的两副面孔负号与减号词法分析阶段还有一个必须解决的歧义字符-既是二元减号也可能是一元负号。判断依据是它的位置。如果-是表达式的第一个字符或者它紧跟在左括号后面比如(-3)或者它的前一个Token是运算符比如2*-3那么它应该被识别为一元负号而不是普通减号。我在实际操作中的做法是在词法分析循环里额外记录上一个Token的类型如果发现-或且满足“前面是开头、左括号、或运算符”这三个条件之一就生成一个特殊类型UnaryMinus或UnaryPlus。这样转换阶段就能明确区分“取负”和“减法”。这个细节如果不处理后面积分、嵌套括号的逻辑就会混乱。4. 从转换到求值C实现与两个易踩的坑有了Token序列下一步就是实现调度场转换和RPN求值。我习惯用std::vector来模拟栈而不是直接用std::stack原因只有一个调试方便。std::vector可以直接打印中间的栈内容而std::stack只能被蒙在鼓里。4.1 中缀转后缀的核心函数转换函数接收前面词法分析得到的std::vectorToken返回一个新的std::vectorToken作为后缀表达式。我用两个vectoroutput存结果序列opStack当运算符栈用。std::vectorToken infixToRpn(const std::vectorToken tokens) { std::vectorToken output; std::vectorToken opStack; auto precedence [](const Token tok) - int { if (tok.type TokenType::UnaryMinus) return 4; if (tok.type TokenType::Operator) { if (tok.text || tok.text -) return 1; if (tok.text * || tok.text /) return 2; if (tok.text ^) return 3; } return 0; }; auto isLeftAssoc [](const Token tok) - bool { if (tok.type TokenType::Operator) { return tok.text || tok.text - || tok.text * || tok.text /; } if (tok.type TokenType::UnaryMinus) return false; return true; }; for (const auto tok : tokens) { if (tok.type TokenType::Number) { output.push_back(tok); } else if (tok.type TokenType::LeftParen) { opStack.push_back(tok); } else if (tok.type TokenType::RightParen) { bool foundLeftParen false; while (!opStack.empty()) { Token top opStack.back(); opStack.pop_back(); if (top.type TokenType::LeftParen) { foundLeftParen true; break; } output.push_back(top); } if (!foundLeftParen) { throw std::runtime_error(括号不匹配多余的右括号); } } else { // 运算符或一元负号 int currPrec precedence(tok); while (!opStack.empty()) { Token top opStack.back(); if (top.type TokenType::LeftParen) break; int topPrec precedence(top); if (topPrec currPrec || (topPrec currPrec isLeftAssoc(tok))) { output.push_back(top); opStack.pop_back(); } else { break; } } opStack.push_back(tok); } } while (!opStack.empty()) { Token top opStack.back(); if (top.type TokenType::LeftParen) { throw std::runtime_error(括号不匹配多余的左括号); } output.push_back(top); opStack.pop_back(); } return output; }注意这里的关键判断当当前运算符tok是左结合时相同优先级需要弹出栈顶当tok是右结合时相同优先级不弹出。这个细节体现在isLeftAssoc(tok)这个条件上如果你反过来写幂运算就会全部变成左结合。4.2 后缀求值弹出顺序最容易搞反求值函数要简单得多一个std::vectordouble当栈遍历后缀Token序列double evalRpn(const std::vectorToken rpn) { std::vectordouble stack; for (const auto tok : rpn) { if (tok.type TokenType::Number) { stack.push_back(tok.numValue); } else if (tok.type TokenType::UnaryMinus) { if (stack.empty()) throw std::runtime_error(表达式不合法操作数不足); double operand stack.back(); stack.pop_back(); stack.push_back(-operand); } else if (tok.type TokenType::Operator) { if (stack.size() 2) throw std::runtime_error(表达式不合法操作数不足); double right stack.back(); stack.pop_back(); double left stack.back(); stack.pop_back(); double result 0.0; if (tok.text ) result left right; else if (tok.text -) result left - right; else if (tok.text *) result left * right; else if (tok.text /) { if (right 0.0) throw std::runtime_error(除零错误); result left / right; } else if (tok.text ^) result std::pow(left, right); stack.push_back(result); } } if (stack.size() ! 1) throw std::runtime_error(表达式不合法操作数栈错误); return stack.back(); }这里有一个我当年踩过的坑值得单独说出来弹栈的顺序。后缀表达式10 2 -正确结果是8我需要弹出2作为右操作数弹出10作为左操作数然后做10 - 2。如果先弹出来的是10再弹出来2然后顺手写成left - right此时left10, right2还好但如果你把第一次弹出的当作left写成right - left就会得到2 - 10 -8。所以在求值函数里务必先用变量right接住第一个弹出的数再用left接住第二个弹出的数。减法和除法尤其敏感一旦顺序颠倒结果就会全错。4.3 调试技巧打印每一步的栈状态我在实现这个计算器的时候最头疼的不是“想不明白算法”而是“明明逻辑看起来对结果就是不对”。后来我养成了一个习惯在转换循环里加上短暂的日志输出每处理一个Token就打印当前输出序列和运算符栈的全部内容。这样一眼就能看出是哪个环节出了问题。void debugPrint(const std::vectorToken output, const std::vectorToken opStack, const Token current) { std::cout 当前Token: current.text \n; std::cout 输出序列: ; for (const auto t : output) std::cout t.text ; std::cout \n运算符栈: ; for (const auto t : opStack) std::cout t.text ; std::cout \n---\n; }别小看这个打印函数。2*(34)-5这类式子单步跟踪一遍之后你对调度场算法的理解会比看十遍文字描述都深刻。在正式版本里可以加一个开关或者直接不调用调试函数但在调试期它帮了大忙。5. 扩展场景一元负号、幂运算、错误处理三件套基础版本跑通之后大多数人的下一步是想让计算器更像样一点。比如输入-32要结果正确输入2^3^2要按右结合算输入1/0不能崩溃而要给提示。这三件事是目前被问得最多的扩展点。5.1 一元负号不是“减号前面补零”一个偷懒的办法是把-3改写成0-3这确实能算对简单情况但遇到2^-3或者(-3)^2就没那么优雅了。更干净的做法是词法分析阶段直接识别一元负号生成单独的UnaryMinus类型Token。词法判断条件我再说仔细一点。一个-如果出现在以下位置就应当视为一元负号表达式最开头前一个Token是运算符前一个Token是左括号。反之如果前一个Token是数字或右括号那它是二元减号。例如2-3中-前是数字2它是减号2*(-3)中-前是左括号它是一元负号。一元负号的转换逻辑不需要很复杂。它优先级最高所以把它压栈后后面遇到任何普通运算符都不会把它弹出去。在RPN输出序列里它表现为一个紧跟操作数之后的neg标记求值阶段只需要弹出一个操作数取负即可。这样-32的后缀是3 neg 2 计算时先取负得-3再加2得到-1。5.2 幂运算的右结合性相同优先级不弹栈基础版本的优先级表只有加减乘除时全部是左结合弹栈规则简单粗暴只要栈顶优先级不低于当前运算符就弹。但加入幂运算这个规则必须改。2^3^2数学上约定为2^(3^2)也就是512而不是(2^3)^2的64。如果沿用“相同优先级也弹栈”的老规则扫描到第二个^时会把第一个^从栈里弹出来后缀变成2 3 ^ 2 ^计算结果就是64不符合约定。修正方法就是我在4.1代码里已经展示过的弹栈时先看结合性。对于左结合运算符相同优先级要弹出对于右结合运算符相同优先级不弹出只把优先级更高的情况弹出。也就是说当前运算符是^时栈顶即使也是^也不要弹让它一并压栈。最终后缀变成2 3 2 ^ ^求值时先算3^29再算2^9512结果正确。5.3 错误处理别让程序滋滋地崩溃这个计算器在错误处理上遵循一个原则发现问题就在原地抛异常主函数外层统一捕获提示给用户。如果返回错误码每一层调用都要检查一次很容易漏而且错误信息会丢失。常见的错误场景和对应处理方式场景现象处理方案输入空字符串词法分析得到空Token序列主函数里提前判断并提示“表达式为空”括号不匹配右括号多余或结束时栈里还有左括号转换阶段检查右括号匹配结束时检查左括号残留连续两个运算符比如1*2求值阶段stack.size() 2时必然触发操作数不足异常除数为零比如1/0求值阶段检查right 0.0并抛“除零错误”数字格式错误比如1.2.3词法分析阶段检测连续小数点并抛异常测试用例也建议按这个表来准备尤其是边界用例。我一般会跑这几条12*3应该得到7(12)*3应该得到92*(34)-5应该得到9-32应该得到-12^3^2应该得到5121/0应该抛出除零错误。跑完这些基本可以说明转换和求值两个阶段的核心逻辑都是对的。6. 我的实现心路历程与后续优化建议这个计算器项目我前后写过三版。第一版用递归下降解析代码很长每个优先级写一个函数虽然能处理负号和幂但每次加功能都要动结构维护起来累。第二版改用调度场算法把转换和求值彻底分开我突然发现整个项目的核心其实就是一张优先级表和两个循环。第三版重构词法分析引入Token结构程序才真正变成“词法分析—语法转换—求值”三层结构每一层都可以独立测试。如果让我给刚开始动手的人一个建议那就是“先把表达式切干净再用两层栈”。不要试图在一个循环里一边做词法一边求值那样负号、括号、多位数会给你上一课。词法分析阶段把字符串变成Token序列调度场算法把Token序列变成后缀Token序列求值函数把后缀序列变成一个数。每一步的输出都可以打印、可以断言问题出在哪一层一目了然。等到基础版本稳定了你可以继续琢磨几个方向。一是支持科学计数法比如1e3这种写法词法分析里多加一种数字格式判断就行。二是支持函数比如sin(0.5)本质上是把函数名当作一个特殊的运算符优先级设为极高转换阶段直接压栈遇到右括号时再弹出来求值阶段多一个分支而已。三是支持变量赋值比如让用户先定义x3然后在表达式里使用x这需要一张符号表。四是支持表达式合法性检查在解析阶段尽早给出更友好的错误提示而不是等到求值阶段才抛异常。我自己的体会是调度场算法带来的最大价值并不只是“能写一个计算器”而是让你第一次真正理解了“为什么需要栈”以及“怎么用栈处理嵌套结构”。去括号的嵌套、运算符的等待、右操作数的就位这些问题背后都有一个LIFO的影子。后来我再看任何需要处理嵌套语法的东西比如JSON解析、模板渲染、表达式引擎都会下意识地想这里能不能用栈能不能用状态机。当然调度场算法也不是万能的。如果表达式语法再复杂一点比如出现三元运算符、类型转换、作用域这些递归下降parser或者一个成熟的parser组合子库会更顺手。但从“搞懂原理”这个目标来说计算器项目逆波兰表达式这条路几乎是性价比最高的一条路径。你可以不依赖任何第三方库用标准库的几个容器和几个基本函数就能把一个看起来简单的计算器做成一个结构清楚的小系统。最后再分享一个小技巧给Token结构加一个text字段保留原始的字符串内容。很多调试问题就是靠它解决的。比如你打印输出序列时看到neg才发现一元负号被处理成了普通减号看到-才发现减号被错误地归类。这种“看得见中间过程”的小习惯比任何调试器都管用。
