栈这个结构很多人学的时候觉得简单不就是后进先出嘛拿个数组或者链表模拟一下push、pop 一写就完事了。但真到了要拿它解决一个稍微像样点的问题比如做一个能算加减乘除、带括号、还能处理多位数的计算器就会发现事情没那么简单。我见过不少同学栈的基本操作背得滚瓜烂熟一到用栈实现综合计算器这种题就卡壳核心原因不是栈没学好而是没想清楚栈到底在这里扮演什么角色。这篇内容就是围绕这个经典问题展开的。我会把用栈实现综合计算器的完整思路拆开讲从为什么需要两个栈、每一步的判定逻辑怎么设计、多位数字怎么处理、括号怎么收尾到实际写代码时容易踩的坑都会给到可以直接复现的细节。适合已经了解栈的基本概念、想把它真正用起来的中初级开发者也适合正在准备算法练习、想把栈的应用这块补扎实的朋友。读完你至少能独立写出一个支持四则运算和括号的整数计算器并且明白每一步为什么这么设计。1. 为什么一个栈不够用从表达式求值的本质说起1.1 中缀表达式带来的天然难题我们平时写的算式比如3 4 * 2 - 1叫做中缀表达式运算符夹在两个操作数中间。这种写法对人友好但对计算机不友好。问题出在优先级和结合性上4 * 2必须先算尽管它出现在后面。如果从左往右一路算过去结果就错了。要正确求值计算机必须有能力记住前面还没轮到处理的运算符和操作数等遇到更高优先级的运算时先处理掉。这个记住的需求正好就是栈的强项——后进先出最近遇到的运算符优先级最高先被处理。但只用一个栈是不够的。因为表达式里同时存在两类需要暂存的东西一类是数字操作数一类是运算符。它们的处理时机和规则完全不同。数字要等运算符确定后才参与计算运算符要等比较完优先级才决定是入栈还是立即执行。把这两类东西混在一个栈里逻辑会变得极其混乱你得不断判断栈顶到底是数字还是符号。1.2 双栈分工数栈与符号栈的职责边界所以标准解法是开两个栈一个数栈numberStack专门存操作数一个符号栈operatorStack专门存运算符。两者各司其职配合完成求值。分工逻辑是这样的扫描表达式遇到数字就压入数栈遇到运算符先和符号栈栈顶的运算符比优先级如果当前运算符优先级小于等于栈顶运算符说明栈顶那个运算可以先算了于是从数栈弹出两个数、从符号栈弹出一个运算符执行计算把结果压回数栈然后继续拿当前运算符和新的栈顶比较如果当前运算符优先级大于栈顶或者符号栈为空就直接把当前运算符压入符号栈遇到左括号直接入符号栈遇到右括号则不断执行计算直到弹出左括号为止。这个流程的核心思想是保证符号栈里的运算符优先级严格递增。一旦要压入的运算符破坏了递增关系就先把前面能算的都算掉。这样当整个表达式扫描完符号栈里剩下的运算符一定是按优先级从低到高排列的从栈顶依次弹出计算即可。提示这里说的优先级递增是从栈底到栈顶的方向。栈顶永远是当前优先级最高的待处理运算符所以它最先被消费。1.3 一个具体例子走一遍拿3 4 * 2 - 1来手动跑一遍感受双栈的节奏步骤读到数栈底→顶符号栈底→顶动作说明133空数字入数栈23符号栈空直接入343, 4数字入数栈4*3, 4, ** 优先级高于 入栈523, 4, 2, *数字入数栈6-3, 4, 2, *- 优先级低于先算 4287-3, 8继续比- 等于 算 38118-11空符号栈空- 入栈9111, 1-数字入数栈10结束11, 1-弹出 -算 11-110最终结果 10和手算一致。这个过程里符号栈始终维持着栈顶优先级最高的状态这就是它能正确工作的根本原因。2. 优先级判定与多位数解析两个最容易翻车的细节2.1 优先级比较函数的写法与边界优先级比较看起来简单但边界处理不好就会出错。我一般用一个函数priority(op)返回运算符的优先级数值// 返回运算符优先级数值越大优先级越高 public static int priority(int op) { if (op * || op /) { return 1; } else if (op || op -) { return 0; } else { return -1; // 假定只有 - * / 四种 } }这里有个关键点判定条件是小于等于而不是小于。为什么因为四则运算满足左结合性3 - 2 - 1必须从左往右算成(3-2)-1 0而不是3-(2-1) 2。当读到第二个-时它和栈顶的-优先级相等此时必须先把栈顶的-算掉才能保证左结合。如果写成小于才计算相等时直接入栈就会变成右结合结果就错了。这个细节我在早期写的时候栽过跟头当时测试10 - 2 - 3得到 11 而不是 5排查了半天才发现是判定条件写成了严格小于。所以记住同级运算符相遇先算栈顶的保证从左到右。2.2 多位数拼接不能读一位算一位另一个高频错误是处理多位数。表达式123 45里123是三个字符如果你读一个字符1就当成数字 1 入栈结果必然错。正确做法是遇到数字字符时先不急着入栈而是继续往后看把连续的数字字符拼成一个完整的数。// 处理多位数循环读取连续数字字符 String keepNum ; int index 0; while (index expression.length()) { char ch expression.charAt(index); if (ch 0 ch 9) { keepNum ch; // 如果已经是最后一位直接入栈 if (index expression.length() - 1) { numStack.push(Integer.parseInt(keepNum)); } else { // 看下一位是不是数字不是就说明当前数读完了 if (expression.charAt(index 1) 0 || expression.charAt(index 1) 9) { numStack.push(Integer.parseInt(keepNum)); keepNum ; // 清空准备读下一个数 } } } // ... 处理运算符的逻辑 index; }这段代码的逻辑是只要下一位还是数字就继续拼一旦下一位不是数字是运算符、括号或已到末尾说明当前这个多位数读完了转成整数入栈然后清空临时变量。注意keepNum每次入栈后必须清空否则下一个数字会拼到上一个数后面。这个 bug 很隐蔽因为只有连续出现多个数字时才会暴露。2.3 用生活类比理解延迟入栈多位数拼接的本质是延迟决策。就像你在超市结账收银员扫一个商品不会立刻让你付款而是把所有商品扫完再一起算总价。数字字符一个个读进来先攒着等确认这个数完整了再一次性入栈。这种攒够了再处理的思路在处理不定长数据时非常常见值得记住。3. 括号的处理让符号栈学会就地清算3.1 左括号直接入栈的理由括号是表达式里优先级最高的结构但它本身不参与运算只负责改变运算顺序。遇到左括号(时直接把它压入符号栈不做任何优先级比较。为什么因为左括号相当于一个隔离标记它后面的运算符优先级再低也要等括号内的内容全部算完才能和括号外的比较。你可以把左括号理解成一道墙墙内的运算自成一体墙外的运算符暂时够不着墙内的东西。所以左括号入栈时不需要比较它天然就是最高优先级的占位符。3.2 右括号触发的连续清算遇到右括号)时逻辑就反过来了它表示括号内的运算到此结束该结算了。此时要不断从数栈和符号栈弹出元素做计算直到符号栈栈顶是左括号为止最后把左括号弹出丢弃。// 遇到右括号循环计算直到遇到左括号 while (!operatorStack.isEmpty() operatorStack.peek() ! () { int num2 numStack.pop(); int num1 numStack.pop(); int op operatorStack.pop(); int res cal(num1, num2, op); numStack.push(res); } // 弹出左括号 operatorStack.pop();这里有个容易忽略的点弹出两个数时顺序不能反。先弹出的是右操作数num2后弹出的是左操作数num1计算时是num1 op num2。因为栈是后进先出先入栈的左操作数在下面后入栈的右操作数在上面所以先弹出的是右操作数。减法、除法对顺序敏感搞反了结果就错。3.3 括号嵌套时的表现对于嵌套括号比如2 * (3 (4 - 1))双栈机制依然成立。每遇到一个左括号就入栈每遇到一个右括号就清算到最近的左括号。因为栈的后进先出特性最内层的括号最先被清算天然符合从内到外的求值顺序。这也是栈结构优雅的地方——它自动帮你处理了嵌套层级你不需要额外维护层级计数。我实测过几层嵌套的表达式只要括号匹配正确逻辑完全不用改。唯一要注意的是括号不匹配的情况比如多了一个右括号或者少了右括号需要在代码里加校验否则会抛异常或者死循环。4. 完整实现与逐段拆解4.1 核心计算函数的封装先把最基础的计算逻辑抽出来输入两个操作数和一个运算符返回结果public static int cal(int num1, int num2, int op) { int res 0; switch (op) { case : res num1 num2; break; case -: res num1 - num2; break; case *: res num1 * num2; break; case /: res num1 / num2; break; default: throw new RuntimeException(不支持的运算符: (char) op); } return res; }注意参数顺序是num1在前、num2在后调用时务必保证num1是左操作数。除法这里用的是整数除法如果需要小数结果把返回类型和栈的元素类型改成double即可但要注意浮点精度问题。4.2 主循环的完整骨架把前面所有片段串起来主流程如下public static int calculate(String expression) { StackInteger numStack new Stack(); StackCharacter operatorStack new Stack(); String keepNum ; int index 0; while (index expression.length()) { char ch expression.charAt(index); if (ch 0 ch 9) { // 多位数处理逻辑见 2.2 节 keepNum ch; if (index expression.length() - 1) { numStack.push(Integer.parseInt(keepNum)); } else if (expression.charAt(index 1) 0 || expression.charAt(index 1) 9) { numStack.push(Integer.parseInt(keepNum)); keepNum ; } } else if (ch () { operatorStack.push(ch); } else if (ch )) { // 右括号清算逻辑见 3.2 节 while (operatorStack.peek() ! () { int num2 numStack.pop(); int num1 numStack.pop(); int op operatorStack.pop(); numStack.push(cal(num1, num2, op)); } operatorStack.pop(); // 弹出左括号 } else { // 运算符处理 while (!operatorStack.isEmpty() operatorStack.peek() ! ( priority(ch) priority(operatorStack.peek())) { int num2 numStack.pop(); int num1 numStack.pop(); int op operatorStack.pop(); numStack.push(cal(num1, num2, op)); } operatorStack.push(ch); } index; } // 扫描结束清算剩余运算符 while (!operatorStack.isEmpty()) { int num2 numStack.pop(); int num1 numStack.pop(); int op operatorStack.pop(); numStack.push(cal(num1, num2, op)); } return numStack.pop(); }4.3 收尾清算为什么不能省很多人写完主循环就以为结束了忘了最后一步表达式扫描完后符号栈里可能还残留运算符。比如3 4扫描完时数栈是[3, 4]符号栈是[]如果不做收尾清算直接返回数栈栈顶得到的是 4 而不是 7。收尾清算的逻辑和右括号清算几乎一样只是没有左括号作为终止条件而是一直清到符号栈为空。这一步是必须的漏掉就是典型的结果错误。提示收尾清算时同样要注意弹出顺序先弹右操作数再弹左操作数。5. 实测中暴露的坑与排查思路5.1 空栈弹出导致的异常最常见的运行时错误是EmptyStackException通常发生在两个地方一是表达式以运算符开头或结尾比如3或3二是括号不匹配比如(34少了右括号收尾清算时符号栈里还留着左括号弹出时逻辑就乱了。排查这类问题的思路是在每次pop之前先判断栈是否为空或者在入口处对表达式做一次合法性校验。我一般会写一个简单的校验函数检查括号是否配对、首尾是否是合法字符。虽然多写几行代码但能省下大量调试时间。5.2 优先级相等时的处理顺序前面提过同级运算符必须先算栈顶否则左结合会变成右结合。这个坑的隐蔽之处在于它只在连续同级运算时暴露比如8 / 4 / 2。如果判定条件写错会算成8 / (4 / 2) 4而正确答案是(8 / 4) / 2 1。测试用例一定要覆盖连续同级运算尤其是减法和除法。5.3 多位数与运算符紧邻的边界还有一种情况是数字和运算符紧邻比如123。处理12时读到1发现下一位2还是数字继续拼读到2发现下一位是不是数字于是把12入栈并清空。这个逻辑是对的。但如果表达式末尾是数字比如123处理最后的3时index已经是最后一位必须走已到末尾直接入栈的分支否则3永远不会入栈。这个边界我在第一次写的时候漏了导致结果少算了最后一位。5.4 一个实用的调试技巧调试计算器时最有效的方法是在每一步打印两个栈的状态。就像 1.3 节那张表一样把每次读到的字符、数栈内容、符号栈内容、执行的动作都打出来一眼就能看出哪一步逻辑跑偏了。这比单步调试快得多因为你能看到整个状态流转的全貌。常见现象可能原因排查方向结果差最后一位数末尾数字未入栈检查是否处理了 index 到末尾的分支连续减法结果偏大同级运算顺序错误检查优先级判定是否为小于等于抛空栈异常括号不匹配或首尾非法加表达式合法性校验多位数被拆开未做连续数字拼接检查 keepNum 逻辑与清空时机括号内结果错误右括号清算未弹左括号检查清算循环终止条件6. 从整数到浮点、从四则到更多运算的扩展方向6.1 支持小数与负数当前实现只支持非负整数。要支持小数把数栈类型改成double多位数拼接时把小数点.也纳入连续读取的范围即可。要支持负数情况会复杂一些因为-既可能是减号也可能是负号。判断方法是看-前面是不是运算符或左括号或表达式开头如果是那它就是负号可以把它和后面的数字一起处理或者用一个特殊标记。6.2 引入更多运算符如果想支持取模%、幂运算^只需要在priority函数里给它们分配更高的优先级并在cal函数里加上对应的计算分支。幂运算是右结合的2^3^2应该算成2^(3^2)这时候优先级判定条件就要针对幂运算特殊处理不能简单套用小于等于。这说明优先级和结合性是两个独立的概念扩展时要分别考虑。6.3 中缀转后缀的另一种思路除了双栈直接求值还有一种经典做法是先把中缀表达式转成后缀表达式逆波兰表达式再对后缀表达式求值。后缀表达式的优点是求值时不需要考虑优先级从左往右遇到运算符就弹出两个数计算即可。转换过程本身也用栈但逻辑和双栈求值不同。两种方法各有适用场景双栈求值更直接中缀转后缀在需要复用表达式比如同一个表达式多次代入不同变量求值时更有优势。我个人在实际项目中更倾向双栈直接求值因为代码量少、逻辑集中调试时状态一目了然。但如果表达式需要被解析成语法树做进一步分析那中缀转后缀或者直接构建 AST 会更合适。选哪种取决于你的实际需求没有绝对的好坏。6.4 性能与栈实现的选型用 Java 的Stack类还是自己用数组模拟栈在计算器这种场景下性能差异可以忽略因为表达式通常不长。但如果是批量处理大量表达式自己用数组实现栈能减少对象创建开销。另外Stack类是同步的单线程场景下用ArrayDeque替代会更高效。这些都是实际工程里值得注意的小细节虽然不影响正确性但体现了对性能的敏感度。写到这里这个用栈实现综合计算器的完整思路就交代清楚了。核心其实就三件事双栈分工、优先级比较用小于等于、多位数要拼接。把这三件事想明白剩下的就是代码细节和边界处理。我建议你先把 1.3 节那张手动推演表自己走一遍再动手写代码写完用几组带括号和连续同级运算的表达式测一测基本就能掌握扎实了。
