LeetCode-Go 题解精讲224. Basic Calculator 基本计算器的双解法实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本篇以 LeetCode-Go 仓库中 224. Basic Calculator 题目文档 为核心深入拆解基本计算器这道经典栈应用题的两种 Go 实现符号位跟踪的单栈扫描法以及字节栈加括号子串化简法。读完本文你将掌握含空格、负数与嵌套括号的表达式求值思路理解sign状态位与栈协同工作的原理并能直接通过仓库内的测试用例验证两种实现的正确性。题目回顾表达式求值的基本约束原题要求实现一个基础计算器求一个简单表达式的值。表达式字符串中允许出现的元素为左括号(与右括号)加号与减号-非负整数空字符空格。原文档给出的三个示例输入输出1 12 2-1 2 3(1(452)-3)(68)23题目附带两条重要约束见原文档 Note 部分可以假设给定表达式总是合法的即括号必然配对、符号与数字的排列必然可计算禁止使用语言内置的eval库函数即必须自己实现求值逻辑。核心难点拆解原文档在解题思路中浓缩了本题的两大注意点这也是几乎所有实现都要面对的三个工程细节跳过空格字符串中任意位置都可能出现空格扫描时需要跳过不能把它们当作有效字符参与计算符号状态跟踪算式中会出现负数与负负得正的情况例如2-(5-6)中括号前的减号要作用于括号内结果因此需要记录每一步计算当前的符号位1或-1而不能只做简单的数字累加括号嵌套括号内的表达式拥有独立的作用域括号前的符号会对括号内整体求值结果取反或保持必须借助栈来保存外层上下文。下面分别讲解仓库中给出的两种解法calculate与calculate1两者的完整实现均位于 224. Basic Calculator.go。解法一单栈扫描与符号位跟踪calculate是本仓库的主推解法整体只对字符串做一趟从左到右的扫描用一个栈保存括号前的计算结果与符号状态核心代码位于 224. Basic Calculator.go#L10-L41。func calculate(s string) int { i, stack, result, sign : 0, list.New(), 0, 1 // 记录加减状态 for i len(s) { if s[i] { i } else if s[i] 9 s[i] 0 { // 获取一段数字 base, v : 10, int(s[i]-0) for i1 len(s) s[i1] 9 s[i1] 0 { v v*base int(s[i1]-0) i } result v * sign i } else if s[i] { sign 1 i } else if s[i] - { sign -1 i } else if s[i] ( { // 把之前计算结果及加减状态压栈开始新的计算 stack.PushBack(result) stack.PushBack(sign) result 0 sign 1 i } else if s[i] ) { // 新的计算结果 * 前一个加减状态 之前计算结果 result result*stack.Remove(stack.Back()).(int) stack.Remove(stack.Back()).(int) i } } return result }四个核心状态变量作用result当前作用域内已经累积的求值结果sign当前符号位1代表加、-1代表减默认初始为1stack用container/list实现的双向链表栈保存进入括号前的result与signi扫描指针逐字符处理的五种情况空格i直接跳过不参与任何计算数字题目允许非负整数且可能为多位数因此内层for循环持续向后拼接每一位v v*10 digit直到遇到非数字字符为止得到完整数值后乘以当前sign累加到result将sign置为1-将sign置为-1。这两个分支使得负负得正天然成立——连续两个减号时第二个减号把sign从-1翻回1(说明进入新的括号作用域。先把当前result与sign依次压栈保存注意压栈顺序弹出时先取到的是sign然后把result归零、sign重置为1开始计算括号内的表达式)括号内计算完毕此时栈顶是进入该括号前压入的sign再往下一层是之前的result。新的result 括号内结果 × 外层符号 外层结果正是括号前减号对整体取反的实现关键。仍以示例2-(5-6)为例推演计算完2后遇到-sign -1遇到(时将result 2与sign -1压栈括号内5 - 6得到result -1遇到)时执行-1 × (-1) 2 3与测试期望一致。复杂度分析时间复杂度每个字符至多被扫描一次数字拼接与栈操作均为常数时间整体为 O(n)n 为字符串长度空间复杂度栈中最多保存嵌套括号层数对应的(result, sign)二元组最坏为 O(n)。解法二字节栈与括号子串化简calculate1提供了另一种思路先把整个表达式按字符压入一个[]byte栈遇到)时取出最近一对括号之间的子串交给calculateStr求值后再把数值结果回填到栈中最终对整个化简后的字符串再求一次值。实现位于 224. Basic Calculator.go#L44-L68。func calculate1(s string) int { stack : []byte{} for i : 0; i len(s); i { if s[i] { continue } else if s[i] ) { tmp, index : , len(stack)-1 for ; index 0; index-- { if stack[index] ( { break } } tmp string(stack[index1:]) stack stack[:index] res : strconv.Itoa(calculateStr(tmp)) for j : 0; j len(res); j { stack append(stack, res[j]) } } else { stack append(stack, s[i]) } } fmt.Printf(stack %v\n, string(stack)) return calculateStr(string(stack)) }其工作流程可以概括为三步扫描字符串空格直接丢弃其余字符数字、运算符、括号依次入栈遇到)时从栈顶向下找到最近的(将两者之间的子串取出并清空到(位置调用calculateStr求出该子表达式的整数值再通过strconv.Itoa转为数字字符回填进栈。这样最内层括号被化简为一个数字全部括号化简完毕后对剩余字符串再调用一次calculateStr得到最终答案。calculateStr连续符号合并与顺序求值子表达式求值函数calculateStr位于 224. Basic Calculator.go#L70-L112它把求值拆成两个阶段。第一阶段合并连续符号。由于括号化简后可能出现2-3、2--3这类连续运算符原文档解题思路中特别点名的负负得正情况代码用一个小栈s做符号规约连续符号组合规约结果保留得--变为--得-、-变为-第二阶段数字与符号分离。借助isDigital辅助函数224. Basic Calculator.go#L114-L118识别数字区间把表达式切分为独立的数字序列nums与符号序列s然后从nums[0]出发按符号顺序依次加减得出结果。复杂度分析与适用说明该解法每次遇到)都会对被截取的子串调用calculateStr重新扫描对于2-(3-(4-1))这类深层嵌套输入内层子串会被反复扫描与回填最坏时间复杂度为 O(n²)从源码结构看calculate1与calculateStr内部保留了fmt.Printf调试输出如stack %v、s %v nums %v res %v运行测试时会在终端打印中间过程更适合作为理解求值流程的教学示例而解法一calculate更适合作为实际提交的简洁方案。测试用例与验证仓库为本题提供了完整测试位于 224. Basic Calculator_test.go。Test_Problem224覆盖了以下用例输入期望输出考察点1 12基本加法、空格 2-1 2 3首尾空格与混合加减(1(452)-3)(68)23多层括号嵌套2-(5-6)3括号前减号负负得正100 23 - 12111多位整数2-(3-(4-1))3深层嵌套与符号翻转此外测试末尾还针对calculateStr的连续符号合并分支补充了一组健壮性用例仅对calculate1断言23 → 5、2(0-3) → -1、2-3 → -1、2-(0-3) → 5分别覆盖了、-、-、--四种规约路径保证符号合并逻辑无遗漏。如何运行测试在仓库根目录执行单题测试go test -v ./leetcode/0224.Basic-Calculator/该仓库基于 Go 1.19见 go.modmodule 名为github.com/halfrost/LeetCode-Go所有题解统一放置于leetcode/目录。若想全量回归并生成覆盖率报告可使用仓库自带的 gotest.shbash gotest.sh脚本会对./leetcode/...以-covermodeatomic模式一次性生成合法的coverage.txt这也是本项目宣称 100% 测试覆盖率所依赖的验证方式。小结Basic Calculator 是理解栈 状态位求解表达式类问题的绝佳范本解法一用sign符号位配合单栈一趟扫描把括号、空格、负数三种干扰统一处理时间 O(n)、空间 O(n)解法二则用字节栈逐步化简括号子串直观但最坏 O(n²)。结合仓库中 题目文档 与 测试用例你可以对照示例逐行验证两种实现的行为差异并由此举一反三迁移到 227. Basic Calculator II、772 等扩展题型的*、/与一元负号处理上。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解精讲：224. Basic Calculator 基本计算器的双解法实现
LeetCode-Go 题解精讲224. Basic Calculator 基本计算器的双解法实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本篇以 LeetCode-Go 仓库中 224. Basic Calculator 题目文档 为核心深入拆解基本计算器这道经典栈应用题的两种 Go 实现符号位跟踪的单栈扫描法以及字节栈加括号子串化简法。读完本文你将掌握含空格、负数与嵌套括号的表达式求值思路理解sign状态位与栈协同工作的原理并能直接通过仓库内的测试用例验证两种实现的正确性。题目回顾表达式求值的基本约束原题要求实现一个基础计算器求一个简单表达式的值。表达式字符串中允许出现的元素为左括号(与右括号)加号与减号-非负整数空字符空格。原文档给出的三个示例输入输出1 12 2-1 2 3(1(452)-3)(68)23题目附带两条重要约束见原文档 Note 部分可以假设给定表达式总是合法的即括号必然配对、符号与数字的排列必然可计算禁止使用语言内置的eval库函数即必须自己实现求值逻辑。核心难点拆解原文档在解题思路中浓缩了本题的两大注意点这也是几乎所有实现都要面对的三个工程细节跳过空格字符串中任意位置都可能出现空格扫描时需要跳过不能把它们当作有效字符参与计算符号状态跟踪算式中会出现负数与负负得正的情况例如2-(5-6)中括号前的减号要作用于括号内结果因此需要记录每一步计算当前的符号位1或-1而不能只做简单的数字累加括号嵌套括号内的表达式拥有独立的作用域括号前的符号会对括号内整体求值结果取反或保持必须借助栈来保存外层上下文。下面分别讲解仓库中给出的两种解法calculate与calculate1两者的完整实现均位于 224. Basic Calculator.go。解法一单栈扫描与符号位跟踪calculate是本仓库的主推解法整体只对字符串做一趟从左到右的扫描用一个栈保存括号前的计算结果与符号状态核心代码位于 224. Basic Calculator.go#L10-L41。func calculate(s string) int { i, stack, result, sign : 0, list.New(), 0, 1 // 记录加减状态 for i len(s) { if s[i] { i } else if s[i] 9 s[i] 0 { // 获取一段数字 base, v : 10, int(s[i]-0) for i1 len(s) s[i1] 9 s[i1] 0 { v v*base int(s[i1]-0) i } result v * sign i } else if s[i] { sign 1 i } else if s[i] - { sign -1 i } else if s[i] ( { // 把之前计算结果及加减状态压栈开始新的计算 stack.PushBack(result) stack.PushBack(sign) result 0 sign 1 i } else if s[i] ) { // 新的计算结果 * 前一个加减状态 之前计算结果 result result*stack.Remove(stack.Back()).(int) stack.Remove(stack.Back()).(int) i } } return result }四个核心状态变量作用result当前作用域内已经累积的求值结果sign当前符号位1代表加、-1代表减默认初始为1stack用container/list实现的双向链表栈保存进入括号前的result与signi扫描指针逐字符处理的五种情况空格i直接跳过不参与任何计算数字题目允许非负整数且可能为多位数因此内层for循环持续向后拼接每一位v v*10 digit直到遇到非数字字符为止得到完整数值后乘以当前sign累加到result将sign置为1-将sign置为-1。这两个分支使得负负得正天然成立——连续两个减号时第二个减号把sign从-1翻回1(说明进入新的括号作用域。先把当前result与sign依次压栈保存注意压栈顺序弹出时先取到的是sign然后把result归零、sign重置为1开始计算括号内的表达式)括号内计算完毕此时栈顶是进入该括号前压入的sign再往下一层是之前的result。新的result 括号内结果 × 外层符号 外层结果正是括号前减号对整体取反的实现关键。仍以示例2-(5-6)为例推演计算完2后遇到-sign -1遇到(时将result 2与sign -1压栈括号内5 - 6得到result -1遇到)时执行-1 × (-1) 2 3与测试期望一致。复杂度分析时间复杂度每个字符至多被扫描一次数字拼接与栈操作均为常数时间整体为 O(n)n 为字符串长度空间复杂度栈中最多保存嵌套括号层数对应的(result, sign)二元组最坏为 O(n)。解法二字节栈与括号子串化简calculate1提供了另一种思路先把整个表达式按字符压入一个[]byte栈遇到)时取出最近一对括号之间的子串交给calculateStr求值后再把数值结果回填到栈中最终对整个化简后的字符串再求一次值。实现位于 224. Basic Calculator.go#L44-L68。func calculate1(s string) int { stack : []byte{} for i : 0; i len(s); i { if s[i] { continue } else if s[i] ) { tmp, index : , len(stack)-1 for ; index 0; index-- { if stack[index] ( { break } } tmp string(stack[index1:]) stack stack[:index] res : strconv.Itoa(calculateStr(tmp)) for j : 0; j len(res); j { stack append(stack, res[j]) } } else { stack append(stack, s[i]) } } fmt.Printf(stack %v\n, string(stack)) return calculateStr(string(stack)) }其工作流程可以概括为三步扫描字符串空格直接丢弃其余字符数字、运算符、括号依次入栈遇到)时从栈顶向下找到最近的(将两者之间的子串取出并清空到(位置调用calculateStr求出该子表达式的整数值再通过strconv.Itoa转为数字字符回填进栈。这样最内层括号被化简为一个数字全部括号化简完毕后对剩余字符串再调用一次calculateStr得到最终答案。calculateStr连续符号合并与顺序求值子表达式求值函数calculateStr位于 224. Basic Calculator.go#L70-L112它把求值拆成两个阶段。第一阶段合并连续符号。由于括号化简后可能出现2-3、2--3这类连续运算符原文档解题思路中特别点名的负负得正情况代码用一个小栈s做符号规约连续符号组合规约结果保留得--变为--得-、-变为-第二阶段数字与符号分离。借助isDigital辅助函数224. Basic Calculator.go#L114-L118识别数字区间把表达式切分为独立的数字序列nums与符号序列s然后从nums[0]出发按符号顺序依次加减得出结果。复杂度分析与适用说明该解法每次遇到)都会对被截取的子串调用calculateStr重新扫描对于2-(3-(4-1))这类深层嵌套输入内层子串会被反复扫描与回填最坏时间复杂度为 O(n²)从源码结构看calculate1与calculateStr内部保留了fmt.Printf调试输出如stack %v、s %v nums %v res %v运行测试时会在终端打印中间过程更适合作为理解求值流程的教学示例而解法一calculate更适合作为实际提交的简洁方案。测试用例与验证仓库为本题提供了完整测试位于 224. Basic Calculator_test.go。Test_Problem224覆盖了以下用例输入期望输出考察点1 12基本加法、空格 2-1 2 3首尾空格与混合加减(1(452)-3)(68)23多层括号嵌套2-(5-6)3括号前减号负负得正100 23 - 12111多位整数2-(3-(4-1))3深层嵌套与符号翻转此外测试末尾还针对calculateStr的连续符号合并分支补充了一组健壮性用例仅对calculate1断言23 → 5、2(0-3) → -1、2-3 → -1、2-(0-3) → 5分别覆盖了、-、-、--四种规约路径保证符号合并逻辑无遗漏。如何运行测试在仓库根目录执行单题测试go test -v ./leetcode/0224.Basic-Calculator/该仓库基于 Go 1.19见 go.modmodule 名为github.com/halfrost/LeetCode-Go所有题解统一放置于leetcode/目录。若想全量回归并生成覆盖率报告可使用仓库自带的 gotest.shbash gotest.sh脚本会对./leetcode/...以-covermodeatomic模式一次性生成合法的coverage.txt这也是本项目宣称 100% 测试覆盖率所依赖的验证方式。小结Basic Calculator 是理解栈 状态位求解表达式类问题的绝佳范本解法一用sign符号位配合单栈一趟扫描把括号、空格、负数三种干扰统一处理时间 O(n)、空间 O(n)解法二则用字节栈逐步化简括号子串直观但最坏 O(n²)。结合仓库中 题目文档 与 测试用例你可以对照示例逐行验证两种实现的行为差异并由此举一反三迁移到 227. Basic Calculator II、772 等扩展题型的*、/与一元负号处理上。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考