Practice/Flex/Leetcode 227. Basic Calculator II

Leetcode 227. Basic Calculator II

CodingMust

Problem

You are given a string representing a mathematical expression that contains non-negative integers and four basic operators: addition (+), subtraction (-), multiplication (*), and division (/). The string may contain spaces between characters.

Your task is to evaluate this expression and return the result as an integer. You must respect standard mathematical operator precedence rules: multiplication and division should be performed before addition and subtraction. Division should truncate toward zero (round down to the nearest integer).

You cannot use built-in evaluation functions like eval().

Requirements

1. Parse and evaluate the expression string correctly
2. Handle operator precedence (multiply and divide before add and subtract)
3. Process division as integer division that truncates toward zero
4. Ignore any whitespace characters in the input
5. Return the final result as an integer

Constraints

• 1 ≤ s.length ≤ 3 × 10⁵
• The string contains only digits, +, -, *, /, and space characters
• All intermediate results will fit in a 32-bit integer
• The expression is guaranteed to be valid
• There are no leading zeros in the numbers
• Time complexity target: O(n) where n is the length of the string
• Space complexity target: O(n) for storing intermediate values

Examples

Example 1:

Input: s = "3+2*2" Output: 7 Explanation: Multiplication is performed first (2*2=4), then addition (3+4=7)

Example 2:

Input: s = " 6-4 / 2 " Output: 4 Explanation: Division is performed first (4/2=2), then subtraction (6-2=4)

Example 3:

Input: s = "100/5*2" Output: 40 Explanation: Operations of equal precedence are evaluated left to right: 100/5=20, then 20*2=40

Example 4:

Input: s = "1-1+1" Output: 1 Explanation: Evaluated left to right: 1-1=0, then 0+1=1