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 
7 private static final Map<Character, Integer> PRECEDENCE = Map.of(
8 '+', 1, '-', 1, '*', 2, '/', 2, '^', 3
9 );
10 
11 public double evaluate(String expression) {
12 Deque<Double> values = new ArrayDeque<>();
13 Deque<Character> operators = new ArrayDeque<>();
14 
15 for (int i = 0; i < expression.length(); i++) {
16 char c = expression.charAt(i);
17 if (Character.isWhitespace(c)) {
18 continue;
19 }
20 if (Character.isDigit(c) || c == '.') {
21 int start = i;
22 while (i < expression.length()
23 && (Character.isDigit(expression.charAt(i)) || expression.charAt(i) == '.')) {
24 i++;
25 }
26 values.push(Double.parseDouble(expression.substring(start, i)));
27 i--;
28 } else if (c == '(') {
29 operators.push(c);
30 } else if (c == ')') {
31 while (operators.peek() != '(') {
32 values.push(apply(operators.pop(), values.pop(), values.pop()));
33 }
34 operators.pop();
35 } else if (PRECEDENCE.containsKey(c)) {
36 while (!operators.isEmpty() && hasPrecedence(operators.peek(), c)) {
37 values.push(apply(operators.pop(), values.pop(), values.pop()));
38 }
39 operators.push(c);
40 } else {
41 throw new IllegalArgumentException("Unexpected character: " + c);
42 }
43 }
44 
45 while (!operators.isEmpty()) {
46 values.push(apply(operators.pop(), values.pop(), values.pop()));
47 }
48 return values.pop();
49 }
50 
51 private boolean hasPrecedence(char stackOp, char current) {
52 if (stackOp == '(') {
53 return false;
54 }
55 if (current == '^') {
56 return PRECEDENCE.get(stackOp) > PRECEDENCE.get(current);
57 }
58 return PRECEDENCE.get(stackOp) >= PRECEDENCE.get(current);
59 }
60 
61 private double apply(char op, double b, double a) {
62 return switch (op) {
63 case '+' -> a + b;
64 case '-' -> a - b;
65 case '*' -> a * b;
66 case '/' -> a / b;
67 case '^' -> Math.pow(a, b);
68 default -> throw new IllegalStateException("Unknown operator: " + op);
69 };
70 }
71}
01 / 01
STEP 01

Walkthrough

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

Related explainers

java 
public interface GitHubClient {
 
    @GetExchange("/users/{username}")
    GitHubUser getUser(@PathVariable String username);

Declarative HTTP clients in Spring

http-client declarative-api proxy
Intermediate 8 steps
java 
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

Building a trie for autocomplete in Java

trie prefix-tree recursion
Intermediate 8 steps
rust 
use std::net::Ipv4Addr;
use std::str::FromStr;
 
#[derive(Debug, Clone, Copy)]

Parsing and matching IPv4 CIDR ranges in Rust

bitwise-operations parsing error-handling
Intermediate 8 steps
java 
@RestController
@RequestMapping("/api/products")
public class ProductSearchController {
 

Binding collection query params in Spring

rest-api query-parameters dependency-injection
Intermediate 6 steps
java 
@Entity
@Table(name = "orders")
@SQLDelete(sql = "UPDATE orders SET deleted = true, deleted_at = now() WHERE id = ?")
@Where(clause = "deleted = false")

Soft deletes with Hibernate in Spring

soft-delete jpa hibernate
Intermediate 9 steps
python 
def is_valid_card_number(number: str) -> bool:
    digits = [int(c) for c in number if c.isdigit()]
 
    if len(digits) < 13 or len(digits) > 19:

Validating card numbers with the Luhn check

checksum validation luhn-algorithm
Intermediate 6 steps

Share this explainer

Here's the card — post it anywhere.

Evaluating math expressions with two stacks — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code