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 Sam K., 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

More Math practice problems

See all Math problems →