LeetCode 224困难栈
基本计算器 图解题解
这道题到底在问什么
只有加减和括号，没有乘除。括号可以任意嵌套，要算出和普通数学一样的结果。
- 输入
- s = "(1+(4+5+2)-3)+(6+8)"
- 输出
- 23
- 输入
- s = "1-( -2)"
- 输出
- 3
最优解：一步一步想明白
- 3括号 = “先把外面的进度存起来，进去单独算完再接回来”，这就是栈。
- 4上排是整条表达式（固定不变），下面竖着的是栈，里面存“括号外面没算完的进度”。
- 5碰到 ( ：把“外面算到一半的 result 和 sign”整对压进栈，括号里从 0 干净地重新算。
- 6第 1 个是数字 1，先攒着（num=1），等碰到符号或括号再结算。
- 7碰到 +：把刚攒好的数按当前符号加进 result，再用 + 决定下一个数是正还是负。
- 8碰到 ( ：把“外面算到一半的 result 和 sign”整对压进栈，括号里从 0 干净地重新算。
- 9第 4 个是数字 4，先攒着（num=4），等碰到符号或括号再结算。
- 10碰到 +：把刚攒好的数按当前符号加进 result，再用 + 决定下一个数是正还是负。
- 11第 6 个是数字 5，先攒着（num=5），等碰到符号或括号再结算。
- 12碰到 +：把刚攒好的数按当前符号加进 result，再用 + 决定下一个数是正还是负。
- 13第 8 个是数字 2，先攒着（num=2），等碰到符号或括号再结算。
- 14碰到 ) ：括号里这段算完了，弹出之前压的那对——括号值先乘上当时的符号，再加回当时的 result，进度就接上了。
- 15碰到 -：把刚攒好的数按当前符号加进 result，再用 - 决定下一个数是正还是负。
- 16第 11 个是数字 3，先攒着（num=3），等碰到符号或括号再结算。
- 17碰到 ) ：括号里这段算完了，弹出之前压的那对——括号值先乘上当时的符号，再加回当时的 result，进度就接上了。
- 18碰到 +：把刚攒好的数按当前符号加进 result，再用 + 决定下一个数是正还是负。
- 19碰到 ( ：把“外面算到一半的 result 和 sign”整对压进栈，括号里从 0 干净地重新算。
- 20第 15 个是数字 6，先攒着（num=6），等碰到符号或括号再结算。
- 21碰到 +：把刚攒好的数按当前符号加进 result，再用 + 决定下一个数是正还是负。
- 22第 17 个是数字 8，先攒着（num=8），等碰到符号或括号再结算。
- 23最后一个 ) 把括号值合并回来后，整条表达式的结果就是 23。
⚠️ 容易写错的地方
✗ 错：只压 result，忘了压 sign
✓ 对：括号外的符号必须一起存
"1-(2+3)" 里括号前是减号，弹栈时要乘 −1
✗ 错：遇 ) 直接弹栈，漏了结清括号内最后一段
✓ 对：先 result += sign*num 再弹栈
括号里最后一个数还没加进 result
✗ 错：弹栈顺序搞反
✓ 对：先弹的是 sign，后弹的是 result
压栈是先 result 后 sign，弹栈顺序正好相反
完整代码（Python / C++ / Java）
Python
def calculate(s: str) -> int:
result, sign, num = 0, 1, 0
stack = []
for c in s:
if c.isdigit():
num = num * 10 + int(c)
elif c in "+-":
result += sign * num
num = 0
sign = 1 if c == "+" else -1
elif c == "(":
stack.append(result); stack.append(sign)
result, sign = 0, 1
elif c == ")":
result += sign * num; num = 0
result *= stack.pop() # 栈顶 sign
result += stack.pop() # 栈顶 result
return result + sign * numC++
int calculate(string s){
long result=0; int sign=1; long num=0;
stack<long> st;
for(char c : s){
if(isdigit(c)) num = num*10 + (c-'0');
else if(c=='+' || c=='-'){
result += sign*num; num=0;
sign = (c=='+') ? 1 : -1;
} else if(c=='('){
st.push(result); st.push(sign);
result=0; sign=1;
} else if(c==')'){
result += sign*num; num=0;
result *= st.top(); st.pop(); // sign
result += st.top(); st.pop(); // result
}
}
return result + sign*num;
}Java
public int calculate(String s){
long result = 0; int sign = 1; long num = 0;
Deque<Long> st = new ArrayDeque<>();
for(char c : s.toCharArray()){
if(Character.isDigit(c)){
num = num * 10 + (c - '0');
} else if(c == '+' || c == '-'){
result += sign * num; num = 0;
sign = (c == '+') ? 1 : -1;
} else if(c == '('){
st.push(result); st.push((long) sign);
result = 0; sign = 1;
} else if(c == ')'){
result += sign * num; num = 0;
result *= st.pop(); // 栈顶 sign
result += st.pop(); // 栈顶 result
}
}
return (int)(result + sign * num);
}复杂度
时间
O(n)
每个字符只扫一次
空间
O(n)
最坏全是左括号，全压进栈
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 基本计算器 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么不直接转成逆波兰表达式再算？+
可以，但只有加减括号时没必要。用 result/sign/num 三变量加一个栈，一遍扫描就够，代码更短、常数更小。逆波兰更适合带乘除和优先级的通用表达式。
如果再加上乘除该怎么改？+
加减括号靠这个栈解决；乘除有更高优先级，通常再引入一个数字栈和一个运算符栈（或在遇到 * / 时立刻和栈顶数字结算），把优先级处理进去。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 基本计算器 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。