Basic Calculator II

This question hides a trap that catches many people. The expression has plus, minus, times and divide all mixed together. So you cannot just go left to right. Times and divide must happen before plus and minus. The interviewer wants to see if you can respect that order with a clean stack. So this is a precedence puzzle in disguise.

🎯 The Problem

You get a math expression as a string and you compute its result.

• It has whole numbers and the four operators +, -, *, /.
• There are no parentheses. There may be spaces.
• The catch is precedence, the rule for which operator runs first.
• Times and divide run before plus and minus.
• Divide truncates toward zero, meaning it drops the fractional part. So 7 / 2 is 3 and -7 / 2 is -3, never rounding away.

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

Explanation: 2*2 runs first because times beats plus.
That gives 4. Then 3 + 4 = 7.

Here is the expression broken into pieces. Notice that 2*2 is grouped first, before the plus.

🐢 Approach 1: Two-Pass Rewrite (Brute Force)

The idea in one line: in the first pass do all the times and divide, then in the second pass add and subtract what is left.

The idea:

• Pass one: handle only * and /.
• Pass two: handle only + and -.

How it works:

• In pass one, wherever you see * or /, compute that piece and replace it with the result.
• After pass one, only plus and minus remain.
• In pass two, add and subtract the leftover numbers left to right.

Why it is weak:

• You build a new list of numbers and operators.
• Then you walk that list a second time.
• It works, but it scans the data more than once and uses extra structures.

Here is the two-pass token code:

def calculate(s):
    nums, ops, num = [], [], 0
    for ch in s + "+":
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch in "+-*/":
            nums.append(num)
            ops.append(ch)
            num = 0

    i = 0
    while i < len(ops) - 1:
        if ops[i] in "*/":
            a, b = nums[i], nums.pop(i + 1)
            nums[i] = a * b if ops[i] == "*" else int(a / b)
            ops.pop(i)
        else:
            i += 1

    total = nums[0]
    for op, num in zip(ops, nums[1:]):
        total = total + num if op == "+" else total - num
    return total

⚡ Approach 2: One Pass With a Stack (Best)

The idea in one line: push numbers for plus and minus, but apply times and divide to the stack top right away.

The idea:

• A stack is a pile where you add and remove from the top.
• Keep the last operator you saw. Start it as +, since the first number is added.
• Build the current number digit by digit.

How each operator is handled:

• On +, push the number.
• On -, push its negative, since subtracting later is the same as adding a negative.
• On *, pop the top, multiply by the number, push the result.
• On /, pop the top, divide by the number truncating toward zero, push the result.

Why it respects precedence:

• Times and divide change the stack top right away, before it ever gets added.
• Plus and minus just leave numbers on the stack.
• Sum the whole stack at the end and you get the answer.
• This is one pass, which is O(n).

Here is the stack changing as we read "3+2*2". Watch how * reaches into the stack while + just pushes.

Steps to Solve

1. Create an empty stack of numbers. Set the current number to 0 and the last operator to +.
2. Read the string character by character.
3. If the character is a digit, fold it into the current number.
4. If the character is an operator, or you reached the end, apply the last operator to the current number.
5. For + push the number, for - push its negative, for * multiply the top, for / divide the top truncating toward zero.
6. Save the new operator and reset the current number to 0.
7. After the scan, add up everything in the stack. That sum is the answer.

#include <stdio.h>
#include <string.h>
#include <ctype.h>

int calculate(const char* s) {
    int stack[100000];
    int top = -1;        // empty stack
    int num = 0;
    char op = '+';       // first number is added
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        char c = s[i];
        if (isdigit(c)) {
            num = num * 10 + (c - '0');  // build the number
        }
        // act on an operator, or at the very last character
        if ((!isdigit(c) && c != ' ') || i == len - 1) {
            if (op == '+') {
                stack[++top] = num;
            } else if (op == '-') {
                stack[++top] = -num;
            } else if (op == '*') {
                stack[top] = stack[top] * num;
            } else if (op == '/') {
                stack[top] = stack[top] / num;  // C truncates toward zero
            }
            op = c;     // remember this operator
            num = 0;    // reset for the next number
        }
    }
    int sum = 0;
    for (int i = 0; i <= top; i++) sum += stack[i];
    return sum;
}

int main(void) {
    const char* s = "3+2*2";
    printf("%d\n", calculate(s));
    return 0;
}

7

#include <iostream>
#include <vector>
#include <string>
#include <cctype>
using namespace std;

int calculate(const string& s) {
    vector<int> stack;
    int num = 0;
    char op = '+';   // first number is added
    int len = s.size();
    for (int i = 0; i < len; i++) {
        char c = s[i];
        if (isdigit(c)) {
            num = num * 10 + (c - '0');  // build the number
        }
        // act on an operator, or at the very last character
        if ((!isdigit(c) && c != ' ') || i == len - 1) {
            if (op == '+') stack.push_back(num);
            else if (op == '-') stack.push_back(-num);
            else if (op == '*') stack.back() = stack.back() * num;
            else if (op == '/') stack.back() = stack.back() / num; // truncates
            op = c;   // remember this operator
            num = 0;  // reset for next number
        }
    }
    int sum = 0;
    for (int v : stack) sum += v;
    return sum;
}

int main() {
    string s = "3+2*2";
    cout << calculate(s) << endl;
    return 0;
}

7

import java.util.ArrayDeque;
import java.util.Deque;

public class BasicCalculator {
    public static int calculate(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        int num = 0;
        char op = '+';  // first number is added
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');  // build the number
            }
            // act on an operator, or at the very last character
            if ((!Character.isDigit(c) && c != ' ') || i == len - 1) {
                if (op == '+') stack.push(num);
                else if (op == '-') stack.push(-num);
                else if (op == '*') stack.push(stack.pop() * num);
                else if (op == '/') stack.push(stack.pop() / num); // truncates
                op = c;   // remember this operator
                num = 0;  // reset for next number
            }
        }
        int sum = 0;
        while (!stack.isEmpty()) sum += stack.pop();
        return sum;
    }

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

7

def calculate(s):
    stack = []
    num = 0
    op = "+"           # first number is added
    n = len(s)
    for i, c in enumerate(s):
        if c.isdigit():
            num = num * 10 + int(c)   # build the number
        # act on an operator, or at the very last character
        if (not c.isdigit() and c != " ") or i == n - 1:
            if op == "+":
                stack.append(num)
            elif op == "-":
                stack.append(-num)
            elif op == "*":
                stack.append(stack.pop() * num)
            elif op == "/":
                # int() truncates toward zero, even for negatives
                stack.append(int(stack.pop() / num))
            op = c       # remember this operator
            num = 0      # reset for next number
    return sum(stack)


s = "3+2*2"
print(calculate(s))

7

function calculate(s) {
  const stack = [];
  let num = 0;
  let op = "+"; // first number is added
  const n = s.length;
  for (let i = 0; i < n; i++) {
    const c = s[i];
    if (c >= "0" && c <= "9") {
      num = num * 10 + (c.charCodeAt(0) - 48); // build the number
    }
    // act on an operator, or at the very last character
    if ((!(c >= "0" && c <= "9") && c !== " ") || i === n - 1) {
      if (op === "+") stack.push(num);
      else if (op === "-") stack.push(-num);
      else if (op === "*") stack.push(stack.pop() * num);
      else if (op === "/") stack.push(Math.trunc(stack.pop() / num)); // truncates
      op = c; // remember this operator
      num = 0; // reset for next number
    }
  }
  return stack.reduce((a, b) => a + b, 0);
}

const s = "3+2*2";
console.log(calculate(s));

7

Let us read the Python version line by line so the precedence logic is clear.

stack = [] starts the empty list of numbers we will add up at the end.

num = 0 holds the number we are building right now, one digit at a time.

op = "+" remembers the operator that came before the current number. We start with + because the first number is simply added.

if c.isdigit(): checks if the character is a digit. If yes, num = num * 10 + int(c) shifts the number left and adds the new digit. So "23" becomes 2, then 23.

if (not c.isdigit() and c != " ") or i == n - 1: is the key trigger. We act when we hit an operator, or when we reach the very last character. The last character matters because there is no operator after it to trigger the final number.

if op == "+": stack.append(num) pushes the number to be added later. elif op == "-": stack.append(-num) pushes the negative, because subtracting later is the same as adding a negative.

elif op == "*": stack.append(stack.pop() * num) pops the top, multiplies it by the current number, and pushes the result. This applies times right away, before any addition.

elif op == "/": stack.append(int(stack.pop() / num)) does the same for divide. We use int() on a true division so the result truncates toward zero, which is the rule the problem wants.

op = c saves the operator we just saw, so the next number knows what to do. num = 0 clears the builder for the next number.

return sum(stack) adds the whole stack. Because times and divide were already handled on the top, this final sum gives the correct answer.

⏱️ Time and Space Complexity

The two-pass idea reads the data more than once and builds extra structures. The stack version reads the string a single time. So it runs in O(n) time, where n is the length of the string. The stack can hold roughly one number per term, so it needs O(n) extra memory.

🧩 Key Takeaways

• ✅ Times and divide must run before plus and minus, so they cannot wait until the end.
• ✅ Push numbers for plus and minus, but apply times and divide to the stack top right away.
• ✅ Subtraction is just pushing a negative number, which keeps the final step a simple sum.
• ✅ Trigger the operator logic on each operator and also on the very last character.
• ✅ Divide truncates toward zero, so watch out for negative results in Python and JavaScript.

🚀 What’s Next?

• Max Stack
• Asteroid Collision