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 task is to evaluate the expression while respecting standard operator precedence where multiplication and division happen before addition and subtraction.
Approach 1: Use a Stack to Handle Precedence (O(n) time, O(n) space)
This approach scans the string once and uses a stack to enforce operator precedence. While iterating through the characters, build the current number digit by digit. When you hit an operator or the end of the string, process the previous operator. Push numbers for +, push the negative value for -, and immediately compute for * or / by popping the last number from the stack and applying the operation. This ensures multiplication and division happen before later additions. At the end, sum all values stored in the stack to produce the final result. The key insight: defer addition/subtraction but resolve multiplication/division immediately. This keeps the algorithm linear while preserving precedence rules.
Approach 2: Two-Pass Parsing Using Sign Tracking (O(n) time, O(1) space)
This method avoids a stack by simulating precedence with running variables. Iterate through the string and track two values: the current number being built and the last evaluated term. When encountering * or /, update the last term immediately by multiplying or dividing it with the current number. When encountering + or -, commit the previous term to a running total and start a new term with the appropriate sign. Effectively, multiplication and division collapse into the current term while addition and subtraction finalize previous results. This approach still processes each character once but uses constant extra memory. It’s essentially performing arithmetic grouping without storing intermediate values in a stack.
Both approaches rely on sequential parsing and simple arithmetic operations from math. The complexity stays linear because each character in the expression is processed exactly once.
Recommended for interviews: The stack-based approach is the most commonly expected solution. It clearly demonstrates understanding of operator precedence and shows comfort with stacks and string parsing. The constant‑space sign‑tracking approach is slightly more optimized and often appears as a follow‑up once you already have the stack version working. Implementing the stack solution first shows clear reasoning; optimizing to constant space demonstrates deeper control over expression evaluation.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack to Handle Precedence | O(n) | O(n) | Most common interview solution. Clear handling of operator precedence. |
| Two-Pass Parsing with Sign Tracking | O(n) | O(1) | When optimizing for constant extra memory while parsing expressions. |
BASIC CALCULATOR II | LEETCODE 227 | PYTHON SOLUTION • Cracking FAANG • 34,883 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