AlgoViz Lab交互式算法学习Algorithms first
基本计算器 · 交互式算法学习
计算包含 +、-、括号和空格的表达式。
#224 · 栈
基本计算器
Basic Calculator
s = "(1+(4+5+2)-3)+(6+8)"栈 / 队列 / 堆3 个关键状态
步骤 1外层默认符号为 +1。
ops=[1]队首
(
1
+
(
4
+
5
+
2
)
-
3
)
+
(
6
+
8
)
队尾
推荐
符号上下文栈
时间
O(n)空间 O(括号深度)栈保存外层符号；每个数字乘当前有效符号后直接累加。
1function calculate(s) {2 let ans = 0,3 sign = 1,4 i = 0;5 const ops = [1];6 while (i < s.length) {7 if (s[i] === ' ') {8 i++;9 continue10 }11 if (s[i] === '+') {12 sign = ops.at(-1);13 i++;14 } else if (s[i] === '-') {15 sign = -ops.at(-1);16 i++;17 } else if (s[i] === '(') {18 ops.push(sign);19 i++;20 } else if (s[i] === ')') {21 ops.pop();22 i++;23 } else {24 let n = 0;25 while (i < s.length && /\d/.test(s[i])) n = n * 10 + +s[i++];26 ans += sign * n;27 }28 }29 return ans;30}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1class Solution {2 public int calculate(String s) {3 Deque<Integer> stk = new ArrayDeque<>();4 int sign = 1;5 int ans = 0;6 int n = s.length();7 for (int i = 0; i < n; ++i) {8 char c = s.charAt(i);9 if (Character.isDigit(c)) {10 int j = i;11 int x = 0;12 while (j < n && Character.isDigit(s.charAt(j))) {13 x = x * 10 + s.charAt(j) - '0';14 j++;15 }16 ans += sign * x;17 i = j - 1;18 } else if (c == '+') {19 sign = 1;20 } else if (c == '-') {21 sign = -1;22 } else if (c == '(') {23 stk.push(ans);24 stk.push(sign);25 ans = 0;26 sign = 1;27 } else if (c == ')') {28 ans = stk.pop() * ans + stk.pop();29 }30 }31 return ans;32 }33}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
基本计算器 · 解法对比
计算包含 +、-、括号和空格的表达式。
- 测试用例
s = "(1+(4+5+2)-3)+(6+8)"- 题目分类
- 栈
- 解法对比
- 2
递归下降解析
遇到左括号递归计算子表达式，右括号返回。
- 时间
O(n)- 空间
O(括号深度)
符号上下文栈
栈保存外层符号；每个数字乘当前有效符号后直接累加。
- 时间
O(n)- 空间
O(括号深度)