15% off all plans & roadmaps Use code

See plans

Basic Calculator II

Updated

TL;DR: Evaluate an expression of non-negative integers using `+`, `-`, `*` and `/` with normal precedence, and without `eval`. Keep a stack of signed terms, fold each `*` or `/` into the term before it, and sum the stack at the end.

Problem

Given a string s which represents an expression, evaluate it and return its value.

The integer division should truncate toward zero.

You may assume the expression is always valid. Every intermediate result stays in the range [-2^31, 2^31 - 1].

Note: You may not use any built-in function that evaluates a string as a mathematical expression, 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 * 10^5
  • s consists of integers and the operators +, -, *, /, separated by some spaces.
  • s represents a valid expression.
  • Every integer in the expression is non-negative and lies in the range [0, 2^31 - 1].
  • The answer fits in a 32-bit integer.

Constraints that matter

  • s can be 3 * 10^5 characters long, so an O(n^2) approach that rescans the string for each operator is too slow in the worst case.
  • Operands are non-negative, but intermediate terms can be negative after a subtraction. Division must truncate toward zero, so a negative dividend needs care.
  • Every intermediate result fits in 32 bits, so you do not need big integers. Python integers are unbounded anyway, but Java, C++, and C# must not overflow on the way.
  • Spaces can appear anywhere between tokens, so the scanner must skip them without treating them as operators.

View on LeetCode

Hints

Hint 1

The expression mixes two precedence levels and has no parentheses.

Hint 2

Split the string into two lists.

Solution

Intuition

The expression mixes two precedence levels and has no parentheses. That makes it an infix evaluation problem, and the standard tool is a stack. The stack holds the terms that still need to be added. Each term is a signed number that may already have been multiplied or divided.

Picture a pile of index cards, each holding a signed number. The stack is that pile, and the top card is the open term that a * or / can still change. When an operator arrives, you combine the top card with the current number and write the result back on it.

A + or - starts a new term. Later * or / operators can still change that term, so you cannot add it to the total yet. Storing the sign with the number lets you add all the terms at the end.

When you reach * or /, the term before it is still open. Pop that term, combine it with the current number, and push the result back. Each operator does a constant amount of work, so the whole expression takes one pass.

Watch the pattern animation

Worked example

Input: s = "12*3-8/2+7*2-5"
Output: 41
Explanation: The two multiplications and the division bind first. 12 * 3 = 36, 8 / 2 = 4, and 7 * 2 = 14. The remaining expression is 36 - 4 + 14 - 5, which equals 41. Division is exact here, so truncation does not change the result.

Approach 1: Brute force

Split the string into two lists. nums holds every number, and ops holds every operator between them. Then apply precedence the blunt way: find the first * or /, combine its two neighbours, delete the operator and one number, and start the scan again from the front.

When no multiplicative operator is left, only + and - remain. Walk those from left to right and add or subtract each number.

Steps

  1. Walk s once. On each digit run, build the number. On each operator, append the number to nums and the operator to ops.
  2. Append the final number to nums. Now len(nums) is len(ops) + 1.
  3. While ops contains * or /, scan from index 0 to find the first one, at index i.
  4. Replace nums[i] with nums[i] op nums[i + 1], truncating toward zero for division. Delete nums[i + 1] and ops[i].
  5. When no * or / remains, start the result at nums[0].
  6. Walk ops from left to right. Add nums[i + 1] for + and subtract it for -. Return the result.

Dry run

Start with nums = [12, 3, 8, 2, 7, 2, 5] and ops = ['*', '-', '/', '+', '*', '-'].

  1. The first * is at index 0. 12 * 3 = 36. Now nums = [36, 8, 2, 7, 2, 5] and ops = ['-', '/', '+', '*', '-'].
  2. The first * or / is at index 1, the /. 8 / 2 = 4. Now nums = [36, 4, 7, 2, 5] and ops = ['-', '+', '*', '-'].
  3. The first * is at index 2. 7 * 2 = 14. Now nums = [36, 4, 14, 5] and ops = ['-', '+', '-'].
  4. No * or / is left. Sum from the left: 36 - 4 = 32, then 32 + 14 = 46, then 46 - 5 = 41. Return 41.

Complexity

TimeO(n^2)
SpaceO(n)

Let n be the length of s. The operator count k is at most n. Each collapse scans up to k operators and deletes from two lists, and each deletion shifts up to k items, so one collapse costs O(k). When most operators are * or /, there are about k collapses, so the total work is O(k^2), which is O(n^2). The two lists hold O(n) items in total, so the space is O(n).

PythonTested in our runner

class Solution:
    def calculate(self, s: str) -> int:
        nums, ops = [], []
        num = 0
        for ch in s:
            if ch.isdigit():
                num = num * 10 + int(ch)
            elif ch in '+-*/':
                nums.append(num)
                ops.append(ch)
                num = 0
        nums.append(num)

        def trunc_div(a, b):
            q = abs(a) // abs(b)
            return q if (a < 0) == (b < 0) else -q

        # Collapse every * and / by rescanning from the start
        while '*' in ops or '/' in ops:
            i = 0
            while ops[i] not in ('*', '/'):
                i += 1
            if ops[i] == '*':
                nums[i] = nums[i] * nums[i + 1]
            else:
                nums[i] = trunc_div(nums[i], nums[i + 1])
            del nums[i + 1]
            del ops[i]

        result = nums[0]
        for i, op in enumerate(ops):
            if op == '+':
                result += nums[i + 1]
            else:
                result -= nums[i + 1]
        return result

The Expression Evaluation (RPN/Infix) infographic is part of Pro

A one-page visual of the pattern: when it applies, the steps and the invariant to keep.

Unlock the infographic

Solution pattern

Expression Evaluation (RPN/Infix)

Part of Stack Patterns

Approach 2: One-pass stackOptimalExpression Evaluation (RPN/Infix)

What is slow in the brute force: each collapse rescans from index 0 to find the next * or /, and each deletion shifts every later element. With k operators, that is up to k collapses at O(k) each, so the total is O(n^2) on inputs such as 1*1*1*....

The insight that fixes it: a * or / only needs the term right before it. Keep the terms on a stack. When you read an operator, apply the pending operator to the number you finished, which means you rewrite the top of the stack in place. One left-to-right pass is enough.

Why it is correct. At every point, the stack holds the finished terms, and only the top term can still be changed by a * or /. Precedence means a * or / binds to the number right before it, so earlier terms are final. Summing the stack therefore gives the value of the whole expression, because each term already carries its sign.

Steps

  1. Set num = 0, an empty stack, and op = '+', the operator that comes before the current number.
  2. For each character, if it is a digit, set num = num * 10 + digit. Skip spaces.
  3. When the character is +, -, *, /, or the last index, apply op to num. + pushes num, - pushes -num, * pops and multiplies, and / pops and divides with truncation.
  4. Set op to the current character and reset num = 0.
  5. After the loop, add every value on the stack and return the sum.

Dry run

Walk through s = "12*3-8/2+7*2-5". Each row is one operator or the last character. The num column shows the number read so far, and the stack shows the terms after the action.

ReadActionnumopstack
1, 2build the number12+[]
*apply + to 12, push 120*[12]
3build the number3*[12]
-apply * to 3, pop 12, push 360-[36]
8build the number8-[36]
/apply - to 8, push -80/[36, -8]
2build the number2/[36, -8]
+apply / to 2, pop -8, push -40+[36, -4]
7build the number7+[36, -4]
*apply + to 7, push 70*[36, -4, 7]
2build the number2*[36, -4, 7]
-apply * to 2, pop 7, push 140-[36, -4, 14]
5build the number5-[36, -4, 14]
last 5apply - to 5, push -505[36, -4, 14, -5]

The stack holds [36, -4, 14, -5]. Summing gives 36 - 4 + 14 - 5 = 41. Return 41.

Complexity

TimeO(n)
SpaceO(n)

Let n be the length of s. The loop visits each character once. A digit does constant work, and an operator does one push or one pop followed by one push, so time is O(n). Each number adds at most one stack entry, so the stack never holds more than O(n) items, which is the space bound. On 1+2+3+..., the stack grows to about n/2 entries.

PythonTested in our runner

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        num = 0
        op = '+'  # operator that comes before the current number
        n = len(s)
        for i, ch in enumerate(s):
            if ch.isdigit():
                num = num * 10 + int(ch)
            if ch in '+-*/' or i == n - 1:
                # Apply the pending operator to the number we just finished
                if op == '+':
                    stack.append(num)
                elif op == '-':
                    stack.append(-num)
                elif op == '*':
                    stack.append(stack.pop() * num)
                else:
                    top = stack.pop()
                    q = abs(top) // abs(num)  # divide magnitudes, then restore the sign
                    stack.append(q if (top < 0) == (num < 0) else -q)
                op = ch
                num = 0
        return sum(stack)

Common mistakes

  • result += num for - instead of pushing -num. The sign is lost, and a later * or / cannot see it. Push the negated number so the stack holds signed terms.
  • op = ch placed before the flush block. The pending operator is then applied with the wrong symbol. Update op only after the flush has used the old value.
  • Missing final flush: the check is only if ch in '+-*/', so the last number is never pushed. Add or i == n - 1 to the condition.
  • Resetting num on every digit, or pushing on every digit. 42 must become num = num * 10 + digit on each digit, so the number is built once at the next operator.
  • Python // or int(top / num) on negative values. -7 // 2 is -4, and the problem wants -3. Divide the absolute values and restore the sign.
  • Treating a space as an operator. A space can flush the number and set op to a character that matches no branch. Skip spaces, and flush only on + - * / or at the last index.

Edge cases

  • 0: a single number. The final flush at the last index pushes 0, and the answer is 0.
  • 7: a single digit at the last index. Without the i == n - 1 check, the answer would be 0.
  • 3/2: leading and trailing spaces are skipped, and the answer is 1 because truncation rounds 1.5 toward zero.
  • 1-7/2: a division of a negative term. The stack holds -7 before /, and truncation gives -3. The answer is 1 - 3 = -2. Floor division would give -3 instead.
  • 14-3/2: multi-digit operands with precedence on the right. The answer is 14 - 1 = 13.
  • 0-2147483647: the largest magnitude term, negated. The answer is -2147483647, which fits in 32 bits.

Follow-ups interviewers ask

Can you solve it in O(1) extra space?
Yes. Keep two variables, total and last, where last is the open term. On + or -, add last to total, then set last to the new signed number. On * or /, update last in place. At the end, return total + last.
How would you handle parentheses?
Parentheses need saved state. On (, push the running total and the pending sign, then start a fresh total. On ), finish the inner total, pop the saved sign and total, and combine them. The expression on this page has no parentheses, so the stack of terms is enough.
What if the expression does not fit in memory?
Read it as a stream. The O(1) variant needs only the numbers total, last, and the current number, plus the pending operator. Each character is read once, so the input can come from a file or socket one character at a time.

Basic Calculator II FAQ

What is the time complexity of Basic Calculator II?

The one-pass stack solution runs in O(n) time, where n is the length of s. Each character is read once and does constant work. The brute force that rescans for * and / runs in O(n^2).

Why use a stack for Basic Calculator II?

A stack holds the terms that are waiting to be added. A * or / only needs the term right before it, which is the top of the stack. That lets precedence work in a single left-to-right pass.

Can Basic Calculator II be solved in O(1) extra space?

Yes. Keep a running total and the most recent open term in two variables. The stack is not needed, because only the last term ever changes.

Why does integer division need care in Python for Basic Calculator II?

Python's // rounds toward negative infinity, so -7 // 2 is -4. The problem needs truncation toward zero, which gives -3. Divide the absolute values, then restore the sign.

Is eval allowed for Basic Calculator II?

No. The problem forbids built-in evaluators such as eval(). The stack approach reads the digits and operators directly, so no string evaluator is needed.

Asked at

See which companies ask this — Pro

Practise it