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.
This approach uses a stack to store numbers and consider operator precedence. Multiplication and division are processed immediately, whereas addition and subtraction modify how numbers are pushed onto the stack.
This C solution iterates over the string, calculates numeric values, updates the stack with results immediately for '*', '/', while '+' and '-' add or subtract the number to/from the stack respectively. Finally, calculates the sum of values in the stack.
Time Complexity: O(n) where n is the length of the string. Space Complexity: O(n) for storing numbers in the stack.
This approach parses the expression twice, first to handle multiplications and divisions, then to process additions and subtractions. This avoids using a stack and simplifies sign handling.
This C code tracks the last number while parsing. It processes multiplication and division without using an additional stack by altering the last number, collects results using '+' and '-', and accumulates a final result.
Time Complexity: O(n) where n is the number of characters in the input string. Space Complexity: O(1) since it only uses primitive data types.
We traverse the string s, and use a variable sign to record the operator before each number. For the first number, its previous operator is considered as a plus sign. Each time we traverse to the end of a number, we decide the calculation method based on sign:
After the traversal ends, the sum of the elements in the stack is the answer.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the string s.
| Approach | Complexity |
|---|---|
| Approach 1: Use a Stack to Handle Precedence | Time Complexity: O(n) where n is the length of the string. Space Complexity: O(n) for storing numbers in the stack. |
| Approach 2: Two-Pass Parsing Using Sign Tracking | Time Complexity: O(n) where n is the number of characters in the input string. Space Complexity: O(1) since it only uses primitive data types. |
| Stack | — |
| 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. |
BASIC CALCULATOR II | LEETCODE 227 | PYTHON SOLUTION • Cracking FAANG • 45,885 views views
Watch 9 more video solutions →Practice Basic Calculator II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor