Basic Calculator

Difficulty: Medium

Problem

Basic Calculator II (no parentheses): a string s holds an arithmetic expression made of non-negative integers, the operators '+', '-', '*', '/', and possibly some spaces. Compute and return its value, with division discarding any fractional part (rounding toward zero), so 0-9/2 is -4. The expression is valid, there is no division by zero, and every intermediate result fits in a 32-bit integer. An empty or all-space string is worth 0. Do not use any built-in that evaluates a string as an expression.

Example

Input: s = "10-4*3+9/2"
Output: 2
Explanation: Do the high-precedence work first: 4*3=12 and 9/2=4 (the fraction is dropped). That leaves 10-12+4, which equals 2.

Brute-force approach

Parse the expression into tokens (numbers and operators). First pass: handle * and /. Second pass: handle + and -.

Steps

  1. Parse expression into tokens list
  2. First pass: find and evaluate all * and / operations
  3. Second pass: evaluate all + and - operations
  4. Return the final result

Time complexity: O(n²) · Space complexity: O(n)

Trade-offs

  • Array manipulation (splicing/shifting) for each evaluation is O(n): every replace shifts the rest of the list
  • May need up to n/2 passes of n looks each (15 looks on 10-4*3+9/2) → O(n²) total
  • Complex token management with shifting indices

Optimal approach

Key insight: Handle higher precedence (*/) immediately by computing with the stack top. Defer lower precedence (+/-) by pushing to the stack. Final sum gives the answer.

Single pass with a stack: build multi-digit numbers, apply * and / immediately with the stack top, and push +/- numbers for later summation.

Steps

  1. Initialize stack=[], num=0, op='+' (the operator waiting before num)
  2. For each character of s + '+' (the extra '+' is an end mark):
  3. If digit: num = num*10 + digit
  4. If an operator or the end mark (not a space): apply op to num with stack, reset num, set op to this character
  5. Return sum of stack

Time complexity: O(n) · Space complexity: O(n)

Pseudocode

function calculate(s):
    stack = []
    num = 0
    op = '+'          // the operator waiting before num
    
    for each ch in s + '+':       // the extra '+' is an end mark
        if ch is a digit:
            num = num * 10 + int(ch)
        else if ch is not ' ':    // an operator, or the end mark
            if op == '+': stack.push(num)
            if op == '-': stack.push(-num)
            if op == '*': stack.push(stack.pop() * num)
            if op == '/': stack.push(trunc(stack.pop() / num))
            op = ch
            num = 0
    
    return sum(stack)

Hints

  • Process * and / immediately when encountered (they have higher precedence)
  • For + and -, push the number onto the stack (with sign) to be summed later
  • Track the operator that waited before the number (call it op) to know what to do with the current number
  • Handle multi-digit numbers by building num = num * 10 + digit
  • The sign belongs to the whole term: in 1-8/3*2 the minus applies to 8/3*2, not just to the 8, so push -8 and let the / and * change that top box
  • The top of the stack is the term the next * or / belongs to
  • The last number has no operator after it: loop over s + '+' (an end mark) so it is finished too, even when the string ends with spaces

Complexity questions

What is the time complexity of the two-pass approach with array modifications?

O(n²). Each evaluation involves array splicing (O(n)), and we may need O(n) evaluations → O(n²).

What is the time complexity of the stack approach?

O(n). Single pass through the string, O(1) per character. Summing the stack at the end is O(n). Total: O(n).

What is the space used by the stack in the worst case?

O(n). In the worst case (all + or - operations), every number is pushed → O(n) stack space.

Check your understanding of Basic Calculator

What is the expected result of '3+2*2'?

7 (multiplication first: 2*2=4, then 3+4=7). Standard math precedence: * and / are evaluated before + and -. So 2*2=4 first, then 3+4=7.

In the expression '14-3/2', what is the expected result?

13 (3/2=1, then 14-1=13). Division has higher precedence than subtraction. 3/2=1 (truncated toward zero), then 14-1=13.

What should '42' (a single number with no operators) evaluate to?

42 (the number itself). A single number with no operators is a valid expression. It simply evaluates to itself: 42.

Related problems

Keep practising