Implement basic expression evaluator
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement a function to evaluate a string expression containing non-negative integers, '+', '-', '*', '/', and spaces. Multiplication and division have higher precedence than addition and subtraction, and division truncates toward zero. Parentheses are not allowed. Do not use any built-in eval. Handle long inputs efficiently and document time and space complexity.
Quick Answer: This question evaluates proficiency in expression parsing, operator precedence handling, integer arithmetic semantics (including truncating division), and efficient tokenization and evaluation within the Coding & Algorithms domain.
Implement a function `evaluate` that evaluates a string expression containing non-negative integers, the operators `+`, `-`, `*`, `/`, and spaces. Multiplication and division have higher precedence than addition and subtraction. Integer division truncates toward zero. Parentheses are NOT allowed, and you may not use any built-in `eval`. The input is guaranteed to be a valid expression that fits in a 32-bit signed integer at every intermediate step.
Example 1:
Input: s = "3+2*2"
Output: 7
Example 2:
Input: s = " 3/2 "
Output: 1
Example 3:
Input: s = " 3+5 / 2 "
Output: 5
Constraints
- 1 <= s.length <= 3 * 10^5
- s consists of non-negative integers and the characters '+', '-', '*', '/', and ' '.
- s represents a valid expression.
- All intermediate values fit in a signed 32-bit integer.
- The integer division truncates toward zero.
- Parentheses are not allowed; do not use any built-in eval.
Examples
Input: "3+2*2"
Expected Output: 7
Explanation: 2*2=4 binds tighter than +, so 3+4=7.
Input: " 3/2 "
Expected Output: 1
Explanation: Spaces are ignored; 3/2 truncates to 1.
Hints
- Track a running operator (start as '+') and accumulate the current number digit by digit. Apply the operator when you hit the next operator or the end of the string.
- Use a stack: for '+' push +num, for '-' push -num. For '*' and '/', pop the top value and combine immediately — that resolves the higher precedence on the fly.
- The final answer is just the sum of everything left on the stack — no second pass needed.
- For truncate-toward-zero division with negatives on the stack, divide magnitudes and re-apply the sign (Python's // floors, so handle the sign explicitly).