Basic Calculator II

Problem

Evaluate a simple arithmetic expression string containing non-negative integers and the operators +, -, , /. Operators follow standard precedence ( and / before + and -). Integer division truncates toward zero. The expression has no parentheses.

Constraints

• 1 ≤ s.length ≤ 3·10⁵
• s contains digits, +, -, *, / and spaces only.
• 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):
        st = []
        num = 0
        op = '+'
        for i, c in enumerate(s):
            if c.isdigit():
                num = num * 10 + int(c)
            if c in '+-*/' or i == len(s) - 1:
                if op == '+':
                    st.append(num)
                elif op == '-':
                    st.append(-num)
                elif op == '*':
                    st.append(st.pop() * num)
                else:
                    st.append(int(st.pop() / num))
                op = c
                num = 0
        return sum(st)

Java

import java.util.Stack;

class Solution {
    public int calculate(String s) {

        if (s == null || s.isEmpty()) return 0;
        int length = s.length();
        Stack<Integer> stack = new Stack<>();
        int currentNumber = 0;
        char operation = '+';
        for (int i = 0; i < length; i++) {
            char currentChar = s.charAt(i);
            if (Character.isDigit(currentChar)) {
                currentNumber = (currentNumber * 10) + (currentChar - '0');
            }
            if (!Character.isDigit(currentChar) && !Character.isWhitespace(currentChar) || i == length - 1) {
                if (operation == '-') {
                    stack.push(-currentNumber);
                }
                else if (operation == '+') {
                    stack.push(currentNumber);
                }
                else if (operation == '*') {
                    stack.push(stack.pop() * currentNumber);
                }
                else if (operation == '/') {
                    stack.push(stack.pop() / currentNumber);
                }
                operation = currentChar;
                currentNumber = 0;
            }
        }
        int result = 0;
        while (!stack.empty()) {
            result += stack.pop();
        }
        return result;
    }
}

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.