上机40天：用栈实现带负号的四则运算表达式求值

今天打开编辑器的时候，时间是晚上九点四十。屏幕上还留着昨天没调完的测试用例，光标一闪一闪地停在那个报错的括号前面。我忽然意识到，这是连续第40天坐在电脑前做上机练习了。

第40天是个很微妙的时间节点。热情早就退了，肌肉记忆还没完全长成，每天到点手会自己摸向键盘，但心里偶尔也会飘过“今天要不歇一天”的念头。我一般会任由这个念头存在，然后继续敲今天的题目。因为我发现，上机练习这事，真正难的不是某一天的题目多难，而是你愿不愿意在第40天、第80天、第120天，打开一个空白文件，从头开始。

今天练的这道题很有意思，它把字符串处理、栈、运算符优先级和边界条件全揉在了一起。一道题能牵出这么多基础知识点，作为第40天的练习再合适不过了。

1. 今天的题目：带负号的四则运算表达式求值

1.1 题面到底要求什么

我是在一个在线判题系统上碰到这道题的。原题很长，但核心要求就一条：给定一个只包含数字、加减乘除、括号和空格的字符串表达式，实现一个计算器，求出结果。表达式里可以出现负数，整数除法向零取整，输入长度不超过100个字符。

题目给了几个示例：

• "3+2*2"输出7
• " 3/2 "输出1（除法向零取整）
• " -3+5 "输出2
• "2*(-3)"输出-6

我多看了几遍最后两个示例，心里基本有数了：这题真正想卡人的地方，不是四则运算本身，而是负号的识别。负号到底是减号，还是一元取负运算符，这是整道题最核心的分水岭。

1.2 为什么选这道题作为第40天的练习

说句实话，我刷题是不太喜欢跳着刷的。第30天的时候，我给自己定了个规矩：每周最后一天的练习，必须做一道“综合题”——它要能覆盖过去一周涉及的主要知识点，最好还有点小坑，这样第二天复盘的时候有东西可写。

这一周我一直在看字符串处理和栈相关的内容，堆了不少零碎知识：字符串遍历的边界控制怎么处理、栈什么时候压入什么时候弹出、运算符优先级怎么比较。这些知识单独拎出来我都能写出来一套，可真要拼在一起做一个完整的计算器，心里没底。

所以看到这题的时候我就知道，它是本周最好的收官题。它不像纯粹的数据结构题那样只考模板，也不像纯粹的工程题那样只考逻辑。它是一个“计算问题”，需要你在一个极其精简的框架里，同时处理好语法解析、运算规则、边界条件。这种综合度，学三天单项知识是补不出来的，必须动手写、写错、再改。

2. 核心原理：为什么先用“中缀转后缀”再求值

2.1 中缀表达式对人友好，对程序不友好

人类书写数学表达式，习惯用的是中缀形式：数字、运算符、数字，运算符夹在中间，比如3+2*2。程序处理它是很别扭的：你要先看下一个运算符的优先级，决定是先算这个还是先算后面那个，再加上括号改变优先级，麻烦得很。

举个例子：3+2*2，如果程序机械地从左往右读，读到3+2会先得出5，再乘2得到10——这在数学上是错的。所以处理中缀表达式时，程序必须“往后看”、判断优先级，或者使用“双栈”直接计算。

我这次用的方法是先转换成后缀表达式，也就是逆波兰表达式。后缀表达式的特点是：运算符永远跟在它作用的两个数字后面。3+2*2转成后缀是3 2 2 * +。程序求值的时候，从左往右走，遇到数字就压栈，遇到运算符就弹出两个数字做运算，结果再压回栈里。整个过程没有括号、没有优先级纠纷，简单得像流水线工作。

2.2 转换规则与优先级细节

中缀转后缀的经典算法，是借助一个运算符栈完成的。遍历输入字符串，遇到的不是数字就是运算符，分情况处理：

• 如果是数字：直接输出（或者入数栈）。
• 如果是运算符：
  • 如果运算符栈为空，或者当前运算符优先级高于栈顶运算符，则直接压栈；
  • 否则，就把栈顶运算符弹出并输出，然后再次比较当前运算符与新栈顶的优先级，直到能压栈为止。
• 如果是左括号：直接压栈。
• 如果是右括号：依次弹出栈顶运算符并输出，直到遇到左括号，再把左括号弹出丢弃。

优先级方面，加减为1级，乘除为2级。这里我处理的是四则运算，括号和负号是额外需要考虑的。

比较优先级时有一个容易忽略的细节：相同优先级下，从左往右结合。比如3-2-1，应该相当于(3-2)-1。所以当新运算符的优先级等于栈顶运算符优先级时，栈顶应该弹出。这个细节如果写成>而不是>=，3-2-1会被算成3-(2-1)，结果从0变成2，测试用例都过不去。

2.3 核心代码：表达式求值的完整实现

我用的C++，实现分成两个部分：第一部分做中缀转后缀，第二部分对后缀求值。一开始我的版本只处理加减乘除，后来才补的负号，所以下面这份代码已经包含了负号处理的逻辑：

#include <iostream> #include <string> #include <stack> #include <cctype> using namespace std; // 判断字符是否为运算符 bool isOperator(char ch) { return ch == '+' || ch == '-' || ch == '*' || ch == '/'; } // 运算符优先级，负号优先级最高，处理为特殊字符 '~' int getPriority(char op) { if (op == '~') return 3; if (op == '*' || op == '/') return 2; if (op == '+' || op == '-') return 1; return 0; } // 中缀表达式转后缀表达式 string infixToPostfix(string s) { string result; stack<char> ops; bool prevIsOperator = true; // 标记上一个有效字符是否为运算符 for (int i = 0; i < s.length(); i++) { char ch = s[i]; if (ch == ' ') continue; if (isdigit(ch)) { result += ch; prevIsOperator = false; } else if (ch == '(') { ops.push(ch); prevIsOperator = true; } else if (ch == ')') { while (!ops.empty() && ops.top() != '(') { result += ops.top(); ops.pop(); } ops.pop(); // 弹出 '(' prevIsOperator = false; } else if (ch == '-') { // 判断是减号还是一元负号 if (prevIsOperator) { // 负号，用特殊字符 '~' 表示 ops.push('~'); } else { // 减号，正常按运算符处理 while (!ops.empty() && getPriority(ops.top()) >= getPriority(ch)) { result += ops.top(); ops.pop(); } ops.push(ch); } prevIsOperator = true; } else if (isOperator(ch)) { while (!ops.empty() && getPriority(ops.top()) >= getPriority(ch)) { result += ops.top(); ops.pop(); } ops.push(ch); prevIsOperator = true; } } while (!ops.empty()) { result += ops.top(); ops.pop(); } return result; } // 对后缀表达式求值 int evaluatePostfix(string postfix) { stack<int> nums; for (int i = 0; i < postfix.length(); i++) { char ch = postfix[i]; if (isdigit(ch)) { nums.push(ch - '0'); } else if (ch == '~') { int a = nums.top(); nums.pop(); nums.push(-a); } else { int b = nums.top(); nums.pop(); int a = nums.top(); nums.pop(); int result; if (ch == '+') result = a + b; else if (ch == '-') result = a - b; else if (ch == '*') result = a * b; else if (ch == '/') result = a / b; nums.push(result); } } return nums.top(); } int calculate(string s) { string postfix = infixToPostfix(s); return evaluatePostfix(postfix); } int main() { string expr = " -3 + 2 * (-3) "; cout << calculate(expr) << endl; return 0; }

这里我用了~这个特殊字符在内部表示一元负号，因为后面对后缀表达式求值时，它需要一个“单目运算”的标记，和双目加减乘除区分开。你也可以直接在数字入栈时做判断，把负号后的数字先取反再压栈，但那样处理多位负数的时候会比较绕，容易出错，所以我最后还是选择了内部标记的方式。

3. 卡了整整四十分钟的坑：负号被当成了减号

3.1 问题是怎么暴露的

写代码很快，调代码很慢。我第一次提交，前两个示例"3+2*2"和" 3/2 "都过了，第三个示例" -3+5 "直接输出一个莫名其妙的结果。我盯着那个错误结果看了好一会儿，第一反应是“是不是空格没处理好”，于是把字符串先整体去了一遍空格，再测，结果还是错的。

我在这道题上花了比练习时长多得多的调试时间。问题表面上是一个输出不对，实际上是转换阶段把-3里的负号当成了减法运算符，整个表达式的语义全变了。

3.2 排查链路：从逐步打印到问题定位

我当时的排查思路是这样的：先把中缀转后缀的结果打印出来。正常输入" -3 + 5 "，手动转换，后缀应该是3~ 5 +——负号先作用于3，再和5相加，结果是2。但我代码里打印出来的是3 5 -。两种顺序一说出来，问题就清楚了：3和5之间的负号，被当成了二元的减法，也就是说，-3在转换时被当成了“0减3”，变成二元运算了，后来+5又被正确处理，最后算成了3-5的转置版。

这个问题的根子还在于负号的语义判断。对计算机而言，负号有双重身份：出现在数字前面，它是一元取负；出现在两个表达式之间，它是二元减法。我的代码里需要一个“上一个有效字符”的状态，来判断这个负号到底该按哪个身份处理。

3.3 三种需要识别负号的典型场景

调试过程中，我把负号的所有出现场景都列了出来，做成了一张表：

判断逻辑的核心就是：如果负号前面的有效字符是数字或右括号，那它是减法；如果前面的有效字符是运算符或左括号，或它本身就是第一个有效字符，那它是取负。

我代码里prevIsOperator这个布尔变量就是干这个的。一开始我只把它初始化为true（表示表达式开头），但忘了在处理右括号后更新状态，导致括号后面跟负号的时候判断错。修完这一处再测试，"2*(-3)"才终于输出了-6。

4. 这40天上机练习，我的方法与收获

4.1 从第1天到第40天的节奏演进

前10天，我的练习方式一塌糊涂。每天打开判题系统，挑一个看起来会做的简单题，写完了事。那道题我可能根本没吃透，第二天遇到同样类型的题目照样卡壳。效率很低，但至少养成了“每天打开编辑器”的习惯。

第11天到第25天，我开始改变策略，不再追逐题目的数量，而是改成专题训练：数组类做两天，字符串类做两天，链表类做两天。每个专题结束的那天，我会把这类题的常见套路写进自己的练习笔记。比如字符串题的核心往往集中在：边界索引、字符判断、特殊状态标记。我今天的负号处理，实际就用到了其中两条。

第26天到第40天，我加入了一个环节：固定晚上打练习日志。日志格式很简单，五列数据：

每天写日志这件事，看起来简单，但它帮我强制建立了一种“练习闭环”：练习、记录、复盘。很多当时没想明白的问题，过两天回头看笔记，一下就通了。

4.2 第40天之后，我给自己的三条硬规矩

通过这40天的练习，我总结出三条对自己特别有用的硬规矩，写在这里，也算给自己下个留档：

第一，每天只做一件事，但这件事必须做完。不要一天开三个题目，每个题目写了一半就换。开题之前先评估：这题的规模大概需要多久？超过今天练习时长就拆成两天做；能在今天结束前提交一个能跑的版本，就把它磨完。

第二，调试时先打印中间状态，不要凭眼睛猜。我今天就是靠把postfix打印出来才定位到负号问题的。C++ 里一条cout语句比盯着代码发呆十分钟管用得多。

第三，遇到新的边界条件，把它加入测试用例。不管题目本身有没有要求，我会额外准备几组用例：负号开头、括号内负号、两个运算符连着、连续括号、除法向零取整。这些用例能复用的价值极高，后面遇到类似题目，直接套用就行。

5. 空闲时间里，我还认真想了“上机练习到底在练什么”

这个问题听起来有点虚，但第40天这个节点，我确实认真想了。很多人上机练习刷题，练的是“把题刷完”，提交通过就完事。但坚持到第40天，我觉得上机练习真正练的是三样东西：

第一，把模糊想法转成精确操作的能力。一个数学上“显然成立”的想法，落到代码里要处理空格、要处理数字越界、要处理运算符栈空不空。这个过程没有任何人能替你完成，只有一次次上机、一次次报错、一次次回头改，大脑才会习惯这种精确性。

第二，把大问题拆成小部分的习惯。表达式求值看起来是一个整体，但我实际写的时候先拆成了“转后缀”和“求值”两大块，每一块再拆成“如何处理数字”“如何处理运算符”“如何处理括号”。这个拆解能力，不只是做算法题有用，写任何稍微大一点的程序都受益。

第三，面对乏味重复任务的耐性。第40天的题目不算难，但我坐下来一遍遍跑测试用例的时候，还是会觉得枯燥。真正拦在“会了”和“熟练了”之间的，就是这份耐性。上机练习第40天，我最大的收获其实不是今天把这道题调通了，而是发现自己对“枯燥”的容忍度，比40天前高了一大截。

回看这40天，我在编辑器里敲下的代码行数大概不到6000行，不算多。但最让我欣慰的是打卡表上那串连续的日期——中间没有断过一天。哪怕是只写二十分钟、只解决一道小题的那几天，也算数。第40天结束前，我把今天的完整题解放进了练习日志。明天，该进入第41天了。