Basic Calculator

Problem

Evaluate a simple arithmetic expression string with +, -, parentheses, and non-negative integers. No * or /. Integer division does not occur. Whitespace is allowed.

Constraints

• 1 ≤ s.length ≤ 3·10⁵
• s contains digits, +, -, (, ), and spaces.
• All intermediate results fit in a 32-bit int.

Approach — Stack

This is a Stack problem. The idea: scan the input once, pushing work onto a stack and popping when the top can be resolved, so the stack always reflects what's still open. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def calculate(self, s):
        res = 0
        num = 0
        sign = 1
        stack = []
        for ch in s:
            if ch.isdigit():
                num = num * 10 + int(ch)
            elif ch in '+-':
                res += sign * num; num = 0
                sign = 1 if ch == '+' else -1
            elif ch == '(':
                stack.append(res); stack.append(sign)
                res = 0; sign = 1
            elif ch == ')':
                res += sign * num; num = 0
                res *= stack.pop()
                res += stack.pop()
        return res + sign * num

Java

import java.util.Stack;

class Solution {

    public int calculate(String s) {

        int operand = 0;
        int n = 0;
        Stack<Object> stack = new Stack<>();

        for (int i = s.length() - 1; i >= 0; i--) {

            char ch = s.charAt(i);

            if (Character.isDigit(ch)) {

                // Forming the operand - in reverse order.
                operand = (int)Math.pow(10, n) * (int)(ch - '0') + operand;
                n += 1;

            } else if (ch != ' ') {
                if (n != 0) {

                    // Save the operand on the stack
                    // As we encounter some non-digit.
                    stack.push(operand);
                    n = 0;
                    operand = 0;

                }
                if (ch == '(') {

                    int res = evaluateExpr(stack);
                    stack.pop();

                    // Append the evaluated result to the stack.
                    // This result could be of a sub-expression within the parenthesis.
                    stack.push(res);

                } else {
                    // For other non-digits just push onto the stack.
                    stack.push(ch);
                }
            }
        }

        //Push the last operand to stack, if any.
        if (n != 0) {
            stack.push(operand);
        }

        // Evaluate any left overs in the stack.
        return evaluateExpr(stack);
    }

    public int evaluateExpr(Stack<Object> stack) {

        // If stack is empty or the expression starts with
        // a symbol, then append 0 to the stack.
        // i.e. [1, '-', 2, '-'] becomes [1, '-', 2, '-', 0]
        if (stack.empty() || !(stack.peek() instanceof Integer)) {
            stack.push(0);
        }

        int res = (int) stack.pop();

        // Evaluate the expression till we get corresponding ')'
        while (!stack.empty() && !((char)stack.peek() == ')')) {

            char sign = (char) stack.pop();

            if (sign == '+') {
                res += (int) stack.pop();
            } else {
                res -= (int) stack.pop();
            }
        }
        return res;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.