Basic Calculator

Difficulty: Medium

Problem

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). 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)
  • May need multiple passes → 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, prevSign='+'
  2. For each character (and at string end):
  3. If digit: num = num*10 + digit
  4. If operator or end: apply prevSign to num with stack, reset num, update prevSign
  5. Return sum of stack

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

Pseudocode

function calculate(s):
    stack = []
    num = 0
    sign = '+'
    
    for i = 0 to len(s)-1:
        if s[i] is digit:
            num = num * 10 + int(s[i])
        if (s[i] is operator or i == len(s)-1) and s[i] != ' ':
            if sign == '+': stack.push(num)
            if sign == '-': stack.push(-num)
            if sign == '*': stack.push(stack.pop() * num)
            if sign == '/': stack.push(trunc(stack.pop() / num))
            sign = s[i]
            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 'previous operator' to know what to do with the current number
  • Handle multi-digit numbers by building num = num * 10 + digit

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