Expression Evaluation

Basic Calculator

Handle expressions with +, −, and parentheses. Use a stack to save the current result and sign when entering '(', then restore when leaving ')'. Process digits into numbers and apply the current sign.

O(n)

How It Works

Evaluating an infix expression with +, −, and parentheses works with a running result, a current sign, and a stack for suspended contexts. Digits accumulate into the current number; on + or −, fold the finished number into the result and record the new sign. An opening parenthesis pushes the result and sign accumulated so far and resets both, because the parenthesized group must be evaluated as its own unit. A closing parenthesis finishes the inner result, pops the saved sign and outer result, and combines them as outer + sign × inner.

Each character is touched once, so the algorithm is O(n) time and O(d) space where d is the nesting depth — far cleaner than repeatedly rewriting innermost parentheses, which degrades to O(n²).

Step-by-Step Visualization

Calculate '(1+(4+5))'

Input

(

)

Stack

Pushresult=0, sign=1

1/4

Code

Java

static int calculate(String s) {
  Stack<Integer> stack = new Stack<>();
  int result = 0, num = 0, sign = 1;

  for (char ch : s.toCharArray()) {
    if (ch >= '0' && ch <= '9') num = num * 10 + (ch - '0');
    else if (ch == '+' || ch == '-') {
      result += sign * num;
      num = 0;
      sign = ch == '+' ? 1 : -1;
    } else if (ch == '(') {
      stack.push(result);
      stack.push(sign);
      result = 0; sign = 1;
    } else if (ch == ')') {
      result += sign * num; num = 0;
      result *= stack.pop(); // sign
      result += stack.pop(); // prev result
    }
  }
  return result + sign * num;
}

Tips & Gotchas

1Use stack to save result and sign before entering parentheses

2Track current number and running result with a sign multiplier

3On '(' push result and sign, on ')' pop and combine

Practice Problems

1Basic Calculator
2Basic Calculator II
3Basic Calculator III
4Evaluate Reverse Polish Notation

About the Expression Evaluation Pattern

Evaluate mathematical expressions by converting them into a format that's easy for a stack to process (like Reverse Polish Notation), or by using a stack to handle operator precedence and nested parentheses.

Key insight

Monotonic stacks are the power tool here. If you need 'next greater/smaller element' or 'span' queries, a monotonic stack gives O(n) instead of O(n²).

Common Stack Interview Problems

Valid Parentheses
Next Greater Element
Largest Rectangle in Histogram
Trapping Rain Water
Daily Temperatures
Decode String

Frequently Asked Questions

What changes when multiplication and division are added?

You need precedence handling: keep the previous operand pending so that * and / can consume it immediately, while + and − commit it to the running total. A common pattern pushes signed terms onto a stack and multiplies the stack top in place for * and /, summing everything at the end.

How should unary minus, as in '-(2 + 3)', be handled?

Treat a minus that appears at the start of the expression or right after '(' as a sign on the upcoming term rather than a binary operator. Initializing the current sign to −1 in those positions handles it without extra token types.

Why push the sign along with the result at '('?

The sign directly before the parenthesis applies to the entire group, not just its first term. Saving it lets you compute the group independently and then apply outer + savedSign × inner when the ')' closes, which correctly distributes cases like 5 − (1 + 2).