Basic Calculator II

Medium Stack Stack Basics Original on LeetCode

Basic Calculator II is a medium stack problem solved with the stack basics pattern. The best approach, optimal (running total and last term, no stack), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (stack of signed terms) up.

Problem

You are given a string s holding an arithmetic expression made of non-negative integers, the operators +, -, *, /, and spaces. Evaluate it and return the integer result.

The usual precedence applies: * and / are done before + and -, and operators of the same precedence go left to right. Integer division truncates toward zero. You may not use any built-in function that evaluates a string as code.

Examples

Example 1

Input
s = "7 - 12 / 4 * 2"
Output
1
Why
12 / 4 = 3, then 3 * 2 = 6, and 7 - 6 = 1.

Example 2

Input
s = " 9 / 2 + 3*3 "
Output
13
Why
9 / 2 truncates to 4, 3 * 3 = 9, so 4 + 9 = 13. Spaces can appear anywhere.

Example 3

Input
s = "8-7/2"
Output
5
Why
7 / 2 truncates to 3 and 8 - 3 = 5.

Constraints

  • 1 <= s.length <= 3 * 10^5
  • s has digits, spaces and the operators + - * / only; there are no brackets.
  • s is a valid expression and every number in it is a non-negative integer below 2^31.
  • Every intermediate result and the final answer fit in a 32-bit signed integer.
  • Division truncates toward zero; no library eval.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (stack of signed terms)O(n)O(n)
Optimal (running total and last term, no stack)O(n)O(1)

1Brute force (stack of signed terms)

TimeO(n)Each character is read once and each term is pushed and popped at most once.
SpaceO(n)The stack can hold one entry per number in the expression.

Read the string left to right, remembering the operator seen before the current number. When a number ends, apply that operator: + pushes the number, - pushes its negation, * and / pop the last term, combine it with the number and push the result. The answer is the sum of the stack.

  1. op = '+', num = 0, empty stack.
  2. For each character: if it is a digit, num = num * 10 + digit.
  3. If it is an operator, or it is the last character: apply op to num (push num, push -num, push pop * num, or push pop / num), then op = this character and num = 0.
  4. Return the sum of all values in the stack.
class Solution {
    public int calculate(String s) {
        Deque<Integer> st = new ArrayDeque<>();
        int num = 0;
        char op = '+';
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            }
            if ((!Character.isDigit(c) && c != ' ') || i == n - 1) {
                if (op == '+') {
                    st.push(num);
                } else if (op == '-') {
                    st.push(-num);
                } else if (op == '*') {
                    st.push(st.pop() * num);
                } else {
                    st.push(st.pop() / num);
                }
                op = c;
                num = 0;
            }
        }
        int result = 0;
        for (int x : st) {
            result += x;
        }
        return result;
    }
}

2Optimal (running total and last term, no stack)

TimeO(n)One pass over the string with O(1) work per character.
SpaceO(1)Only a handful of integer variables.

Only the top of the stack is ever changed, and everything beneath it is just added at the end. So keep total (the sum of finished terms) and last (the term still being built). + or - moves last into total and starts a new term; * and / update last in place.

  1. total = 0, last = 0, num = 0, op = '+'.
  2. Build num from digits as before.
  3. When a number ends: for + or -, total += last and last = ±num; for *, last = last * num; for /, last = last / num (truncated).
  4. Set op to the current character and reset num.
  5. Return total + last.
class Solution {
    public int calculate(String s) {
        int total = 0, last = 0, num = 0;
        char op = '+';
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            }
            if ((!Character.isDigit(c) && c != ' ') || i == n - 1) {
                if (op == '+' || op == '-') {
                    total += last;
                    last = op == '+' ? num : -num;
                } else if (op == '*') {
                    last = last * num;
                } else {
                    last = last / num;
                }
                op = c;
                num = 0;
            }
        }
        return total + last;
    }
}

Edge cases to test

  • A single number with no operators
  • Spaces before, after and between tokens
  • Multi-digit numbers
  • Division that truncates, including a negative term like 2 - 7 / 2
  • A chain of * and / that must be applied left to right

Hints

Hint 1

* and / bind tighter than + and -. Think of the expression as a sum of terms, where each term is a run of products and quotients.

Hint 2

When you finish reading a number, you know the operator in front of it. + and - start a new term; * and / change the last term.

Hint 3

You only ever modify the most recent term, so a single variable can replace the stack.

FAQ

What is the best time complexity for Basic Calculator II?

Optimal (running total and last term, no stack) runs in O(n) time and O(1) extra space. One pass over the string with O(1) work per character.

Which pattern does Basic Calculator II use?

It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.

Is there a brute force solution for Basic Calculator II?

Yes. Brute force (stack of signed terms) takes O(n) time and O(n) space. Read the string left to right, remembering the operator seen before the current number.

Which edge cases should I test for Basic Calculator II?

A single number with no operators; Spaces before, after and between tokens; Multi-digit numbers; Division that truncates, including a negative term like 2 - 7 / 2; A chain of and / that must be applied left to right.