MediumMathStringStack

Basic Calculator II

1 approach, code in every language

You are given a string that encodes a simple arithmetic expression made up of non-negative integers and the operators +, -, * and /. The expression contains no parentheses, and any number of spaces may appear between tokens.

Evaluate the expression and return its integer result. Multiplication and division bind more tightly than addition and subtraction, so they must be applied before the surrounding + and - operators. Integer division truncates toward zero, meaning any fractional part is discarded rather than rounded.

You may assume the input is always a valid expression and that the final answer fits in a 32-bit signed integer.

Example 1

Input: s = "3+2*2"

Output: 7

The multiplication 2*2 is applied first to get 4, then 3+4 yields 7.

Example 2

Input: s = " 3/2 "

Output: 1

Integer division of 3 by 2 truncates toward zero, giving 1. Surrounding spaces are ignored.

Constraints

1 <= s.length <= 3 * 10^5
s consists of integers and the operators '+', '-', '*', '/' separated by some spaces.
s represents a valid expression.
All integer values are in the range [0, 2^31 - 1].
The answer is guaranteed to fit in a 32-bit integer.

Stack of Additive Terms

Defer + and - by pushing signed terms onto a stack, resolve * and / immediately, then sum the stack.

Loading animation…

Intuition

Addition and subtraction can always wait until the very end, because their result does not depend on what comes after them. Multiplication and division, however, must combine with the value directly next to them before any addition happens. To respect this, we keep a stack that holds each additive term as a signed number. Whenever we finish reading a number, we look at the operator that came before it: a plus pushes the number, a minus pushes its negation, and a times or divide pops the previous term and folds the new number into it right away. Once the whole string is scanned, every remaining stack entry is an independent additive term, so summing them produces the answer.

Algorithm walkthrough

1Track the current number being built, and remember the operator seen just before it (initialize this operator to '+').
2Walk through each character, multiplying the running number by ten and adding each digit so multi-digit numbers accumulate correctly.
3When you reach a non-space operator, or the last character of the string, resolve the previously stored operator against the current number.
4For '+' push the number, for '-' push its negative, and for '*' or '/' pop the stack top and push the product or truncated quotient.
5Update the stored operator to the current character and reset the running number to zero before continuing.
6After the scan completes, add together everything left on the stack and return that total.

Implementation

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        num = 0
        op = '+'
        for i, ch in enumerate(s):
            if ch.isdigit():
                num = num * 10 + int(ch)
            if (not ch.isdigit() and ch != ' ') or i == len(s) - 1:
                if op == '+':
                    stack.append(num)
                elif op == '-':
                    stack.append(-num)
                elif op == '*':
                    stack.append(stack.pop() * num)
                elif op == '/':
                    stack.append(int(stack.pop() / num))
                op = ch
                num = 0
        return sum(stack)

Time

O(n)

Space

O(n)

Each character is visited once. The stack can hold up to one entry per additive term, which is O(n) in the worst case.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Stacks & Queues

After the pattern

Now solve one you haven't seen.

Stockroom Quantity Formula is our own problem on the technique behind Basic Calculator II: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free