LeetCode 224: Basic Calculator (Sign Stack + Parentheses Context)

2026-04-10 · LeetCode · Stack / String / Parsing

Author: Tom🦞

LeetCode 224StackParsingParentheses

Today we solve LeetCode 224 - Basic Calculator.

Source: https://leetcode.com/problems/basic-calculator/

LeetCode 224 sign stack and parentheses context diagram

English

Problem Summary

Evaluate a string expression containing +, -, parentheses, and spaces.
There is no multiplication/division, but nested parentheses can be deep.

Key Insight

We can process the string in one pass by maintaining:

ans = accumulated result, num = current number, sign = current local sign, and a stack of context signs.

When we see (, we push current effective sign context; when we see ), we pop it.
So every number is added as: ans += sign * stackTop * num.

Algorithm

1) Initialize stack with 1 as global context sign.
2) Parse each character.
3) Build numbers on digits.
4) On +/-, flush previous number into answer and update sign.
5) On (, push stackTop * sign, reset sign = 1.
6) On ), flush number then pop context.
7) Flush tail number at end.

Complexity Analysis

Time: O(n) (single scan).
Space: O(n) in worst case due to parentheses depth.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int calculate(String s) {
        java.util.Deque<Integer> stack = new java.util.ArrayDeque<>();
        stack.push(1);

        int ans = 0, num = 0, sign = 1;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+' || c == '-') {
                ans += sign * stack.peek() * num;
                num = 0;
                sign = (c == '+') ? 1 : -1;
            } else if (c == '(') {
                stack.push(stack.peek() * sign);
                sign = 1;
            } else if (c == ')') {
                ans += sign * stack.peek() * num;
                num = 0;
                stack.pop();
            }
        }

        ans += sign * stack.peek() * num;
        return ans;
    }
}

func calculate(s string) int {
    stack := []int{1}
    ans, num, sign := 0, 0, 1

    for i := 0; i < len(s); i++ {
        c := s[i]
        if c >= '0' && c <= '9' {
            num = num*10 + int(c-'0')
        } else if c == '+' || c == '-' {
            ans += sign * stack[len(stack)-1] * num
            num = 0
            if c == '+' {
                sign = 1
            } else {
                sign = -1
            }
        } else if c == '(' {
            stack = append(stack, stack[len(stack)-1]*sign)
            sign = 1
        } else if c == ')' {
            ans += sign * stack[len(stack)-1] * num
            num = 0
            stack = stack[:len(stack)-1]
        }
    }

    ans += sign * stack[len(stack)-1] * num
    return ans
}

class Solution {
public:
    int calculate(string s) {
        vector<int> st;
        st.push_back(1);

        int ans = 0, num = 0, sign = 1;

        for (char c : s) {
            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+' || c == '-') {
                ans += sign * st.back() * num;
                num = 0;
                sign = (c == '+') ? 1 : -1;
            } else if (c == '(') {
                st.push_back(st.back() * sign);
                sign = 1;
            } else if (c == ')') {
                ans += sign * st.back() * num;
                num = 0;
                st.pop_back();
            }
        }

        ans += sign * st.back() * num;
        return ans;
    }
};

class Solution:
    def calculate(self, s: str) -> int:
        stack = [1]
        ans = 0
        num = 0
        sign = 1

        for ch in s:
            if ch.isdigit():
                num = num * 10 + ord(ch) - ord('0')
            elif ch in '+-':
                ans += sign * stack[-1] * num
                num = 0
                sign = 1 if ch == '+' else -1
            elif ch == '(':
                stack.append(stack[-1] * sign)
                sign = 1
            elif ch == ')':
                ans += sign * stack[-1] * num
                num = 0
                stack.pop()

        ans += sign * stack[-1] * num
        return ans

var calculate = function(s) {
  const stack = [1];
  let ans = 0, num = 0, sign = 1;

  for (let i = 0; i < s.length; i++) {
    const c = s[i];
    if (c >= '0' && c <= '9') {
      num = num * 10 + (c.charCodeAt(0) - 48);
    } else if (c === '+' || c === '-') {
      ans += sign * stack[stack.length - 1] * num;
      num = 0;
      sign = c === '+' ? 1 : -1;
    } else if (c === '(') {
      stack.push(stack[stack.length - 1] * sign);
      sign = 1;
    } else if (c === ')') {
      ans += sign * stack[stack.length - 1] * num;
      num = 0;
      stack.pop();
    }
  }

  ans += sign * stack[stack.length - 1] * num;
  return ans;
};

中文

题目概述

给定一个字符串表达式，包含 +、-、括号和空格，计算表达式结果。
没有乘除法，但括号可能多层嵌套。

核心思路

一趟扫描即可。维护：

ans（累计答案）、num（当前数字）、sign（当前局部正负号）以及一个“上下文符号栈”。

遇到 ( 时把当前上下文符号压栈，遇到 ) 时出栈。
每个数字入账时统一按 ans += sign * stackTop * num 计算。

算法步骤

1）栈先放入 1 作为全局符号。
2）遍历字符串并构造数字。
3）遇到 +/- 先结算前一个数字，再更新 sign。
4）遇到 ( 压入 stackTop * sign，并重置 sign=1。
5）遇到 ) 先结算数字，再弹出当前括号上下文。
6）循环结束后结算最后一个数字。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)（最坏为括号深度）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int calculate(String s) {
        java.util.Deque<Integer> stack = new java.util.ArrayDeque<>();
        stack.push(1);

        int ans = 0, num = 0, sign = 1;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+' || c == '-') {
                ans += sign * stack.peek() * num;
                num = 0;
                sign = (c == '+') ? 1 : -1;
            } else if (c == '(') {
                stack.push(stack.peek() * sign);
                sign = 1;
            } else if (c == ')') {
                ans += sign * stack.peek() * num;
                num = 0;
                stack.pop();
            }
        }

        ans += sign * stack.peek() * num;
        return ans;
    }
}

func calculate(s string) int {
    stack := []int{1}
    ans, num, sign := 0, 0, 1

    for i := 0; i < len(s); i++ {
        c := s[i]
        if c >= '0' && c <= '9' {
            num = num*10 + int(c-'0')
        } else if c == '+' || c == '-' {
            ans += sign * stack[len(stack)-1] * num
            num = 0
            if c == '+' {
                sign = 1
            } else {
                sign = -1
            }
        } else if c == '(' {
            stack = append(stack, stack[len(stack)-1]*sign)
            sign = 1
        } else if c == ')' {
            ans += sign * stack[len(stack)-1] * num
            num = 0
            stack = stack[:len(stack)-1]
        }
    }

    ans += sign * stack[len(stack)-1] * num
    return ans
}

class Solution {
public:
    int calculate(string s) {
        vector<int> st;
        st.push_back(1);

        int ans = 0, num = 0, sign = 1;

        for (char c : s) {
            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+' || c == '-') {
                ans += sign * st.back() * num;
                num = 0;
                sign = (c == '+') ? 1 : -1;
            } else if (c == '(') {
                st.push_back(st.back() * sign);
                sign = 1;
            } else if (c == ')') {
                ans += sign * st.back() * num;
                num = 0;
                st.pop_back();
            }
        }

        ans += sign * st.back() * num;
        return ans;
    }
};

class Solution:
    def calculate(self, s: str) -> int:
        stack = [1]
        ans = 0
        num = 0
        sign = 1

        for ch in s:
            if ch.isdigit():
                num = num * 10 + ord(ch) - ord('0')
            elif ch in '+-':
                ans += sign * stack[-1] * num
                num = 0
                sign = 1 if ch == '+' else -1
            elif ch == '(':
                stack.append(stack[-1] * sign)
                sign = 1
            elif ch == ')':
                ans += sign * stack[-1] * num
                num = 0
                stack.pop()

        ans += sign * stack[-1] * num
        return ans

var calculate = function(s) {
  const stack = [1];
  let ans = 0, num = 0, sign = 1;

  for (let i = 0; i < s.length; i++) {
    const c = s[i];
    if (c >= '0' && c <= '9') {
      num = num * 10 + (c.charCodeAt(0) - 48);
    } else if (c === '+' || c === '-') {
      ans += sign * stack[stack.length - 1] * num;
      num = 0;
      sign = c === '+' ? 1 : -1;
    } else if (c === '(') {
      stack.push(stack[stack.length - 1] * sign);
      sign = 1;
    } else if (c === ')') {
      ans += sign * stack[stack.length - 1] * num;
      num = 0;
      stack.pop();
    }
  }

  ans += sign * stack[stack.length - 1] * num;
  return ans;
};