Computer Science A

Course Progress 0/0
Week 25 RPN Calculator - Interactive Lesson

RPN Calculator - Interactive Lesson

23 min read
  • Step 7: The Complete Calculator
  • Knowledge Check
    • Final Knowledge Check
  • Key Takeaways

    • How Do Computers Solve Math?

    When you type (100 + 200) * 3 into a calculator, you instinctively know to add first, then multiply. But computers don’t think like humans — they need a systematic algorithm to handle:

    • Operator precedence (* before +)
    • Parentheses (grouping overrides precedence)
    • Left-to-right evaluation

    The solution? Reverse Polish Notation (RPN) — a technique invented by Polish mathematician Jan Łukasiewicz and popularized by Hewlett-Packard calculators in the 1970s.

    The Pipeline

    Expression String → Tokenize → Convert to RPN → Evaluate → Result
"(100 + 200) * 3" → [100, +, 200, *, 3] → [100, 200, +, 3, *] → 900

    Key Data Structures

    Structure Used For Why
    ArrayList Storing tokens & RPN output Ordered sequence, index access
    Stack Operator reordering & calculation LIFO — last operator in is first out
    HashMap Looking up operators by character O(1) lookup for precedence & calculation

    Let’s build each piece step by step.

    Step 1: The Token Class

    Every part of a math expression is a Token — a number, an operator (+, -, *, /), or a parenthesis.

    The Token class stores:

    • The character (e.g. +, *)
    • The precedence (multiplication before addition)
    • The calculation function (what the operator actually does)

    Key Concept: We use Java’s BiFunction<Double, Double, Double> — a functional interface that takes two doubles and returns a double. This lets us store math operations as data.

    Challenge: Read the Token class below, then modify it to add a POWER operator check.

    Run the code to see the test output.

    import java.util.function.BiFunction;

public class Token {
    private final Character token;
    private final int precedence;
    private final BiFunction<Double, Double, Double> calculation;
    private final int numArgs;

    // Constructor for passive/non-operator tokens
    public Token() { this('0'); }

    // Constructor for simple token (parenthesis)
    public Token(Character token) { this(token, 0, null, 0); }

    // Full constructor for operators
    public Token(Character token, int precedence, BiFunction<Double, Double, Double> calculation, int numArgs) {
        this.token = token;
        this.precedence = precedence;
        this.calculation = calculation;
        this.numArgs = numArgs;
    }

    public Character getToken() { return token; }
    public int getPrecedence() { return precedence; }
    public int getNumArgs() { return numArgs; }

    // Returns true if THIS token has higher precedence (lower number = higher priority)
    public boolean isPrecedent(Token other) {
        return this.precedence > other.getPrecedence();
    }

    // Execute the math operation
    public Double calculate(Double a, Double b) {
        return this.calculation.apply(a, b);
    }

    public String toString() { return this.token.toString(); }
}

// --- TEST ---
Token add = new Token('+', 4, (a, b) -> a + b, 2);
Token mul = new Token('*', 3, (a, b) -> a * b, 2);
Token paren = new Token('(');

System.out.println("Token '+' precedence: " + add.getPrecedence());
System.out.println("Token '*' precedence: " + mul.getPrecedence());
System.out.println("Does '+' yield to '*'? " + add.isPrecedent(mul));
System.out.println("3 + 5 = " + add.calculate(3.0, 5.0));
System.out.println("3 * 5 = " + mul.calculate(3.0, 5.0));

// TODO: Create a POWER token ('^', precedence 2) and test 2^10

    Code Runner Challenge

    Read the Token class. It represents a single element in a math expression — an operator with its precedence and calculation function. The test creates a few tokens and checks precedence. Try modifying the test to create a POWER token with precedence 2.

    Lines: 1 Characters: 0
    Output
    Click "Run" in code control panel to see output ...

    Popcorn Hack 1: Precedence Check

    In the Token class, lower precedence numbers mean higher priority. Given Token add = new Token('+', 4, ...) and Token mul = new Token('*', 3, ...), what does add.isPrecedent(mul) return?

    Step 2: TermOrOperator — Subclass of Token

    A TermOrOperator extends Token to also represent numeric values. This is an example of inheritance — the key AP CSA concept.

    • If it’s a number: stores the value as a String (e.g. "100", "3.14")
    • If it’s an operator: inherits the token, precedence, and calculation from Token
    • If it’s a parenthesis: just stores the character

    Why inheritance? Both numbers and operators need to live in the same ArrayList. By making them share a parent class, we can store ArrayList<TermOrOperator> and treat them polymorphically.

    Challenge: Run the code to see how different TermOrOperator types behave.

    import java.util.function.BiFunction;

// --- Token (parent class) ---
class Token {
    private final Character token;
    private final int precedence;
    private final BiFunction<Double, Double, Double> calculation;
    private final int numArgs;

    public Token() { this('0'); }
    public Token(Character token) { this(token, 0, null, 0); }
    public Token(Character token, int precedence, BiFunction<Double, Double, Double> calculation, int numArgs) {
        this.token = token;
        this.precedence = precedence;
        this.calculation = calculation;
        this.numArgs = numArgs;
    }
    public Character getToken() { return token; }
    public int getPrecedence() { return precedence; }
    public int getNumArgs() { return numArgs; }
    public boolean isPrecedent(Token t) { return this.precedence > t.getPrecedence(); }
    public Double calculate(Double a, Double b) { return this.calculation.apply(a, b); }
    public String toString() { return this.token.toString(); }
}

// --- TermOrOperator (child class) ---
class TermOrOperator extends Token {
    private final String value;

    // Constructor for numeric values
    public TermOrOperator(String value) {
        this.value = value;
    }

    // Constructor for parenthesis
    public TermOrOperator(Character token) {
        super(token);
        this.value = null;
    }

    // Constructor for binary operators
    public TermOrOperator(Character token, int precedence, BiFunction<Double, Double, Double> calculation) {
        super(token, precedence, calculation, 2);
        this.value = null;
    }

    // Constructor for unary operators (like sqrt)
    public TermOrOperator(Character token, int precedence, BiFunction<Double, Double, Double> calculation, int numArgs) {
        super(token, precedence, calculation, numArgs);
        this.value = null;
    }

    public String getValue() { return value; }

    public String toString() {
        return (this.value != null) ? this.value : super.toString();
    }
}

// --- TEST ---
TermOrOperator num = new TermOrOperator("42");
TermOrOperator plus = new TermOrOperator('+', 4, (a, b) -> a + b);
TermOrOperator openParen = new TermOrOperator('(');

System.out.println("Number token: " + num + " (value=" + num.getValue() + ")");
System.out.println("Operator token: " + plus + " (precedence=" + plus.getPrecedence() + ")");
System.out.println("Parenthesis token: " + openParen);
System.out.println();
System.out.println("Polymorphism demo — all in one ArrayList:");
java.util.ArrayList<TermOrOperator> list = new java.util.ArrayList<>();
list.add(openParen);
list.add(num);
list.add(plus);
list.add(new TermOrOperator("8"));
list.add(new TermOrOperator(')'));
System.out.println(list);

// TODO: Create a modulo operator (%, precedence 3) and test 10 % 3

    Code Runner Challenge

    TermOrOperator extends Token to also hold numeric values. Run the code to see the three types: value, operator, and parenthesis. Then try adding a new operator for modulo (%).

    Lines: 1 Characters: 0
    Output
    Click "Run" in code control panel to see output ...

    Popcorn Hack 2: Inheritance & Polymorphism

    We store both numbers and operators in ArrayList<TermOrOperator>. Which AP CSA concept makes this possible?

    Encapsulation — private fields hide implementation
    Polymorphism — subclass objects stored as parent type
    Abstraction — Token is an abstract class
    Overloading — multiple constructors in Token

    Step 3: Tokens Map — Fast Operator Lookup

    The Tokens class uses a HashMap to store all operators and separators. This gives us O(1) lookup — when we encounter a character in the expression, we can instantly check:

    1. Is it an operator? → operators.contains('+')
    2. What’s its precedence? → operators.getPrecedence('+')
    3. How does it calculate? → operators.get('+').calculate(3, 5)

    AP CSA Connection: This is a real-world use of HashMap<K, V> — one of the most important data structures.

    Challenge: Run the code and then add the ^ (power) operator to the map.

    import java.util.Map;
import java.util.HashMap;
import java.util.function.BiFunction;

// Compact Token + TermOrOperator for this runner
class Token {
    private final Character token;
    private final int precedence;
    private final BiFunction<Double, Double, Double> calculation;
    private final int numArgs;
    public Token() { this('0'); }
    public Token(Character token) { this(token, 0, null, 0); }
    public Token(Character token, int precedence, BiFunction<Double, Double, Double> calc, int numArgs) {
        this.token = token; this.precedence = precedence; this.calculation = calc; this.numArgs = numArgs;
    }
    public Character getToken() { return token; }
    public int getPrecedence() { return precedence; }
    public int getNumArgs() { return numArgs; }
    public boolean isPrecedent(Token t) { return this.precedence > t.getPrecedence(); }
    public Double calculate(Double a, Double b) { return calculation.apply(a, b); }
    public String toString() { return token.toString(); }
}

class TermOrOperator extends Token {
    private final String value;
    public TermOrOperator(String value) { this.value = value; }
    public TermOrOperator(Character token) { super(token); this.value = null; }
    public TermOrOperator(Character token, int prec, BiFunction<Double, Double, Double> calc) {
        super(token, prec, calc, 2); this.value = null;
    }
    public TermOrOperator(Character token, int prec, BiFunction<Double, Double, Double> calc, int n) {
        super(token, prec, calc, n); this.value = null;
    }
    public String getValue() { return value; }
    public String toString() { return value != null ? value : super.toString(); }
}

// --- Tokens Map (HashMap wrapper) ---
class Tokens {
    private Map<Character, TermOrOperator> map = new HashMap<>();

    public void put(Character token) {
        map.put(token, new TermOrOperator(token));
    }
    public void put(Character token, int prec, BiFunction<Double, Double, Double> calc) {
        map.put(token, new TermOrOperator(token, prec, calc));
    }
    public void put(Character token, int prec, BiFunction<Double, Double, Double> calc, int n) {
        map.put(token, new TermOrOperator(token, prec, calc, n));
    }
    public TermOrOperator get(Character token) { return map.get(token); }
    public boolean contains(Character token) { return map.containsKey(token); }
    public String toString() { return map.toString(); }
}

// --- TEST ---
Tokens ops = new Tokens();
ops.put('+', 4, (a, b) -> a + b);
ops.put('-', 4, (a, b) -> a - b);
ops.put('*', 3, (a, b) -> a * b);
ops.put('/', 3, (a, b) -> a / b);
ops.put('%', 3, (a, b) -> a % b);

System.out.println("Operator map: " + ops);
System.out.println("Contains '+'? " + ops.contains('+'));
System.out.println("Contains 'x'? " + ops.contains('x'));
System.out.println("Precedence of '+': " + ops.get('+').getPrecedence());
System.out.println("Precedence of '*': " + ops.get('*').getPrecedence());
System.out.println("10 / 3 = " + ops.get('/').calculate(10.0, 3.0));
System.out.println("10 % 3 = " + ops.get('%').calculate(10.0, 3.0));

// TODO: Add power operator (^, precedence 2, Math.pow) and test 2^8

    Code Runner Challenge

    The Tokens class uses a HashMap for O(1) operator lookup. Run to see all registered operators. Then add the power operator (^, precedence 2, Math.pow).

    Lines: 1 Characters: 0
    Output
    Click "Run" in code control panel to see output ...

    Popcorn Hack 3: HashMap Lookup

    The Tokens class uses HashMap<Character, TermOrOperator>. What is the time complexity of checking operators.contains('+')?

    Step 4: Tokenizing an Expression

    Before we can do any math, we need to break the expression string into tokens. This is called tokenization — the same concept compilers use to parse source code.

    "(100 + 200) * 3" → [(, 100, +, 200, ), *, 3]

    The algorithm walks character by character:

    • If it’s a digit or decimal point → accumulate into a multi-character number
    • If it’s an operator or separator → flush the accumulated number, then add the operator
    • Spaces are separators but don’t get added as tokens

    Challenge: Run the tokenizer on different expressions to see how it breaks them down.

    import java.util.*;
import java.util.function.BiFunction;

class Token {
    private final Character token; private final int precedence;
    private final BiFunction<Double, Double, Double> calc; private final int numArgs;
    public Token() { this('0'); }
    public Token(Character t) { this(t,0,null,0); }
    public Token(Character t, int p, BiFunction<Double,Double,Double> c, int n) { token=t; precedence=p; calc=c; numArgs=n; }
    public Character getToken() { return token; }
    public int getPrecedence() { return precedence; }
    public int getNumArgs() { return numArgs; }
    public boolean isPrecedent(Token t) { return precedence > t.getPrecedence(); }
    public Double calculate(Double a, Double b) { return calc.apply(a,b); }
    public String toString() { return token.toString(); }
}
class TermOrOperator extends Token {
    private final String value;
    public TermOrOperator(String v) { value=v; }
    public TermOrOperator(Character t) { super(t); value=null; }
    public TermOrOperator(Character t, int p, BiFunction<Double,Double,Double> c) { super(t,p,c,2); value=null; }
    public TermOrOperator(Character t, int p, BiFunction<Double,Double,Double> c, int n) { super(t,p,c,n); value=null; }
    public String getValue() { return value; }
    public String toString() { return value!=null ? value : super.toString(); }
}
class Tokens {
    private Map<Character,TermOrOperator> map = new HashMap<>();
    public void put(Character t) { map.put(t, new TermOrOperator(t)); }
    public void put(Character t, int p, BiFunction<Double,Double,Double> c) { map.put(t, new TermOrOperator(t,p,c)); }
    public void put(Character t, int p, BiFunction<Double,Double,Double> c, int n) { map.put(t, new TermOrOperator(t,p,c,n)); }
    public TermOrOperator get(Character t) { return map.get(t); }
    public boolean contains(Character t) { return map.containsKey(t); }
}

// --- Tokenizer ---
Tokens operators = new Tokens();
operators.put('+', 4, (a,b) -> a+b);
operators.put('-', 4, (a,b) -> a-b);
operators.put('*', 3, (a,b) -> a*b);
operators.put('/', 3, (a,b) -> a/b);
operators.put('%', 3, (a,b) -> a%b);
operators.put('^', 2, (a,b) -> Math.pow(a,b));

Tokens separators = new Tokens();
separators.put(' ');
separators.put('(');
separators.put(')');

ArrayList<TermOrOperator> tokenize(String expr, Tokens ops, Tokens seps) {
    ArrayList<TermOrOperator> terms = new ArrayList<>();
    int start = 0;
    StringBuilder multi = new StringBuilder();
    for (int i = 0; i < expr.length(); i++) {
        char c = expr.charAt(i);
        if (ops.contains(c) || seps.contains(c)) {
            if (multi.length() > 0) {
                terms.add(new TermOrOperator(expr.substring(start, i)));
            }
            TermOrOperator t = ops.get(c);
            if (t == null) t = seps.get(c);
            if (t != null && t.getToken() != ' ') terms.add(t);
            start = i + 1;
            multi = new StringBuilder();
        } else {
            multi.append(c);
        }
    }
    if (multi.length() > 0) terms.add(new TermOrOperator(expr.substring(start)));
    return terms;
}

// --- TEST ---
String[] expressions = {
    "100 + 200 * 3",
    "(100 + 200) * 3",
    "3.14 * 2",
    "2 ^ 10",
    "100 % 7"
};
for (String expr : expressions) {
    System.out.println("\"" + expr + "\"  →  " + tokenize(expr, operators, separators));
}

// TODO: Try tokenizing your own expression!

    Code Runner Challenge

    The tokenizer splits a math expression string into individual tokens. Run it to see how different expressions get tokenized. Try adding your own expression at the bottom.

    Lines: 1 Characters: 0
    Output
    Click "Run" in code control panel to see output ...

    Trace It: How Does Tokenization Work?

    "(100 + 200) * 3"

    Walk through each character. What happens at each step?

    Character-by-Character Trace:

    Step 1: char = '('
    Separator found — multi is empty, skip number flush — Add ( token — Result: [(]
    Step 2-4: chars = '1', '0', '0'
    Not an operator or separator — Accumulate into multi = "100" — No token added yet
    Step 5: char = ' '
    Separator found — Flush multi — Add number token "100" — Space is not added (filtered out) — Result: [(, 100]
    Step 6: char = '+'
    Operator found — multi is empty — Add + operator token — Result: [(, 100, +]
    Steps 7-10: ' ', '2', '0', '0'
    Space flushes nothing (multi empty), then accumulate "200"
    Step 11: char = ')'
    Separator found — Flush "200" — Add ) token — Result: [(, 100, +, 200, )]
    Steps 12-15: ' ', '*', ' ', '3'
    Space, then * operator added, then space, then "3" accumulated and flushed at end-of-string
    Final Result
    [(, 100, +, 200, ), *, 3] — 7 tokens from a 15-character string. Notice how spaces are used as delimiters but never become tokens themselves.

    Step 5: Converting to Reverse Polish Notation (The Stack Algorithm)

    This is the core algorithm. RPN reorders tokens so that operators come AFTER their operands, eliminating the need for parentheses.

    Infix (normal): (100 + 200) * 3
    RPN (postfix): 100 200 + 3 *

    The Shunting-Yard Algorithm (by Dijkstra)

    Uses a Stack to reorder operators:

    1. Number → goes straight to output
    2. ( → push onto operator stack
    3. ) → pop operators to output until ( is found
    4. Operator → pop higher-precedence operators from stack to output, then push current
    5. End → pop remaining operators to output

    Challenge: Trace the algorithm by hand for (100 + 200) * 3, then run to verify.

    import java.util.*;
import java.util.function.BiFunction;

class Token {
    private final Character token; private final int precedence;
    private final BiFunction<Double,Double,Double> calc; private final int numArgs;
    public Token() { this('0'); }
    public Token(Character t) { this(t,0,null,0); }
    public Token(Character t,int p,BiFunction<Double,Double,Double> c,int n) { token=t;precedence=p;calc=c;numArgs=n; }
    public Character getToken() { return token; }
    public int getPrecedence() { return precedence; }
    public int getNumArgs() { return numArgs; }
    public boolean isPrecedent(Token t) { return precedence>t.getPrecedence(); }
    public Double calculate(Double a,Double b) { return calc.apply(a,b); }
    public String toString() { return token.toString(); }
}
class TermOrOperator extends Token {
    private final String value;
    public TermOrOperator(String v) { value=v; }
    public TermOrOperator(Character t) { super(t); value=null; }
    public TermOrOperator(Character t,int p,BiFunction<Double,Double,Double> c) { super(t,p,c,2); value=null; }
    public TermOrOperator(Character t,int p,BiFunction<Double,Double,Double> c,int n) { super(t,p,c,n); value=null; }
    public String getValue() { return value; }
    public String toString() { return value!=null?value:super.toString(); }
}
class Tokens {
    Map<Character,TermOrOperator> map=new HashMap<>();
    void put(Character t) { map.put(t,new TermOrOperator(t)); }
    void put(Character t,int p,BiFunction<Double,Double,Double> c) { map.put(t,new TermOrOperator(t,p,c)); }
    TermOrOperator get(Character t) { return map.get(t); }
    boolean contains(Character t) { return map.containsKey(t); }
}

Tokens ops = new Tokens();
ops.put('+',4,(a,b)->a+b); ops.put('-',4,(a,b)->a-b);
ops.put('*',3,(a,b)->a*b); ops.put('/',3,(a,b)->a/b);
ops.put('^',2,(a,b)->Math.pow(a,b));
Tokens seps = new Tokens();
seps.put(' '); seps.put('('); seps.put(')');

ArrayList<TermOrOperator> tokenize(String expr) {
    ArrayList<TermOrOperator> terms = new ArrayList<>();
    int start=0; StringBuilder multi=new StringBuilder();
    for (int i=0;i<expr.length();i++) {
        char c=expr.charAt(i);
        if (ops.contains(c)||seps.contains(c)) {
            if (multi.length()>0) terms.add(new TermOrOperator(expr.substring(start,i)));
            TermOrOperator t=ops.get(c); if(t==null) t=seps.get(c);
            if (t!=null && t.getToken()!=' ') terms.add(t);
            start=i+1; multi=new StringBuilder();
        } else multi.append(c);
    }
    if (multi.length()>0) terms.add(new TermOrOperator(expr.substring(start)));
    return terms;
}

// --- Shunting-Yard: Infix → RPN ---
ArrayList<TermOrOperator> toRPN(ArrayList<TermOrOperator> terms) {
    ArrayList<TermOrOperator> rpn = new ArrayList<>();
    Stack<TermOrOperator> opStack = new Stack<>();
    for (TermOrOperator term : terms) {
        if (term.getToken() == '(') {
            opStack.push(term);
        } else if (term.getToken() == ')') {
            while (opStack.peek().getToken() != '(') rpn.add(opStack.pop());
            opStack.pop(); // remove '('
        } else if (ops.contains(term.getToken())) {
            while (!opStack.isEmpty() && ops.contains(opStack.peek().getToken()) && term.isPrecedent(opStack.peek()))
                rpn.add(opStack.pop());
            opStack.push(term);
        } else {
            rpn.add(term);
        }
    }
    while (!opStack.isEmpty()) rpn.add(opStack.pop());
    return rpn;
}

// --- TEST ---
String[] expressions = {
    "100 + 200 * 3",
    "(100 + 200) * 3",
    "3 + 4 * 2 - 1",
    "2 ^ 10"
};
for (String expr : expressions) {
    ArrayList<TermOrOperator> tokens = tokenize(expr);
    ArrayList<TermOrOperator> rpn = toRPN(tokens);
    System.out.println("Infix:  " + expr);
    System.out.println("Tokens: " + tokens);
    System.out.println("RPN:    " + rpn);
    System.out.println();
}

    Code Runner Challenge

    The Shunting-Yard algorithm converts infix to RPN using a Stack. Run to see step-by-step conversion. Try tracing "5 + 3 * 2" by hand first, then verify with the code.

    Lines: 1 Characters: 0
    Output
    Click "Run" in code control panel to see output ...

    RPN Ordering Challenge

    Drag the tokens into correct Reverse Polish Notation order for: (5 + 3) * 2

    Available Tokens

    Your RPN Order

    Step 6: Evaluating RPN — The Final Calculation

    Once we have RPN, evaluation is beautifully simple using a Stack:

    1. Read tokens left to right
    2. Number → push onto stack
    3. Operator → pop operand(s), calculate, push result back
    4. Done → one number remains on stack = final answer

    Example: 100 200 + 3 *

    Step Token Stack Action
    1 100 [100] Push
    2 200 [100, 200] Push
    3 + [300] Pop 200 & 100, add, push 300
    4 3 [300, 3] Push
    5 * [900] Pop 3 & 300, multiply, push 900

    Result: 900

    Interactive Stack Visualization

    Step through RPN evaluation of 100 200 + 3 * and watch the stack in action.

    Token Stream
    Stack
    Click Next Step to begin evaluation.

    Step 7: The Complete Calculator

    Now let’s put it all together. The full Calculator class chains the entire pipeline:

    Expression → Tokenize → RPN → Evaluate → Result

    Challenge: Run the complete calculator, then try your own expressions!

    Supported operators: +, -, *, /, %, ^ (power), √ (square root)

    import java.util.*;
import java.util.function.BiFunction;

class Token {
    private final Character token; private final int precedence;
    private final BiFunction<Double,Double,Double> calc; private final int numArgs;
    public Token() { this('0'); }
    public Token(Character t) { this(t,0,null,0); }
    public Token(Character t,int p,BiFunction<Double,Double,Double> c,int n) {
        token=t; precedence=p; calc=c; numArgs=n;
    }
    public Character getToken() { return token; }
    public int getPrecedence() { return precedence; }
    public int getNumArgs() { return numArgs; }
    public boolean isPrecedent(Token t) { return precedence > t.getPrecedence(); }
    public Double calculate(Double a, Double b) { return calc.apply(a,b); }
    public String toString() { return token.toString(); }
}

class TermOrOperator extends Token {
    private final String value;
    public TermOrOperator(String v) { value=v; }
    public TermOrOperator(Character t) { super(t); value=null; }
    public TermOrOperator(Character t,int p,BiFunction<Double,Double,Double> c) { super(t,p,c,2); value=null; }
    public TermOrOperator(Character t,int p,BiFunction<Double,Double,Double> c,int n) { super(t,p,c,n); value=null; }
    public String getValue() { return value; }
    public String toString() { return value!=null ? value : super.toString(); }
}

class Tokens {
    private Map<Character,TermOrOperator> map = new HashMap<>();
    public void put(Character t) { map.put(t, new TermOrOperator(t)); }
    public void put(Character t,int p,BiFunction<Double,Double,Double> c) { map.put(t, new TermOrOperator(t,p,c)); }
    public void put(Character t,int p,BiFunction<Double,Double,Double> c,int n) { map.put(t, new TermOrOperator(t,p,c,n)); }
    public TermOrOperator get(Character t) { return map.get(t); }
    public int getPrecedence(Character t) { return map.get(t).getPrecedence(); }
    public boolean contains(Character t) { return map.containsKey(t); }
}

public class Calculator {
    private final String expression;
    private ArrayList<TermOrOperator> terms = new ArrayList<>();
    private ArrayList<TermOrOperator> rpnTerms = new ArrayList<>();
    private Tokens operators = new Tokens();
    private Tokens separators = new Tokens();
    private Double result = 0.0;

    public Calculator(String expression) {
        initOperators();
        initSeparators();
        this.expression = expression;
        this.termTokenizer();
        this.termsToRPN();
        this.rpnToResult();
    }

    private void initOperators() {
        operators.put('*', 3, (a,b) -> a*b);
        operators.put('/', 3, (a,b) -> a/b);
        operators.put('%', 3, (a,b) -> a%b);
        operators.put('+', 4, (a,b) -> a+b);
        operators.put('-', 4, (a,b) -> a-b);
        operators.put('^', 2, (a,b) -> Math.pow(a,b));
    }

    private void initSeparators() {
        separators.put(' ');
        separators.put('(');
        separators.put(')');
    }

    private void termTokenizer() {
        int start = 0;
        StringBuilder multi = new StringBuilder();
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (operators.contains(c) || separators.contains(c)) {
                if (multi.length() > 0)
                    terms.add(new TermOrOperator(expression.substring(start, i)));
                TermOrOperator t = operators.get(c);
                if (t == null) t = separators.get(c);
                if (t != null && t.getToken() != ' ') terms.add(t);
                start = i + 1;
                multi = new StringBuilder();
            } else {
                multi.append(c);
            }
        }
        if (multi.length() > 0) terms.add(new TermOrOperator(expression.substring(start)));
    }

    private void termsToRPN() {
        Stack<TermOrOperator> opStack = new Stack<>();
        for (TermOrOperator term : terms) {
            if (term.getToken() == '(') {
                opStack.push(term);
            } else if (term.getToken() == ')') {
                while (opStack.peek().getToken() != '(') rpnTerms.add(opStack.pop());
                opStack.pop();
            } else if (operators.contains(term.getToken())) {
                while (!opStack.isEmpty() && operators.contains(opStack.peek().getToken())
                       && term.isPrecedent(opStack.peek()))
                    rpnTerms.add(opStack.pop());
                opStack.push(term);
            } else {
                rpnTerms.add(term);
            }
        }
        while (!opStack.isEmpty()) rpnTerms.add(opStack.pop());
    }

    private void rpnToResult() {
        Stack<Double> calcStack = new Stack<>();
        for (TermOrOperator term : rpnTerms) {
            if (operators.contains(term.getToken())) {
                Double op2 = calcStack.pop();
                Double op1 = calcStack.pop();
                calcStack.push(term.calculate(op1, op2));
            } else {
                calcStack.push(Double.valueOf(term.getValue()));
            }
        }
        this.result = calcStack.pop();
    }

    public String toString() {
        return "Original expression: " + expression + "\n"
             + "Tokenized expression: " + terms + "\n"
             + "Reverse Polish Notation: " + rpnTerms + "\n"
             + "Final result: " + String.format("%.2f", result);
    }

    public static void main(String[] args) {
        System.out.println("=== Simple Math ===");
        System.out.println(new Calculator("100 + 200 * 3"));
        System.out.println();

        System.out.println("=== Parentheses Override Precedence ===");
        System.out.println(new Calculator("(100 + 200) * 3"));
        System.out.println();

        System.out.println("=== Decimals ===");
        System.out.println(new Calculator("100.2 - 99.3"));
        System.out.println();

        System.out.println("=== Modulo ===");
        System.out.println(new Calculator("300 % 200"));
        System.out.println();

        System.out.println("=== Power ===");
        System.out.println(new Calculator("2 ^ 10"));
        System.out.println();

        // TODO: Add your own expression here!
        // System.out.println(new Calculator("YOUR EXPRESSION"));
    }
}
Calculator.main(null);

    Code Runner Challenge

    The complete RPN Calculator! Run it to see the full pipeline — from expression to tokenization to RPN to result. Try adding your own expressions at the bottom of main().

    Lines: 1 Characters: 0
    Output
    Click "Run" in code control panel to see output ...

    Knowledge Check

    Test your understanding of the full RPN Calculator pipeline!

    Final Knowledge Check

    5 questions covering the entire lesson

    Question 1 of 5
    What data structure does the Shunting-Yard algorithm use to temporarily hold operators during the infix-to-RPN conversion?
    Question 2 of 5
    What is the RPN (postfix) form of 3 + 4 * 2?
    Question 3 of 5
    In the Token class, BiFunction<Double, Double, Double> is used for the calculation field. What type of Java feature is BiFunction?
    Question 4 of 5
    During RPN evaluation of 5 3 + 2 *, what is on the stack after processing the + token?
    Question 5 of 5
    When the tokenizer encounters a ) character, what does it do?

    Key Takeaways

    Data Structures Used

    Data Structure Where Purpose
    ArrayList terms, rpnTerms Ordered storage of tokens
    Stack Shunting-yard & evaluation LIFO for operator reordering and calculation
    HashMap Tokens class O(1) lookup of operators by character

    AP CSA Concepts Demonstrated

    • Inheritance — TermOrOperator extends Token
    • Polymorphism — numbers and operators stored in the same ArrayList<TermOrOperator>
    • Encapsulation — private fields with getters
    • Functional Interfaces — BiFunction<Double, Double, Double> for operator calculations
    • Algorithmic Thinking — Dijkstra’s Shunting-Yard algorithm

    Hack Ideas

    1. Add support for unary minus (negative numbers like -5 + 3)
    2. Add trigonometric functions (sin, cos, tan)
    3. Add error handling for malformed expressions (mismatched parentheses, division by zero)
    4. Build a visual step-by-step debugger that shows the stack state at each step
    5. Create a GUI calculator that uses this engine under the hood

    Course Timeline