用C++实现计算器：逆波兰表达式与调度场算法完整指南

第一次用C++写计算器时，我做了一个只支持两个数加减乘除的小程序，当时觉得挺得意。直到输入1+2*3，程序干净利落地返回了9，我才意识到问题根本不在“算”，而在“顺序”。后来一位做过编译器的朋友点了一句：你把中缀表达式转成逆波兰表达式，也就是后缀表达式，再交给程序算，事情就顺了。

这篇东西就是围绕这条路展开的。我会从“为什么中缀对机器不友好”开始，把逆波兰表达式的转换算法、词法分析、求值函数，以及一元负号、幂运算、错误恢复这些容易翻车的地方都过一遍。适合正在学C++数据结构、想动手写一个真正能处理括号和优先级的计算器的读者，也适合准备啃编译原理、想先摸摸“表达式解析”的门道的朋友。看完你可以直接照着我这个思路实现一版，代码不复杂，但每一步都有值得琢磨的地方。

1. 先想清楚：为什么中缀表达式对机器不友好

人类写1+2*3，眼睛扫一眼就知道先算乘法，因为“乘法优先级高于加法”这种规则已经刻在脑回路里了。但计算机从左往右读这个字符串，它看到的只是字符序列，如果不额外处理优先级，按扫描顺序计算就会得到9。括号更麻烦，(1+2)*3和1+2*3字符只差一对括号，结果却完全不同。

解决办法有很多种，其中一种最直观的思路就是：不要让你写的解析代码去“理解”优先级规则，而是先把表达式改写成一种没有歧义的格式，再计算。后缀表达式，也叫逆波兰表达式，就是这种格式。

什么叫后缀表达式？运算符跟在操作数后面。1+2*3写成后缀是1 2 3 * +，(1+2)*3写成后缀是1 2 + 3 *。后缀表达式有个非常漂亮的性质：从左到右扫描，碰到数字就压栈，碰到运算符就弹出顶部的两个数字做运算，再把结果压回去。整个过程根本不需要知道“乘法优先于加法”，因为转换阶段已经把先后顺序安排好了。

正因为这样，计算器的核心难点并不在求值，而在“中缀转后缀”。这个转换做得对，求值反而是最轻松的一段代码。我见过很多同学上来就写一个巨大的switch循环，试图在单个for里同时完成“看字符、查优先级、做运算”，最后被括号和负号折磨得怀疑人生。实际上分两步走——先转后缀，再算后缀——逻辑会清晰得多。

2. 核心转换算法：优先级表与调度场规则

把一个中缀表达式转换成后缀表达式，最经典的做法叫调度场算法。这个名字源自火车调度站，想象一个轨道岔口，左边的火车皮（操作数）直接开向输出轨道，而需要“等待连接”的运算符先进侧线缓冲区停一下，时机合适再开出来。这个“侧线缓冲区”在代码里就是一个运算符栈。

2.1 为什么需要一个显式的优先级表

转换过程里，每次遇到一个运算符，都要判断它该直接输出，还是该先把栈里等着的某些运算符赶出来。这个判断依赖优先级表。我先把常见运算符的优先级和结合性列出来，后面所有逻辑都围绕这张表展开。

结合性这个概念很多人一开始不重视，实际上它直接影响弹栈规则。加减乘除都是左结合，意思是1-2+3应当按(1-2)+3计算，而不是1-(2+3)。幂运算习惯上是右结合，2^3^2应当按2^(3^2)理解。一元负号优先级最高，而且也是右结合，这会在第5节详细展开。

2.2 四类Token的处理规则

输入经过词法分析之后，会得到一个个Token，每个Token只会是操作数、运算符、左括号、右括号四种类型之一。转换主循环针对这四种类型分别处理：

• 操作数：直接追加到输出序列。
• 左括号：压入运算符栈，它像一个屏障，把括号内的运算符和括号外的隔开。
• 右括号：从运算符栈不断弹出运算符到输出序列，直到遇到栈顶的左括号为止，最后把这个左括号弹出并丢弃。
• 运算符：先看栈顶。只要栈顶是运算符，并且栈顶运算符的优先级不低于当前运算符——具体还要考虑结合性——就把栈顶弹出到输出序列。重复这个动作直到不满足条件，然后把当前运算符压入栈。

关于“不低于”的细节，很多人在这里翻车。对于左结合运算符，遇到相同优先级也要弹出。举个例子，1-2+3，扫描到+时，栈顶是-，两者优先级相同。如果此时不把-弹出去，+直接入栈，后缀会变成1 2 3 + -，求值得到-4，而正确结果应该是2。对左结合运算符来说，相同优先级必须先弹出，才能保证从左到右计算。

2.3 完整走查：2*(3+4)-5

光讲规则太抽象，我用一个具体例子把整个流程走一遍。输入是2*(3+4)-5，我把每一步的Token、动作、输出序列和运算符栈的变化列成下面这张表。

最终后缀表达式是2 3 4 + * 5 -。求值过程：3+4=7，2*7=14，14-5=9。整个转换过程里，左括号起到了“暂停弹栈”的作用，右括号则负责把括号内积累的运算符一次性清理出来。这也是调度场算法的精髓——用栈的先进后出模拟“优先级高的运算符先被处理，但必须等右操作数就位”。

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::vector<Token> tokenize(const std::string& expr) { std::vector<Token> tokens; size_t i = 0; while (i < expr.size()) { if (std::isspace(static_cast<unsigned char>(expr[i]))) { ++i; continue; } if (std::isdigit(static_cast<unsigned char>(expr[i])) || expr[i] == '.') { size_t start = i; bool hasDot = false; while (i < expr.size() && (std::isdigit(static_cast<unsigned 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::vector<Token>，返回一个新的std::vector<Token>作为后缀表达式。我用两个vector：output存结果序列，opStack当运算符栈用。

std::vector<Token> infixToRpn(const std::vector<Token>& tokens) { std::vector<Token> output; std::vector<Token> 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::vector<double>当栈，遍历后缀Token序列：

double evalRpn(const std::vector<Token>& rpn) { std::vector<double> 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，此时left=10, right=2还好；但如果你把第一次弹出的当作left，写成right - left，就会得到2 - 10 = -8。所以在求值函数里，务必先用变量right接住第一个弹出的数，再用left接住第二个弹出的数。减法和除法尤其敏感，一旦顺序颠倒，结果就会全错。

4.3 调试技巧：打印每一步的栈状态

我在实现这个计算器的时候，最头疼的不是“想不明白算法”，而是“明明逻辑看起来对，结果就是不对”。后来我养成了一个习惯：在转换循环里加上短暂的日志输出，每处理一个Token，就打印当前输出序列和运算符栈的全部内容。这样一眼就能看出是哪个环节出了问题。

void debugPrint(const std::vector<Token>& output, const std::vector<Token>& 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*(3+4)-5这类式子单步跟踪一遍之后，你对调度场算法的理解会比看十遍文字描述都深刻。在正式版本里可以加一个开关，或者直接不调用调试函数，但在调试期它帮了大忙。

5. 扩展场景：一元负号、幂运算、错误处理三件套

基础版本跑通之后，大多数人的下一步是想让计算器更像样一点。比如输入-3+2要结果正确，输入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标记，求值阶段只需要弹出一个操作数取负即可。这样-3+2的后缀是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^2=9，再算2^9=512，结果正确。

5.3 错误处理：别让程序滋滋地崩溃

这个计算器在错误处理上遵循一个原则：发现问题就在原地抛异常，主函数外层统一捕获，提示给用户。如果返回错误码，每一层调用都要检查一次，很容易漏，而且错误信息会丢失。

常见的错误场景和对应处理方式：

测试用例也建议按这个表来准备，尤其是边界用例。我一般会跑这几条：1+2*3应该得到7，(1+2)*3应该得到9，2*(3+4)-5应该得到9，-3+2应该得到-1，2^3^2应该得到512，1/0应该抛出除零错误。跑完这些，基本可以说明转换和求值两个阶段的核心逻辑都是对的。

6. 我的实现心路历程与后续优化建议

这个计算器项目我前后写过三版。第一版用递归下降解析，代码很长，每个优先级写一个函数，虽然能处理负号和幂，但每次加功能都要动结构，维护起来累。第二版改用调度场算法，把转换和求值彻底分开，我突然发现整个项目的核心其实就是一张优先级表和两个循环。第三版重构词法分析，引入Token结构，程序才真正变成“词法分析—语法转换—求值”三层结构，每一层都可以独立测试。

如果让我给刚开始动手的人一个建议，那就是“先把表达式切干净，再用两层栈”。不要试图在一个循环里一边做词法一边求值，那样负号、括号、多位数会给你上一课。词法分析阶段把字符串变成Token序列，调度场算法把Token序列变成后缀Token序列，求值函数把后缀序列变成一个数。每一步的输出都可以打印、可以断言，问题出在哪一层，一目了然。

等到基础版本稳定了，你可以继续琢磨几个方向。一是支持科学计数法，比如1e3这种写法，词法分析里多加一种数字格式判断就行。二是支持函数，比如sin(0.5)，本质上是把函数名当作一个特殊的运算符，优先级设为极高，转换阶段直接压栈，遇到右括号时再弹出来，求值阶段多一个分支而已。三是支持变量赋值，比如让用户先定义x=3，然后在表达式里使用x，这需要一张符号表。四是支持表达式合法性检查，在解析阶段尽早给出更友好的错误提示，而不是等到求值阶段才抛异常。

我自己的体会是，调度场算法带来的最大价值并不只是“能写一个计算器”，而是让你第一次真正理解了“为什么需要栈”以及“怎么用栈处理嵌套结构”。去括号的嵌套、运算符的等待、右操作数的就位，这些问题背后都有一个LIFO的影子。后来我再看任何需要处理嵌套语法的东西，比如JSON解析、模板渲染、表达式引擎，都会下意识地想：这里能不能用栈，能不能用状态机。

当然，调度场算法也不是万能的。如果表达式语法再复杂一点，比如出现三元运算符、类型转换、作用域这些，递归下降parser或者一个成熟的parser组合子库会更顺手。但从“搞懂原理”这个目标来说，计算器项目+逆波兰表达式这条路，几乎是性价比最高的一条路径。你可以不依赖任何第三方库，用标准库的几个容器和几个基本函数，就能把一个看起来简单的计算器做成一个结构清楚的小系统。

最后再分享一个小技巧：给Token结构加一个text字段，保留原始的字符串内容。很多调试问题就是靠它解决的。比如你打印输出序列时看到neg才发现一元负号被处理成了普通减号；看到-才发现减号被错误地归类。这种“看得见中间过程”的小习惯，比任何调试器都管用。