java 71 lines · 9 steps

Evaluating math expressions with two stacks

A single-pass shunting-yard evaluator that respects operator precedence, parentheses, and right-associative exponentiation.

Explained by highlit

Intermediate stacks parsing operator-precedence shunting-yard recursion-free

1import java.util.ArrayDeque;
2import java.util.Deque;
3import java.util.Map;
4 
5public final class ExpressionEvaluator {
6 
  private static final Map<Character, Integer> PRECEDENCE = Map.of(
      '+', 1, '-', 1, '*', 2, '/', 2, '^', 3
  );
10 
  public double evaluate(String expression) {
      Deque<Double> values = new ArrayDeque<>();
      Deque<Character> operators = new ArrayDeque<>();
14 
      for (int i = 0; i < expression.length(); i++) {
          char c = expression.charAt(i);
          if (Character.isWhitespace(c)) {
              continue;
          }
          if (Character.isDigit(c) || c == '.') {
              int start = i;
              while (i < expression.length()
                  && (Character.isDigit(expression.charAt(i)) || expression.charAt(i) == '.')) {
                  i++;
              }
              values.push(Double.parseDouble(expression.substring(start, i)));
              i--;
          } else if (c == '(') {
              operators.push(c);
          } else if (c == ')') {
              while (operators.peek() != '(') {
                  values.push(apply(operators.pop(), values.pop(), values.pop()));
              }
              operators.pop();
          } else if (PRECEDENCE.containsKey(c)) {
              while (!operators.isEmpty() && hasPrecedence(operators.peek(), c)) {
                  values.push(apply(operators.pop(), values.pop(), values.pop()));
              }
              operators.push(c);
          } else {
              throw new IllegalArgumentException("Unexpected character: " + c);
          }
      }
44 
      while (!operators.isEmpty()) {
          values.push(apply(operators.pop(), values.pop(), values.pop()));
      }
      return values.pop();
  }
50 
  private boolean hasPrecedence(char stackOp, char current) {
      if (stackOp == '(') {
          return false;
      }
      if (current == '^') {
          return PRECEDENCE.get(stackOp) > PRECEDENCE.get(current);
      }
      return PRECEDENCE.get(stackOp) >= PRECEDENCE.get(current);
  }
60 
  private double apply(char op, double b, double a) {
      return switch (op) {
          case '+' -> a + b;
          case '-' -> a - b;
          case '*' -> a * b;
          case '/' -> a / b;
          case '^' -> Math.pow(a, b);
          default -> throw new IllegalStateException("Unknown operator: " + op);
      };
  }
71}

01 / 01

STEP 01

Walkthrough

Space play ←→ step click any line

Three takeaways

1Two stacks — one for values, one for operators — let you evaluate infix expressions in a single left-to-right pass.
2Flushing higher-or-equal precedence operators before pushing a new one enforces correct evaluation order without building a tree.
3Treating exponentiation with strict '>' instead of '>=' cleanly encodes right-associativity.

Related explainers

ruby

class UserAgentParser
  BROWSERS = [
    [/Edg\/([\d.]+)/, "Edge"],
    [/OPR\/([\d.]+)/, "Opera"],

Parsing user-agent strings in Ruby

regex pattern-matching lookup-tables

Intermediate 8 steps

java

@Component
@Converter
public class EncryptedStringConverter implements AttributeConverter<String, String> {

Transparent column encryption in Spring & JPA

encryption aes-gcm jpa-converter

Advanced 10 steps

javascript

function evaluate(expression) {
  const tokens = tokenize(expression);
  let pos = 0;

Building a recursive descent calculator

parsing recursion operator-precedence

Intermediate 8 steps

java

package com.acme.billing.config;
 
import org.springframework.boot.autoconfigure.condition.ConditionalOnProperty;
import org.springframework.boot.context.properties.ConfigurationProperties;

Feature-flagged beans with Spring @ConditionalOnProperty

feature-flags conditional-beans strategy-pattern

Intermediate 5 steps

rust

use chrono::{Duration, NaiveDate};
 
#[derive(Debug)]
pub struct DateRange {

Parsing and iterating date ranges in Rust

error-handling iterators parsing

Intermediate 7 steps

java

public static Map<String, String> parseCookieHeader(String header) {
    Map<String, String> cookies = new LinkedHashMap<>();
    if (header == null || header.isBlank()) {
        return cookies;