DSA sheet · Stack · Expression evaluation pattern

Basic Calculator II

This is the first problem of the second stack pattern in the sheet: expression evaluation. We get a maths expression as a string, like "3+2*2", and we must compute its value ourselves, following the rule that * and / are done before + and −. The teacher first solves it with a slow but natural two-list brute force, explains a surprise (why it still passes on LeetCode), and then shows the one-pass stack solution that interviewers expect. The stack idea here (keep the last operator, settle a number only when the next operator arrives) comes back again in every calculator-style problem.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Stacks and expression evaluation from scratch
• Part A · Brute force: a numbers list and an operators list
• Part B · Optimal: one pass with a stack and the "last operator"
• Part C · Revision page

Part 0 · Stacks and expression evaluation from scratch

What is a stack?

A stack is a pile of plates. You can only put a plate on the top (push) and only take the plate from the top (pop). Looking at the top plate without removing it is called peek. The last plate you put on is the first one you take off. This rule is called LIFO: Last In, First Out.

The Python list as a stack

We always write a stack left = bottom, right = top. So [3, 4] means 3 is at the bottom and 4 is on top.

  [3, 4]      top →  | 4 |
                     | 3 |  ← bottom
                     +---+

The pattern on this page: expression evaluation

• Operands are the numbers (3, 2, 2). Operators are the signs (+, −, *, /).
• Operator precedence means "which sign goes first". * and / have higher precedence than + and −. In school this is the BODMAS rule (Brackets, Orders, Division, Multiplication, Addition, Subtraction). So 3+2*2 is 3 + 4 = 7, not 5 * 2 = 10.
• Signs with the same precedence are done left to right: 8/2*2 = 4 * 2 = 8.
• The stack trick: keep a numbers stack. Numbers that must wait (because a + or − is in front of them) sit in the stack. When a * or / shows up, we take the top number out, combine it right away, and put the result back. At the very end, everything left in the stack is just added up.
• The last sign idea: we remember the operator that came before the current number. That operator decides what we do with the number.

Reading a multi-digit number from a string

The string gives digits one character at a time. For "19" we first see '1', then '9'. To build the number: start with num = 0, and for each digit do num = num * 10 + digit. So 0 → 0*10+1 = 1 → 1*10+9 = 19. Shifting left by one place (×10) makes room for the new digit.

In Java the teacher writes ch - '0' to turn the character into its number (it subtracts ASCII codes). In Python we simply write int(ch).

Python trap: division must truncate toward zero

The problem says integer division truncates toward zero: drop the decimal part. 7/2 = 3.5 → 3, and −7/2 = −3.5 → −3.

For positive numbers both agree. As soon as one side is negative, // goes the wrong way. In Python always write int(a / b) for this problem. In Part B a negative number really does reach the division, so this matters.

Part A · Brute force: a numbers list and an operators list

LeetCode 227

1The question in simple words

You get a string s holding a valid expression with non-negative whole numbers, the four signs + - * /, and maybe some spaces. Return its value as an integer.

• Follow precedence: * and / before + and −.
• Division truncates toward zero.
• Spaces mean nothing. Ignore them.
• You may not use a built-in that evaluates a string as maths (like Python's eval). We build it ourselves.

2What the constraints tell us

• 1 ≤ s.length ≤ 3 × 10⁵ → the string is never empty, and it can be long.
• The teacher's usual rule of thumb: around 10⁸ simple operations per second is the limit. Between 10⁸ and 10⁹ the code is very slow, and beyond 10⁹ it surely gives TLE (Time Limit Exceeded). Even 10⁷ can fail if each step is heavy.
• An O(n²) solution here would be (3 × 10⁵)² = 9 × 10¹⁰ → far beyond the limit. So we need about O(n).
• The expression is always valid, and every intermediate result fits in a 32-bit integer → no need to handle broken input or overflow (Python ints never overflow anyway).
• The numbers are non-negative, and there is no unary minus like "-3+2".

3Intuition: do it the way you would on paper

On paper you'd scan the expression, do every * and / first, then go back and do the + and −. The trouble: when you stand on a *, you need the number before it and the number after it. The one before you already passed, so you could have kept it somewhere. The one after you haven't read yet.

The teacher's simple fix: first split the string into two lists, one list of numbers and one list of operators. Once everything is laid out in lists, both neighbours of every operator are easy to reach by index.

Notice: there is always one operator fewer than numbers. And operator ops[i] always works on nums[i] and nums[i+1].

4Building the logic

Step 1: split the string

• A space → skip it (continue).
• A digit → grow the current number: num = num * 10 + int(ch).
• An operator → the number we were building is complete. Put it in nums, put the operator in ops, and reset num = 0 to start reading the next number.

Step 2: first pass, only * and /

Look at each operator. If it's + or −, leave it alone and move on (BODMAS says not yet). If it's * or /, compute nums[i] * nums[i+1] (or the division).

Step 3: second pass, + and −

Now only + and − are left. Do the exact same "combine, write back, remove" loop with + and −, left to right. When it finishes, the list has one number. That's the answer: nums[0].

5Approach steps

1. Scan the string: skip spaces, build numbers digit by digit, and on every operator push the finished number to nums and the operator to ops, then reset num.
2. After the scan, push the last number.
3. Pass 1: for each operator that is * or /, compute with its two neighbours, write the result at nums[i], remove nums[i+1] and ops[i], and stay at the same i. Otherwise move on.
4. Pass 2: do the same for + and −.
5. Return nums[0].

6Code (Python)

class Solution:
    def calculate(self, s: str) -> int:
        nums, ops = [], []
        num = 0
        for ch in s:
            if ch == ' ':
                continue                      # spaces mean nothing
            if ch.isdigit():
                num = num * 10 + int(ch)      # build multi-digit numbers
            else:                             # an operator
                nums.append(num)              # the number before it is complete
                ops.append(ch)
                num = 0                       # start reading a new number
        nums.append(num)                      # the last number has no operator after it

        # pass 1: * and /  (higher precedence)
        i = 0
        while i < len(ops):
            if ops[i] == '*' or ops[i] == '/':
                if ops[i] == '*':
                    result = nums[i] * nums[i + 1]
                else:
                    result = int(nums[i] / nums[i + 1])   # truncate toward zero
                nums[i] = result              # write the result back
                nums.pop(i + 1)               # the right number is used up
                ops.pop(i)                    # the operator is used up
                # do NOT move i: the next operator slid into position i
            else:
                i += 1                        # + or -: leave it for pass 2

        # pass 2: + and -
        i = 0
        while i < len(ops):
            if ops[i] == '+':
                nums[i] = nums[i] + nums[i + 1]
            else:
                nums[i] = nums[i] - nums[i + 1]
            nums.pop(i + 1)
            ops.pop(i)
        return nums[0]

In pass 2 every operator gets used, so i stays at 0 the whole time and we keep folding the list from the left.

7Code line by line

8Dry run: s = "3+2*2/2+1"

Answer 6 ✓. Look at the row with /: if we had stored 4 in a separate variable and moved on, the division would have used the old 2 instead of 4. Writing back into the list is what keeps the chain correct.

9Complexity & the "why did it pass?" surprise

• At first glance: one loop to split, one pass, another pass → 3n → O(n)? No.
• Removing from the middle of a list is not O(1). If the list is [2, 3, 4, 5, 6, 7] and we remove 3, every element after it shifts one step left and gets a new index (4 was at index 2, now at 1; 5 was at 3, now at 2, …). That shifting is O(n).
• So each * or / costs O(n). If there are k such operators, pass 1 is O(n · k). In the worst case (like "1*2/3*4/5…") about half the characters are operators, so k ≈ n/2 → O(n²). Pass 2 also removes, with the same worst case.
• Space O(n) for the two lists.

Part B · Optimal: one pass with a stack and the "last operator"

1The question in simple words

Same question as Part A. Now we want one left-to-right scan, with no list removals.

2What the constraints tell us

• n up to 3 × 10⁵ → O(n) is what we aim for. One scan plus one final sum is O(n).
• The expression is valid, so every operator has a number on each side. That guarantees the stack is never empty when we pop for * or / (the number before the * was pushed already).

3Intuition: settle a number only when the NEXT operator arrives

In the brute force we waited for + and − and only acted on * and /. Let's keep that idea but do it on the fly.

• Think of every number as carrying the sign written in front of it. "3+2*2" is really +3 +2 *2. The first number has no sign, so we pretend it has a +. That's why the operator variable starts as '+'.
• A number with + or − in front of it can't be combined yet (a * may come later and grab it). So we just push it on a stack: +num or -num. Storing the sign inside the number means at the end we can simply add everything.
• A number with * or / in front of it must be combined now, with the number just before it. That number is the top of the stack. Pop it, combine, push the result back.

But when do we know a number is complete? A number like 411 comes digit by digit. We only know it's finished when we reach the next operator. So at every operator we settle the previous number using the previous operator. To combine two numbers we need three things:

4Building the logic from "3+2*2"

1. Start: stack = [], num = 0, op = '+'.
2. Read 3 → num = 3.
3. Read +. The number 3 is complete. Its sign (op) is + → push 3. Now update op = '+' (the operator we're standing on) and reset num = 0.
4. Read 2 → num = 2.
5. Read *. The 2 is complete. Its sign is + → push 2. Stack [3, 2]. Now op = '*', num = 0.
6. Read 2 → num = 2.
7. The string ends. But this last 2 has no next operator to trigger it!

5Approach steps

1. stack = [], num = 0, op = '+'.
2. For i from 0 to len(s) (included): ch = '+' if i == len(s), else s[i].
3. If ch is a digit → num = num * 10 + int(ch).
4. Else if ch is not a space (so it's an operator): settle num using the old op: + → push num · − → push −num · * → push pop() * num · / → push int(pop() / num). Then op = ch, num = 0.
5. Return the sum of the stack.

6Code (Python)

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        num = 0
        op = '+'                              # the first number counts as "+num"
        n = len(s)
        for i in range(n + 1):                # one extra step for the fake '+'
            ch = '+' if i == n else s[i]
            if ch.isdigit():
                num = num * 10 + int(ch)
            elif ch != ' ':                   # an operator: settle the previous number
                if op == '+':
                    stack.append(num)
                elif op == '-':
                    stack.append(-num)
                elif op == '*':
                    stack.append(stack.pop() * num)
                else:                         # op == '/'
                    stack.append(int(stack.pop() / num))   # truncate toward zero
                op = ch                       # this operator is the sign of the NEXT number
                num = 0
        answer = 0
        while stack:
            answer += stack.pop()
        return answer

The final loop can also be written return sum(stack). On screen the teacher's first run failed because the last branch was missing its divide sign. She fixed it and it passed. When you copy the four branches, check each sign carefully.

7Code line by line

8Dry run: s = "14-3*2/4+5"

The correct value: 3*2 = 6, 6/4 = 1 (1.5 cut down), so 14 − 1 + 5 = 18. The table shows only the steps where something happens (digits just grow num). "op" is the sign waiting for the current number.

At i = 8, Python's -6 // 4 would be −2 and the answer would be 17 ✗. The truncation rule matters.

The top of each stack is red. The bottom of the box is the bottom of the stack.

The teacher's example "3+2*2" in short: at '+' push 3 → [3]; at '*' push 2 → [3, 2]; at the fake '+' op is * → pop 2, push 2×2 = 4 → [3, 4]; sum = 7.

9Complexity & remember

• Time O(n): one scan over the string, each character handled once. Every push and pop is O(1), and the final sum touches each stack item once.
• Space O(n): in the worst case (all + and −) every number sits in the stack. The brute force also used O(n) for two lists, so we gave up nothing and gained a lot of speed.
• The teacher's interview tip: the stack solution is the truly optimal one, and it's the one the interviewer expects you to explain, with a proper dry run.

Part C · Revision page

s = Solution()
print(s.calculate("3+2*2"))         # 7
print(s.calculate(" 3/2 "))         # 1
print(s.calculate(" 3+5 / 2 "))     # 5
print(s.calculate("14-3/2"))        # 13  (// would give 12)
print(s.calculate("14-3*2/4+5"))    # 18
print(s.calculate("42"))            # 42

Based on this video: Basic Calculator II