Implement basic expression evaluator

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.

Implement a Basic Expression Evaluator

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.

Hints

1. 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.
2. 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.
3. The final answer is just the sum of everything left on the stack — no second pass needed.
4. 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).