Basic Calculator II
Medium · Math · Math · String · Stack
Problem
You are given a string s holding a valid arithmetic expression made of non-negative integers, the operators +, -, *, /, and spaces. There are no parentheses.
Evaluate the expression and return its integer value. Use normal precedence (* and / before + and -, left to right within a level), and make integer division truncate toward zero.
Do not use a built-in eval. Every intermediate result fits in a signed 32-bit integer.
Examples
Input: s = "2+3*4" Output: 14
Multiplication first: 2 + 12 = 14.
Input: s = " 14 / 3 - 1 " Output: 3
14 / 3 truncates to 4, then 4 - 1 = 3.
Input: s = "10-6/4*3" Output: 7
6 / 4 = 1, times 3 is 3, and 10 - 3 = 7.
Constraints
- 1 <= len(s) <= 3 · 10^5
- s contains digits, '+', '-', '*', '/' and ' '
- s is a valid expression
- Every integer in s is in [0, 2^31 - 1]
- Every intermediate result fits in a signed 32-bit integer
Approaches
- Baseline: tokenize, then collapse * and / one at a time — time O(n²), space O(n)
Follow-up
Add parentheses and unary minus, and the single pass needs a stack again: save the running sum and sign when a "(" opens, and fold the inner value back in at ")". That is the other calculator problem.
Related problems
Start free on Cariara · Coding problems · System design studio
