Basic Calculator

Difficulty: Medium

Problem

Given a string s which represents an expression, evaluate this expression and return its value. The integer division should truncate toward zero. The expression contains non-negative integers and operators '+', '-', '*', '/' with optional spaces. You may not use any built-in function which evaluates strings as mathematical expressions.

Example

Input: s = "3+2*2"
Output: 7
Explanation: Multiplication has higher precedence: 2*2=4, then 3+4=7.

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)