Watch 10 video solutions for Basic Calculator II, a medium level problem involving Math, String, Stack. This walkthrough by Cracking FAANG has 34,883 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 [-231, 231 - 1].
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
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 * 105s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.s represents a valid expression.[0, 231 - 1].Problem Overview: You receive a string representing a mathematical expression containing non‑negative integers and the operators +, -, *, and /. Spaces may appear anywhere. The goal is to evaluate the expression while respecting normal operator precedence (multiplication and division before addition and subtraction).
Approach 1: Use a Stack to Handle Precedence (O(n) time, O(n) space)
This approach scans the string once while building numbers and applying operations as they appear. Keep a stack of intermediate values and track the previous operator. When you finish reading a number, decide what to do based on the last operator: push the number for +, push its negative for -, or pop the top element and immediately compute multiplication or division for * and /. Multiplication and division are resolved immediately, which naturally preserves precedence.
After processing the entire string, sum the values in the stack to produce the final result. Each character is processed once, and each stack operation is constant time. This method is straightforward and mirrors how expression evaluation works conceptually, making it common in stack-based parsing problems involving string expressions.
Approach 2: Two-Pass Parsing Using Sign Tracking (O(n) time, O(1) space)
This approach removes the explicit stack and instead tracks the last computed term. Iterate through the string while building the current number and remembering the previous operator. Maintain two variables: result for the accumulated sum and lastTerm for the most recent value that may still be affected by multiplication or division.
When encountering + or -, add lastTerm to result and start a new term with the current number (positive or negative). For * and /, update lastTerm directly by multiplying or dividing it with the current number. This delays addition until the correct precedence is guaranteed. The algorithm still scans the expression once, but it stores only a few integers, achieving constant auxiliary space.
This technique relies on careful state tracking rather than a container, making it slightly more optimized for memory. It still requires parsing integers from the string and handling truncating division according to problem rules. Problems combining arithmetic evaluation with math parsing often use this pattern.
Recommended for interviews: The stack-based approach is the most widely expected answer because it clearly demonstrates how you enforce operator precedence during a single pass. After presenting that solution, mentioning the constant-space sign-tracking optimization shows deeper understanding of expression parsing and algorithmic refinement.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack to Handle Precedence | O(n) | O(n) | General case; easiest to reason about when evaluating expressions with operator precedence. |
| Two-Pass Parsing with Sign Tracking | O(n) | O(1) | When optimizing memory or demonstrating deeper understanding of expression parsing. |