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 [-2^31, 2^31 - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Examples

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 * 10^5
  • s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
  • s represents a valid expression.
  • All the integers in the expression are non-negative integers in the range [0, 2^31 - 1].
  • The answer is guaranteed to fit in a 32-bit integer.

Thinking Process

  1. Operator Precedence: * and / have higher precedence than + and -
  • Stack matches nested or LIFO structure (parentheses, monotonic scans).
  • Push on open / larger; pop when the current element resolves pending work.
  • Monotonic stack finds next greater/smaller in O(n).
Stack top push / pop LIFO — monotonic stack scans array

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Monotonic stack (this problem) O(n) O(n) Next greater/smaller element
Parentheses matching O(n) O(n) Push open, pop on close
Expression evaluation O(n) O(n) Operand + operator stacks
Stack simulation O(n) O(n) Process in LIFO order

Solution

Time Complexity: O(n)
Space Complexity: O(n)

Use a stack to store numbers. When encountering + or -, push the number (with sign for -). When encountering * or /, immediately compute with the top of stack and push the result. Finally, sum all elements in the stack.

class Solution:
    def calculate(self, s):
        n = len(s)
        if n == 0:
            return 0

        stk = []
        operation = '+'
        curr = 0

        for i in range(n):
            ch = s[i]

            if ch.isdigit():
                curr = curr * 10 + (ord(ch) - ord('0'))

            if (not ch.isdigit() and not ch.isspace()) or i == n - 1:
                if operation == '-':
                    stk.append(-curr)

                elif operation == '+':
                    stk.append(curr)

                elif operation == '*':
                    top = stk.pop()
                    stk.append(top * curr)

                elif operation == '/':
                    top = stk.pop()
                    stk.append(int(top / curr))

                operation = ch
                curr = 0

        rtn = 0
        while stk:
            rtn += stk.pop()

        return rtn

Solution Explanation

Approach: Monotonic stack (this problem)

Key idea: 1. Operator Precedence: * and / have higher precedence than + and -

How the code works:

  1. Operator Precedence: * and / have higher precedence than + and -
    • Stack matches nested or LIFO structure (parentheses, monotonic scans).
    • Push on open / larger; pop when the current element resolves pending work.
    • Monotonic stack finds next greater/smaller in O(n).

Walkthrough — input s = "3+2*2", expected output 7:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

| Solution | Time | Space | Notes | |———-|——|——-|——-| | Stack-Based | O(n) | O(n) | Clear logic, uses stack | | Optimized | O(n) | O(1) | No stack needed |

How the Algorithms Work

Key Insight: Operator Precedence

  • * and /: Higher precedence - must be evaluated immediately
  • + and -: Lower precedence - can be deferred until the end

Solution 1: Stack-Based Step-by-Step

Example: s = "3+2*2"

Step Char curr operation Stack Action
0 - 0 ’+’ [] Initialize
1 ‘3’ 3 ’+’ [] Build number
2 ’+’ 0 ’+’ [3] Push 3, set op
3 ‘2’ 2 ’+’ [3] Build number
4 ‘*’ 0 ‘*’ [3] Set op to *
5 ‘2’ 2 ‘*’ [3] Build number
6 End 0 - [3, 4] Pop 3, calc 3*2=4, push 4
Final - - - [3, 4] Sum: 3+4=7

Visual Representation:

"3+2*2"
 3 + 2 * 2
 ↑   ↑   ↑
 |   |   |
 |   |   Process: 2*2 = 4, push 4
 |   |
 |   Push: 3
 |
 Sum all: 3 + 4 = 7

Solution 2: Optimized Step-by-Step

Example: s = "3+2*2"

Step Char curr sign last rtn Action
0 - 0 ’+’ 0 0 Initialize
1 ‘3’ 3 ’+’ 0 0 Build number
2 ’+’ 0 ’+’ 3 0 Add last to rtn, set last=3
3 ‘2’ 2 ’+’ 3 0 Build number
4 ‘*’ 0 ‘*’ 3 0 Set sign to *
5 ‘2’ 2 ‘*’ 6 0 Build number, calc last=3*2=6
6 End 0 - 6 0 Add last to rtn: 0+6=6

Wait, let me recalculate:

Actually, at step 2 (when we see ‘+’), we should:

  • rtn += last → rtn = 0 + 0 = 0
  • last = (sign == '+') ? curr : -curr → last = 3

At step 5 (when we see ‘2’ and sign is ‘*’):

  • We process the previous sign ‘*’
  • last = last * curr → last = 3 * 2 = 6

At the end:

  • rtn += last → rtn = 0 + 6 = 6

But the answer should be 7, not 6. Let me trace more carefully:

Actually, the issue is that when we see the operator, we need to process the previous operator. Let me trace correctly:

"3+2*2"
 i=0: '3' → curr = 3
 i=1: '+' → process '+' with curr=3
        sign was '+', so rtn += last (0), last = 3
        sign = '+', curr = 0
 i=2: '2' → curr = 2
 i=3: '*' → process '*' with curr=2
        sign was '*', so last = last * curr = 3 * 2 = 6
        sign = '*', curr = 0
 i=4: '2' → curr = 2
 i=5: end → process '*' with curr=2
        sign was '*', so last = last * curr = 6 * 2 = 12
        Then rtn += last = 0 + 12 = 12

This is still wrong. The issue is that we’re processing the operator when we see the NEXT operator or end. Let me look at the code again:

class Solution:
    def calculate(self, s):
        n = len(s)
        if n == 0:
            return 0

        curr = 0
        last = 0
        rtn = 0
        sign = '+'

        for i in range(n):
            ch = s[i]

            if ch.isdigit():
                curr = curr * 10 + (ord(ch) - ord('0'))

            if (not ch.isdigit() and not ch.isspace()) or i == n - 1:
                if sign == '+' or sign == '-':
                    rtn += last
                    last = curr if sign == '+' else -curr

                elif sign == '*':
                    last = last * curr

                elif sign == '/':
                    last = int(last / curr)

                sign = ch
                curr = 0

        rtn += last
        return rtn

I see - when we see an operator, we process the PREVIOUS operator with the current number. Let me trace again:

"3+2*2"
 i=0: '3' → curr = 3
 i=1: '+' → process previous sign '+' with curr=3
        sign was '+' (initial), so rtn += last (0), last = 3
        sign = '+', curr = 0
 i=2: '2' → curr = 2
 i=3: '*' → process previous sign '+' with curr=2
        sign was '+', so rtn += last (3), last = 2
        sign = '*', curr = 0
 i=4: '2' → curr = 2
 i=5: end → process previous sign '*' with curr=2
        sign was '*', so last = last * curr = 2 * 2 = 4
        Then rtn += last = 3 + 4 = 7 ✓

Yes! That’s correct now.

Algorithm Breakdown

Solution 1: Stack-Based

1. Build Numbers

if not isdigit(ch)  and  not isspace(ch)  or  i == len - 1:
    # Process previous operation
    if sign == '+'  or  sign == '-':
        rtn += last
        (curr if         last = (sign == '+')  else -curr)
         else if(sign == '') :
        last = last  curr
         else if(sign == '/') :
        last = last / curr
    sign = ch  # Update sign for next operation
    curr = 0
  • Accumulate digits to form multi-digit numbers

2. Process Operators

if isdigit(ch):
    curr = (curr  10) + (ch - '0')

3. Sum Stack

if not isdigit(ch)  and  not isspace(ch)  or  i == len - 1:
    if operation == '-':
        stk.push(-curr)  # Push negative for subtraction
         else if(operation == '+') :
        stk.push(curr)
         else if(operation == '') :
        stkTop = stk.top()
        stk.pop()
        stk.push(stkTop  curr)  # Immediate evaluation
         else if(operation == '/') :
        stkTop = stk.top()
        stk.pop()
        stk.push(stkTop / curr)  # Immediate evaluation
    operation = ch
    curr = 0

Solution 2: Optimized

1. Track Last Value

rtn = 0
while not not stk:
    rtn += stk.top()
    stk.pop()
  • last: Stores the value that might be multiplied/divided
  • rtn: Accumulates final result

2. Process Operators

curr = 0, last = 0, rtn = 0
char sign = '+'

3. Final Addition

if sign == '+'  or  sign == '-':
    rtn += last  # Add previous last to result
    (curr if     last = (sign == '+')  else -curr  # Set new last)
     else if(sign == '') :
    last = last  curr  # Immediate evaluation
     else if(sign == '/') :
    last = last / curr  # Immediate evaluation

Complexity

| Solution | Time | Space | Notes | |———-|——|——-|——-| | Stack-Based | O(n) | O(n) | Clear logic, uses stack | | Optimized | O(n) | O(1) | No stack needed |

Why Solution 2 Works

Key Observation

For expressions like a + b * c:

  • We can’t evaluate a + b first (wrong precedence)
  • We evaluate b * c first, then add to a
  • So we keep a separate and combine b * c immediately

Variable Roles

  • last: Holds the value that’s part of a * or / chain, or a single +/- operand
  • rtn: Accumulates values that are completely processed (added/subtracted)

Example: "3+2*2"

Step 1: Process '3' with sign '+'
  rtn += last (0) → rtn = 0
  last = 3

Step 2: Process '2' with sign '*'
  last = last * 2 = 3 * 2 = 6

Step 3: End, process with sign '*'
  last = last * 2 = 6 * 2 = 12
  rtn += last = 0 + 12 = 12

Wait, that’s still wrong. Let me re-read the code logic:

Actually, when we see an operator, we process the PREVIOUS operator. So:

"3+2*2"
 i=0: '3' → curr=3
 i=1: '+' → process sign='+' (initial) with curr=3
        rtn += last (0), last = 3, sign='+', curr=0
 i=2: '2' → curr=2
 i=3: '*' → process sign='+' with curr=2
        rtn += last (3), last = 2, sign='*', curr=0
 i=4: '2' → curr=2
 i=5: end → process sign='*' with curr=2
        last = last * curr = 2 * 2 = 4
        rtn += last = 3 + 4 = 7 ✓

Perfect!

Common Mistakes

  1. Single number: "42" → 42
  2. Only spaces: " " → 0 (handled by initial check)
  3. Division truncation: "3/2" → 1 (not 1.5)
  4. Negative results: "1-2" → -1
  5. Multiple spaces: "3 + 2" → 5 (spaces are ignored)

  6. Consecutive operators: Not possible (given expression is valid)

  7. Wrong operator precedence: Evaluating + before *
  8. Number building: Not handling multi-digit numbers correctly
  9. Sign handling: Forgetting to push negative for - or set last negative
  10. End of string: Not processing the last number when string ends
  11. Division truncation: Using floating point instead of integer division

Detailed Example Walkthrough

Example: s = " 3+5 / 2 "

Solution 1 (Stack):

Step 0: Initialize
  stk = []
  operation = '+'
  curr = 0

Step 1-2: ' 3' → curr = 3
Step 3: '+' → process operation='+' with curr=3
  stk.push(3)
  operation = '+', curr = 0
  stk = [3]

Step 4-5: ' 5' → curr = 5
Step 6: ' ' → skip
Step 7: '/' → process operation='+' with curr=5
  stk.push(5)
  operation = '/', curr = 0
  stk = [3, 5]

Step 8: ' ' → skip
Step 9: '2' → curr = 2
Step 10: ' ' → skip
Step 11: end → process operation='/' with curr=2
  top = 5, stk.pop()
  stk.push(5 / 2) = stk.push(2)
  stk = [3, 2]

Final: Sum stack = 3 + 2 = 5 ✓

Solution 2 (Optimized):

Step 0: Initialize
  curr = 0, last = 0, rtn = 0
  sign = '+'

Step 1-2: ' 3' → curr = 3
Step 3: '+' → process sign='+' with curr=3
  rtn += last (0) → rtn = 0
  last = 3
  sign = '+', curr = 0

Step 4-5: ' 5' → curr = 5
Step 6: ' ' → skip
Step 7: '/' → process sign='+' with curr=5
  rtn += last (3) → rtn = 3
  last = 5
  sign = '/', curr = 0

Step 8: ' ' → skip
Step 9: '2' → curr = 2
Step 10: ' ' → skip
Step 11: end → process sign='/' with curr=2
  last = last / curr = 5 / 2 = 2
  rtn += last = 3 + 2 = 5 ✓

Pattern Recognition

This problem demonstrates the Expression Evaluation pattern:

  • Process operators based on precedence
  • Use stack or variables to defer lower-precedence operations
  • Build numbers incrementally
  • Handle spaces and edge cases

Key Insight:

  • Higher precedence operators (*, /) are evaluated immediately
  • Lower precedence operators (+, -) are deferred
  • Stack or variables can track deferred values

Optimization Tips

Solution 2 Advantages

  • O(1) space: No stack needed
  • Fewer operations: Direct variable updates
  • Better cache performance: No stack memory access

When to Use Each

  • Stack-based: Easier to understand and extend (e.g., for parentheses)
  • Optimized: Better for space-constrained scenarios

Code Quality Notes

  1. Readability: Stack approach is more intuitive
  2. Efficiency: Optimized approach uses O(1) space
  3. Correctness: Both handle operator precedence correctly
  4. Maintainability: Stack approach is easier to extend

Key Takeaways

  1. Operator Precedence: * and / have higher precedence than + and -
  2. Immediate Evaluation: Evaluate * and / immediately when encountered
  3. Deferred Evaluation: Defer + and - until the end
  4. Number Building: Build multi-digit numbers by curr = curr * 10 + digit
  5. Sign Handling: For -, push negative number or set last to negative

References

Template Reference