LeetCode 227: Basic Calculator II (Single Pass + Last-Term Folding)
LeetCode 227ParsingStackToday we solve LeetCode 227 - Basic Calculator II.
Source: https://leetcode.com/problems/basic-calculator-ii/
English
Problem Summary
Given a string expression s containing non-negative integers, spaces, and operators +, -, *, /, evaluate it and return the integer result. Division truncates toward zero.
Key Insight
* and / have higher precedence than + and -. We can scan once and keep a stack of signed terms:
- On + or -, push current number as a new term.
- On * or /, pop the last term, combine with current number, then push back.
- At the end, sum all terms.
This naturally enforces operator precedence without building an AST.
Algorithm
1. Initialize stack, num = 0, and sign = '+'.
2. Iterate characters of s from left to right.
3. If digit, update num = num * 10 + digit.
4. If current char is an operator (or we reached end), apply previous sign to num:
- '+': push num
- '-': push -num
- '*': push stack.pop() * num
- '/': push truncateTowardZero(stack.pop() / num)
5. Set sign to current operator and reset num = 0.
6. Return the sum of stack.
Complexity Analysis
Let n be the length of s.
Time: O(n).
Space: O(n) in the worst case (all +/- terms).
Common Pitfalls
- Forgetting to process the last number at end-of-string.
- Treating integer division as floor for negatives instead of truncation toward zero.
- Ignoring spaces while parsing.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int calculate(String s) {
java.util.ArrayDeque<Integer> stack = new java.util.ArrayDeque<>();
int num = 0;
char sign = '+';
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
}
if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
if (sign == '+') stack.push(num);
else if (sign == '-') stack.push(-num);
else if (sign == '*') stack.push(stack.pop() * num);
else stack.push(stack.pop() / num); // truncates toward zero in Java
sign = c;
num = 0;
}
}
int ans = 0;
while (!stack.isEmpty()) ans += stack.pop();
return ans;
}
}func calculate(s string) int {
stack := make([]int, 0)
num := 0
sign := byte('+')
apply := func(op byte, x int) {
n := len(stack)
switch op {
case '+':
stack = append(stack, x)
case '-':
stack = append(stack, -x)
case '*':
stack[n-1] = stack[n-1] * x
case '/':
stack[n-1] = stack[n-1] / x // truncates toward zero in Go
}
}
for i := 0; i < len(s); i++ {
c := s[i]
if c >= '0' && c <= '9' {
num = num*10 + int(c-'0')
}
if (c < '0' || c > '9') && c != ' ' || i == len(s)-1 {
apply(sign, num)
sign = c
num = 0
}
}
ans := 0
for _, v := range stack {
ans += v
}
return ans
}class Solution {
public:
int calculate(string s) {
vector<int> st;
long num = 0;
char sign = '+';
for (int i = 0; i < (int)s.size(); ++i) {
char c = s[i];
if (isdigit(c)) {
num = num * 10 + (c - '0');
}
if ((!isdigit(c) && c != ' ') || i == (int)s.size() - 1) {
if (sign == '+') st.push_back((int)num);
else if (sign == '-') st.push_back(-(int)num);
else if (sign == '*') st.back() = st.back() * (int)num;
else st.back() = st.back() / (int)num; // truncates toward zero in C++
sign = c;
num = 0;
}
}
int ans = 0;
for (int x : st) ans += x;
return ans;
}
};class Solution:
def calculate(self, s: str) -> int:
stack = []
num = 0
sign = '+'
for i, c in enumerate(s):
if c.isdigit():
num = num * 10 + int(c)
if (not c.isdigit() and c != ' ') or i == len(s) - 1:
if sign == '+':
stack.append(num)
elif sign == '-':
stack.append(-num)
elif sign == '*':
stack[-1] = stack[-1] * num
else:
stack[-1] = int(stack[-1] / num) # truncates toward zero
sign = c
num = 0
return sum(stack)var calculate = function(s) {
const stack = [];
let num = 0;
let sign = '+';
const isDigit = (c) => c >= '0' && c <= '9';
for (let i = 0; i < s.length; i++) {
const c = s[i];
if (isDigit(c)) {
num = num * 10 + (c.charCodeAt(0) - 48);
}
if ((!isDigit(c) && c !== ' ') || i === s.length - 1) {
if (sign === '+') stack.push(num);
else if (sign === '-') stack.push(-num);
else if (sign === '*') stack[stack.length - 1] *= num;
else stack[stack.length - 1] = Math.trunc(stack[stack.length - 1] / num);
sign = c;
num = 0;
}
}
return stack.reduce((a, b) => a + b, 0);
};中文
题目概述
给定一个表达式字符串 s，包含非负整数、空格和运算符 +、-、*、/，返回计算结果。除法要求向 0 截断。
核心思路
因为 *、/ 优先级高于 +、-，可以用“单次扫描 + 项栈”处理：
- 遇到 +/-：把当前数字作为新项入栈（正或负）。
- 遇到 *//：拿栈顶和当前数字先算完，再把结果放回栈顶。
- 最后把栈中所有项求和。
算法步骤
1）初始化栈、num = 0、sign = '+'。
2）从左到右扫描字符串。
3）若是数字，执行 num = num * 10 + digit。
4）若遇到运算符（或到达末尾），按“上一个 sign”处理当前 num：
- '+'：入栈 num
- '-'：入栈 -num
- '*'：栈顶变为 栈顶 * num
- '/'：栈顶变为 truncateTowardZero(栈顶 / num)
5）更新 sign 为当前运算符，重置 num = 0。
6）最终返回栈内元素之和。
复杂度分析
设字符串长度为 n。
时间复杂度：O(n)。
空间复杂度：O(n)（最坏情况下每个项都入栈）。
常见陷阱
- 忘记在字符串末尾触发最后一个数字的结算。
- 对负数除法错误地用“向下取整”而不是“向 0 截断”。
- 解析时没有正确跳过空格。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int calculate(String s) {
java.util.ArrayDeque<Integer> stack = new java.util.ArrayDeque<>();
int num = 0;
char sign = '+';
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
}
if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
if (sign == '+') stack.push(num);
else if (sign == '-') stack.push(-num);
else if (sign == '*') stack.push(stack.pop() * num);
else stack.push(stack.pop() / num);
sign = c;
num = 0;
}
}
int ans = 0;
while (!stack.isEmpty()) ans += stack.pop();
return ans;
}
}func calculate(s string) int {
stack := make([]int, 0)
num := 0
sign := byte('+')
apply := func(op byte, x int) {
n := len(stack)
switch op {
case '+':
stack = append(stack, x)
case '-':
stack = append(stack, -x)
case '*':
stack[n-1] = stack[n-1] * x
case '/':
stack[n-1] = stack[n-1] / x
}
}
for i := 0; i < len(s); i++ {
c := s[i]
if c >= '0' && c <= '9' {
num = num*10 + int(c-'0')
}
if (c < '0' || c > '9') && c != ' ' || i == len(s)-1 {
apply(sign, num)
sign = c
num = 0
}
}
ans := 0
for _, v := range stack {
ans += v
}
return ans
}class Solution {
public:
int calculate(string s) {
vector<int> st;
long num = 0;
char sign = '+';
for (int i = 0; i < (int)s.size(); ++i) {
char c = s[i];
if (isdigit(c)) {
num = num * 10 + (c - '0');
}
if ((!isdigit(c) && c != ' ') || i == (int)s.size() - 1) {
if (sign == '+') st.push_back((int)num);
else if (sign == '-') st.push_back(-(int)num);
else if (sign == '*') st.back() = st.back() * (int)num;
else st.back() = st.back() / (int)num;
sign = c;
num = 0;
}
}
int ans = 0;
for (int x : st) ans += x;
return ans;
}
};class Solution:
def calculate(self, s: str) -> int:
stack = []
num = 0
sign = '+'
for i, c in enumerate(s):
if c.isdigit():
num = num * 10 + int(c)
if (not c.isdigit() and c != ' ') or i == len(s) - 1:
if sign == '+':
stack.append(num)
elif sign == '-':
stack.append(-num)
elif sign == '*':
stack[-1] = stack[-1] * num
else:
stack[-1] = int(stack[-1] / num)
sign = c
num = 0
return sum(stack)var calculate = function(s) {
const stack = [];
let num = 0;
let sign = '+';
const isDigit = (c) => c >= '0' && c <= '9';
for (let i = 0; i < s.length; i++) {
const c = s[i];
if (isDigit(c)) {
num = num * 10 + (c.charCodeAt(0) - 48);
}
if ((!isDigit(c) && c !== ' ') || i === s.length - 1) {
if (sign === '+') stack.push(num);
else if (sign === '-') stack.push(-num);
else if (sign === '*') stack[stack.length - 1] *= num;
else stack[stack.length - 1] = Math.trunc(stack[stack.length - 1] / num);
sign = c;
num = 0;
}
}
return stack.reduce((a, b) => a + b, 0);
};
Comments