企业官网建设流程全解析

Go 实现逆波兰表达式求值：LeetCode 150 题解与栈解法源码剖析（LeetCode-Go 实战）

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本文围绕 LeetCode 第 150 题「Evaluate Reverse Polish Notation（逆波兰表达式求值）」展开，结合开源仓库 LeetCode-Go 中该题目的 README.md、完整 Go 实现与配套测试用例，从题目约束、栈求解思路、源码逐行解读到覆盖率验证，系统地讲解如何在 Go 中借助栈这一经典数据结构高效完成后缀表达式求值。读完本文，你将掌握栈运算的核心套路，理解 Go 整数除法向零截断的特性，并能在本仓库环境中复现测试与覆盖率验证流程。

题目描述

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

有效运算符为+、-、*、/。每个操作数可以是整数，也可以是另一个表达式。

题目给出的注意点（来自 README.md）：

• 两个整数相除的结果需要向零截断（truncate toward zero）；
• 给定的 RPN 表达式始终有效，即表达式总能求出一个结果，并且不会出现除零操作。

示例一

Input: ["2", "1", "+", "3", "*"] Output: 9 Explanation: ((2 + 1) * 3) = 9

示例二

Input: ["4", "13", "5", "/", "+"] Output: 6 Explanation: (4 + (13 / 5)) = 6

示例三

Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] Output: 22 Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22

题目大意：计算逆波兰表达式（后缀表达式）的值。

逆波兰表达式（后缀表达式）速览

逆波兰表达式（Reverse Polish Notation，简称 RPN，也称后缀表达式）由波兰逻辑学家 Jan Łukasiewicz 提出，其核心特点是运算符写在两个操作数之后。例如中缀表达式((2 + 1) * 3)写作后缀形式就是2 1 + 3 *。

RPN 之所以在计算机领域被广泛使用，是因为它天然契合栈式求值模型，完全不需要括号来区分优先级：

• 遇到操作数就压栈；
• 遇到运算符就弹出栈顶的两个操作数进行计算，再把结果压回栈中。

这种"无括号、无优先级、从左到右扫描一遍即可出结果"的性质，使其大量应用于计算器程序、栈式虚拟机（如 JVM、Python 字节码）以及编译器表达式求值等场景。

题目关键约束解读

在动手写代码之前，有两个约束直接决定了实现细节：

1. 除法向零截断：RPN 求值中13 / 5应得2（而不是2.6或向下取整的2）。Go 语言中整数除法a / b本身就是向零截断的（对正数即直接舍去小数部分，对负数则向零方向舍入），因此源码中直接用/运算符即可满足题意，无需额外处理。
2. 表达式恒有效、无除零：意味着不需要在代码中做除零保护或合法性校验，简化了实现逻辑；同时栈内元素数量始终能保证弹出两个操作数。

解题思路：经典的栈解法

这道题是考察栈数据结构应用的经典题目（这也是原文档在"解题思路"中给出的核心提示）。

算法流程非常直观，可以概括为三步：

1. 从左到右遍历tokens中的每个 token；
2. 若 token 是操作数（整数，可含负号），将其压入栈；
3. 若 token 是运算符（+、-、*、/），从栈顶弹出两个操作数num1（先弹出的、位于栈顶下方）与num2（后弹出的、位于栈顶），计算num1 op num2并将结果压回栈。

遍历结束后，栈中剩下的唯一元素即为整个表达式的值。

示例二的手工推演

以["4", "13", "5", "/", "+"]为例：

最终栈顶即答案6，与示例输出一致。

示例三中的两个易错点

示例三["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]中值得注意两点：

• 负数作为操作数："-11"是一个完整的操作数而非运算符，解析时须正确识别为整数-11；
• 减法与除法的操作数顺序：栈是后进先出的，弹出时先得到的是后入栈的操作数。若表达式为a b -，应计算a - b（先弹出的a作为被减数/被除数），而不是b - a。示例三中的6 / -132与10 * 0均依赖这一顺序约定，最终推导出22。

仓库源码实现逐行剖析

LeetCode-Go 仓库在 150. Evaluate Reverse Polish Notation.go 中给出了完整实现，这里附上源码：

package leetcode import ( "strconv" ) func evalRPN(tokens []string) int { stack := make([]int, 0, len(tokens)) for _, token := range tokens { v, err := strconv.Atoi(token) if err == nil { stack = append(stack, v) } else { num1, num2 := stack[len(stack)-2], stack[len(stack)-1] stack = stack[:len(stack)-2] switch token { case "+": stack = append(stack, num1+num2) case "-": stack = append(stack, num1-num2) case "*": stack = append(stack, num1*num2) case "/": stack = append(stack, num1/num2) } } } return stack[0] }

对源码的关键点逐一解读：

1. 用切片直接模拟栈，并预分配容量

stack := make([]int, 0, len(tokens))

实现没有引入额外的栈结构，而是直接使用 Go 原生切片模拟栈，append即入栈、切片截断即出栈。预分配len(tokens)容量可以避免多次扩容带来的内存拷贝，在大规模输入下更高效。

2. 用strconv.Atoi区分操作数与运算符

v, err := strconv.Atoi(token) if err == nil { stack = append(stack, v) }

这是本实现最巧妙的地方：对每个 token 尝试用strconv.Atoi做整数解析。解析成功说明它是操作数（包括"-11"这样的负数），压栈；解析失败（如"+"）则走运算符分支。这样既避免了手写字符判断，也天然覆盖了负数的场景。

3. 弹出顺序决定减法/除法的正确性

num1, num2 := stack[len(stack)-2], stack[len(stack)-1] stack = stack[:len(stack)-2]

num2是后入栈（栈顶）的元素，num1是它下面的元素。后续统一按num1 op num2计算，从而保证a b -得到a - b、a b /得到a / b。出栈通过切片截断stack[:len(stack)-2]一次完成。

4. 运算符分派用switch表达

对+ - * /四种运算符分别计算结果并压回栈。从源码结构可以推断：由于题目保证表达式有效，代码没有为未知 token 提供default分支；若未来扩展其他运算符，需要在此处补充对应分支。

5. 结果即栈底唯一元素

return stack[0]

遍历结束时，栈中只剩下一个元素，它就是整个表达式的求值结果。

顺带一提，本仓库 structures/Stack.go 中提供了基于[]int的通用栈封装（含NewStack、Push、Pop、Len、IsEmpty等 API，并在 structures/Stack_test.go 中有配套测试）。而 150 题的解法则选择了更轻量的内联切片栈写法，省去了封装调用的开销，这也体现了"当栈操作简单时直接使用切片即可"的常见工程取舍。

测试用例与覆盖率验证

仓库为本题提供了完整的测试文件 150. Evaluate Reverse Polish Notation_test.go，采用question150 / para150 / ans150结构组织表格化测试数据，共覆盖 5 组用例：

从仓库根目录的 coverage.txt（第 2041–2049 行）可以看到，evalRPN函数内部的每个基本块均被测试命中，包括Atoi成功与失败两个分支、+ - * /四个运算符分支以及最终return stack[0]，与项目"100% test coverage"的总体目标一致。

在仓库根目录运行 gotest.sh 即可一键生成覆盖率文件（该脚本通过go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...对全部 leetcode 包一次性产出合法的覆盖率报告）；也可以只针对本题所在包单独运行：

go test -v -run Test_Problem150 ./leetcode/0150.Evaluate-Reverse-Polish-Notation/

运行后会输出类似【input】:["2","1","+","3","*"] 【output】:9的逐用例结果（见测试文件中的fmt.Printf调试输出），便于直观核对每组输入与输出。

复杂度分析

• 时间复杂度：O(n)，其中n为tokens的长度。每个 token 只被处理一次，入栈、出栈、四则运算均为 O(1) 操作；
• 空间复杂度：O(n)，最坏情况下表达式前半段全是操作数（例如"1", "2", "3", ..., "+"），栈中需同时存放接近 n 个元素。代码中make([]int, 0, len(tokens))的预分配也印证了空间上界为 O(n)。

扩展思考：RPN 相关题目与后续方向

掌握本题后，可以沿着两个方向继续深入：

1. 中缀转后缀：逆波兰表达式求值常与"中缀表达式转后缀表达式"（借助运算符优先级与辅助栈）配套出现，二者组合即构成一个完整的中缀计算器。理解了本题的求值过程，反向理解转换算法会更容易。
2. 同仓库栈类题目对照：LeetCode-Go 中大量题目与栈相关，例如 20. Valid Parentheses（括号匹配压栈/出栈）、155. Min Stack（栈 + 辅助栈维护最小值）等，它们的共同点是"利用后进先出的特性维护某种中间状态"，与本题的求值思路一脉相承。

此外可以思考的工程细节：如果表达式规模极大，可考虑用显式栈替代递归（本题本身就是迭代实现，无递归栈溢出风险）；如果运算符集合扩展（如%、幂运算），只需在switch中增加分支并保证弹栈顺序一致即可。

总结

LeetCode 150 是一道以栈为核心的经典送分题，其求解框架"遇数压栈、遇符弹二算一、结果回栈"简单且通用。在 LeetCode-Go 仓库中，本题通过strconv.Atoi错误判定巧妙区分操作数与运算符、用切片预分配实现高性能栈、并借助测试用例与覆盖率报告验证了所有分支，是一个"题目约束 → 思路设计 → 源码实现 → 测试验证"完整闭环的优质范本。掌握它的栈式思维，对后续处理表达式解析、括号匹配、单调栈等题目都大有裨益。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go