Course4all
Join us on telegram
Home/dsa/Stack/Basic Calculator II

Basic Calculator II

Master this topic with zero to advance depth.

Basic Calculator II

Implement a basic calculator to evaluate a simple expression string containing non-negative integers, +, -, *, / operators and empty spaces.

Visual Representation

s = "3+2*2" 1. '3': num = 3 2. '+': Push 3. num = 0, sign = '+' 3. '2': num = 2 4. '*': 2*2 = 4 (High precedence). 5. Result: 3 + 4 = 7
Medium

Examples

Input: s = "3+2*2"
Output: 7
Approach 1

Level I: Brute Force (Two-Pass: First Handle *, / Then +, -)

Intuition

Without a stack, we can handle operator precedence in two passes: First, scan for * and / and evaluate them in-place (replacing the two operands and the operator with the result). Then, sum all remaining numbers separated by + and -. This avoids the stack but requires two traversals.

⏱ O(N) — two linear passes over the token list.💾 O(N) to store the parsed tokens.
java
import java.util.*;

public class Main {
    public static int calculate(String s) {
        s = s.replaceAll(" ", "");
        // Tokenize
        List<String> tokens = new ArrayList<>();
        int i = 0;
        while (i < s.length()) {
            if (Character.isDigit(s.charAt(i))) {
                int j = i;
                while (j < s.length() && Character.isDigit(s.charAt(j))) j++;
                tokens.add(s.substring(i, j))
;               i = j;
            } else {
                tokens.add(String.valueOf(s.charAt(i++)));
            }
        }
        // Pass 1: * and /
        int j = 0;
        while (j < tokens.size()) {
            if (tokens.get(j).equals("*") || tokens.get(j).equals("/")) {
                long a = Long.parseLong(tokens.get(j-1)), b = Long.parseLong(tokens.get(j+1));
                long res = tokens.get(j).equals("*") ? a * b : a / b;
                tokens.set(j-1, String.valueOf(res));
                tokens.remove(j); tokens.remove(j);
            } else j++;
        }
        // Pass 2: + and -
        long result = Long.parseLong(tokens.get(0));
        j = 1;
        while (j < tokens.size()) {
            long num = Long.parseLong(tokens.get(j+1));
            if (tokens.get(j).equals("+")) result += num;
            else result -= num;
            j += 2;
        }
        return (int)result;
    }
    public static void main(String[] args) {
        System.out.println(calculate("3+2*2")); // 7
    }
}
Approach 2

Level III: Optimal (Single Stack Simulation)

Intuition

Use a stack to store values. For + and -, push the number (negatively for -). For * and /, pop the last value, perform the operation with the current number, and push it back. Finally, sum the stack.

⏱ O(N)💾 O(N)

Detailed Dry Run

CharNumSignStackAction
'3'3'+'[]-
'+'0'+'[3]Push 3
'2'2'+'[3]-
'*'0'*'[3]-
'2'2'*'[3]-
End--[3, 4]Pop 2, Push 2*2
java
import java.util.*;

public class Solution {
    public int calculate(String s) {
        if (s == null || s.isEmpty()) return 0;
        Stack<Integer> stack = new Stack<>();
        int num = 0;
        char sign = '+';
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) num = num * 10 + (c - '0');
            if (!Character.isDigit(c) && c != ' ' || i == s.length() - 1) {
                if (sign == '+') stack.push(num);
                if (sign == '-') stack.push(-num);
                if (sign == '*') stack.push(stack.pop() * num);
                if (sign == '/') stack.push(stack.pop() / num);
                sign = c;
                num = 0;
            }
        }
        int res = 0;
        for (int i : stack) res += i;
        return res;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.calculate("3+2*2")); // 7
    }
}

⚠️ Common Pitfalls & Tips

Division should truncate toward zero. Be careful with spaces and multi-digit numbers. Handle the last number in the string properly.

← Previous QuestionValidate Stack Sequences
Next Question →Decode String