Problem Description

Implement a basic arithmetic expression evaluator that computes the value of a given mathematical expression string.

Input

The input is a string s representing a mathematical expression.

Details and Assumptions

• The expression string s will only contain:
  • Non-negative integers in base 10, which may consist of multiple digits.
  • The arithmetic operators: '+', '-', '*', and '/'.
  • Space characters ' ', which should be ignored during evaluation.
• The input expression is guaranteed to be syntactically valid; there will be no malformed input or division by zero scenarios.
• Standard operator precedence rules apply: multiplication ('*') and division ('/') have higher precedence than addition ('+') and subtraction ('-').
• Operators of the same precedence are evaluated from left to right (left-associative).
• Division operations should perform integer division, truncating the result toward zero.
• The input expression will not contain parentheses.

Output

Return the computed integer value of the expression. The result is guaranteed to fit within a 32-bit signed integer.

Constraints

• The length of the input string s will be between 1 and 100,000 characters, inclusive.
• The solution should aim for a time complexity of O(n), where n is the length of s.
• The solution should aim for an extra space complexity of O(1) or O(n) (excluding the input string itself).

Examples

Example 1:

• Input: "3+2*2"
• Output: 7
• Explanation: 2*2 = 4, then 3 + 4 = 7.

Example 2:

• Input: " 14-3/2 "
• Output: 13
• Explanation: 3/2 truncates toward zero and becomes 1, so 14 - 1 = 13.

Example 3:

• Input: "100/10*3+5"
• Output: 35
• Explanation: 100/10 = 10, 10*3 = 30, then 30 + 5 = 35.