DSA problem
Basic Calculator II
Given a string s which represents an expression, evaluate this expression and return its value. The integer division should truncate toward zero. You may assume that the given expression is always valid. All intermediate results will be in the range of [-2^31, 2^31 - 1].
s consists of integers and operators +, -, *, / separated by some number of spaces. Notice the important distinction from "Basic Calculator I": this problem has * and / but no parentheses. The challenge is correctly handling operator precedence — multiplication and division must be applied before addition and subtraction.
A clean recursive-descent parser would work, but a single-pass stack-based approach is simpler and faster. The trick is to remember the previous operator and the current number. As you scan the string and parse a complete number, you decide what to do with it based on the previous operator. If the previous operator was + or -, you push the number (with a sign for -) onto a stack; you don't sum it in yet, because a later * or / could attach to it. If the previous operator was * or /, you pop the top of the stack, apply the operator with the current number, and push the result back, so that the chain of *// is folded immediately.
After the scan, the stack contains numbers that should just be summed (since multiplication and division have all been resolved into the stack values). Returning the sum of the stack is the answer. This runs in O(n) time and O(n) space.
Examples
s = "3+2*2"7s = " 3/2 "1s = " 3+5 / 2 "5Constraints
- 1 <= s.length <= 3 * 10^5
- s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
- s represents a valid expression.
- All the integers in the expression are non-negative integers in the range [0, 2^31 - 1].
- The answer is guaranteed to fit in a 32-bit integer.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.