LeetCode 224 基本计算器｜Go 切片模拟栈解题

题目回顾给你一个字符串表达式s实现基本计算器返回计算结果。 约束表达式包含数字、、-、(、)、空格-可以做一元负号不会作为一元运算符不能调用 eval 之类内置表达式计算函数表达式合法长度最大 3*10^5需要高效解法输入s (1(452)-3)(68) 输出23难点括号嵌套括号会改变后面所有数字的正负号还有多位数解析、空格跳过、一元负号。思路符号栈解法不用把表达式转后缀这道题只有加减本质所有运算都是数字 × 符号然后累加总和。 括号的作用括号内部所有数字的整体符号被括号前的正负影响。核心思想res保存最终累加结果sign当前数字的符号1 /-1栈 stack切片实现专门保存括号带来的全局符号遇到(把当前的sign压入栈代表括号内部所有数字要乘上这个符号遇到)弹出栈顶回到括号外面的符号环境当前符号 栈顶符号-当前符号 - 栈顶符号Go 实现栈约定切片模拟栈入栈stack append(stack, val)取栈顶stack[len(stack)-1]出栈stack stack[:len(stack)-1]判空len(stack) 0初始状态stack [1]默认全局正号。完整 Go 代码func calculate(s string) int { // 切片模拟栈存储括号带来的符号 stack : make([]int, 0) stack append(stack, 1) // 初始全局符号为正1 res : 0 // 最终累加结果 sign : 1 // 当前数字的符号 for i : 0; i len(s); i { ch : s[i] switch ch { case : // 空格直接跳过 continue case : // 加号符号等于栈顶保存的全局符号 sign stack[len(stack)-1] case -: // 减号符号等于负的栈顶全局符号 sign -stack[len(stack)-1] case (: // 左括号把当前符号压栈括号内复用这个符号基准 stack append(stack, sign) case ): // 右括号弹出栈顶退出括号作用域 stack stack[:len(stack)-1] default: // 数字解析多位数 num : 0 for ; i len(s) s[i] 0 s[i] 9; i { num num*10 int(s[i]-0) } // for循环i会多走一步回退 i-- // 累加数字 * 当前符号 res sign * num } } return res }逐行拆解逻辑stack : make([]int,0); stackappend(stack,1)栈初始化压入1代表最外层没有括号的时候默认符号为正。遍历字符串每个字符遇到空格直接continue忽略。遇到当前符号取栈顶栈顶保存了当前括号层级的基准符号。遇到-当前符号取负的栈顶。比如-(12)(之前是-sign-1压栈括号内部所有数字都乘 - 1。遇到(把当前sign压入栈。括号里面所有的 -都会基于这个栈顶符号。遇到)栈切片截断弹出栈顶离开括号恢复上一层符号环境。遇到数字字符循环解析连续数字处理多位数例如123。内层 for 循环 i 会自增退出后 i 多走了一格需要i--回退。res sign * num把带符号的数字加到结果。举个例子推演-(12)-sign -stack[top]栈顶是 1 →sign-1(append(stack, -1)栈变成[1,-1]1res (-1)*1→ res-1sign stack[top] -12res (-1)*2→ res-3)弹出栈顶栈回到[1]最终返回-3结果正确。Go 切片模拟栈相关知识点栈操作Go 切片写法说明初始化空栈stack : make([]int,0)长度 0容量自动扩容入栈 pushstack append(stack, val)追加到切片尾部取栈顶 topstack[len(stack)-1]尾部元素就是栈顶注意栈不能为空出栈 popstack stack[:len(stack)-1]切片截断丢弃最后一个元素不会修改底层数组栈是否为空len(stack) 0判断长度注意stack[:len(stack)-1]只是切片视图截断底层数组不会立刻删除元素GoGC 自动回收算法刷题完全够用。易错点总结多位数解析后 i--内层 for 循环 i 持续 读完数字后 i 指向非数字字符外层循环还会 i如果不回退会跳过一个字符造成解析错误。栈初始一定要压入1不能用空栈否则取栈顶stack[len(stack)-1]会索引越界 panic。区分sign和栈存的值sign当前这个数字要用的正负栈存的是括号层级的基准符号括号嵌套的时候保存现场。处理一元负号例如-1-(32)这套逻辑天然支持一元负号不需要额外特殊判断这也是这个解法的巧妙之处。跳过空格不能漏掉空格 case否则会把空格当成未知字符进入数字分支。测试用例func main() { println(calculate(1 1)) // 2 println(calculate( 2-1 2 )) //3 println(calculate((1(452)-3)(68))) //23 println(calculate(- (3 (4 5)))) //-12 }复杂度分析时间复杂度 \(O(n)\)每个字符最多遍历两次数字内层循环 i 向前走不会重复遍历。n 是字符串长度。空间复杂度 \(O(n)\)最坏情况全是左括号栈存 n 个符号。适合题目 \(3*10^5\) 的大数据输入。补充其他思路对比这道题还有一种经典解法双栈数字栈 运算符栈把表达式转后缀表达式再计算。 但是双栈代码量大还要处理运算符优先级。本题只有加减符号栈解法更简洁高效。小结这道非常适合练习 Go 切片模拟栈。栈不只是存数字也可以存状态这里是正负符号遇到括号嵌套场景用栈保存现场退出括号再恢复现场是通用解题套路。