Skip to main content

224. Basic Calculator

hard

Evaluate a math string with +, -, parentheses, and non-negative integers — without calling eval. The classic stack-based approach handles nested parens with sign tracking.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation. Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Constraints

  • 1 <= s.length <= 3 * 10^5
  • s consists of digits, '+', '-', '(', ')', and ' '.
  • s represents a valid expression.
  • '+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
  • '-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
  • There will be no two consecutive operators in the input.
  • Every number and running calculation will fit in a signed 32-bit integer.

Examples

Example 1

Input
s = "1 + 1"
Output
2

Example 2

Input
s = " 2-1 + 2 "
Output
3

Example 3

Input
s = "(1+(4+5+2)-3)+(6+8)"
Output
23

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Walk the string. Maintain a running result and a current sign (+1 or -1).

Hint 2

On a digit, parse the full number (consume consecutive digits), multiply by sign, add to result.

Hint 3

On '(', push the current result and sign onto a stack, then reset result to 0 and sign to +1 for the nested expression.

Hint 4

On ')', pop the saved sign and multiply it into the current result, then add the popped previous result. On '+' or '-', update sign.

Solution approach

Reveal approach

Single-pass with a stack of (result, sign) pairs. Maintain current result = 0 and current sign = +1. Walk the string: if digit, parse the full number and add (sign * number) to result. If '+', set sign = +1. If '-', set sign = -1. If '(', push (result, sign) onto the stack, reset result = 0 and sign = +1 — start a fresh sub-evaluation. If ')', the current result is the sub-expression's value; pop (prev_result, prev_sign) and set result = prev_result + prev_sign * result. Skip whitespace. After the loop, result holds the final value. O(n) time, O(n) space for the stack on deeply nested input.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • stack
  • math
  • string-scan

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft
  • Apple

Practice these live with InterviewChamp.AI

Drill Basic Calculator and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →