Computer Science A

Course Progress 0/0
Week 25 Understanding Reverse Polish Notation (RPN)

Understanding Reverse Polish Notation (RPN)

14 min read • Assignment

What is Reverse Polish Notation?

Reverse Polish Notation (RPN) is a way of writing mathematical expressions where operators come after their operands instead of before or between them.

Standard Notation vs RPN

Normal (pemdas) RPN Result
3 + 4 3 4 + 7
(5 + 2) * 3 5 2 + 3 * 21
10 - 2 * 3 10 2 3 * - 4

Why is RPN useful?

  • No need for parentheses to show order of operations

  • Used in calculators, compilers, and many programming languages.

  • Breaks the expression into tokens (numbers and operators) to make it simpler

Stacks and Queues

Stack (LIFO - Last In, First Out)

A stack works like a stack of plates - the last plate added is the first one taken out.

Plates

Stack Operations:

push(item) - Add item to the top of the stack (like placing a plate on the stack)

pop() - Remove and return the top item (like taking the top plate off the stack)

peek() - Look at the top item without removing it (like looking at the top plate without lifting it)

Queue (FIFO - First In, First Out)

A queue works like a line at the store - the first person in line is the first one served.

Line

Queue Operations:

enqueue(item) - Add item to the back (like joining the back of a line)

dequeue() - Remove and return the front item (like the first person in line being served)

peek() - Look at the front item without removing it (like checking who’s next in line)

Now time for a game!

Stack Clicker is a mini game that helps you practice stack thinking by making quick decisions and watching how actions are processed in order. As you play, connect what you see to LIFO behavior and the step-by-step logic used in RPN evaluation.

Main Learning Targets

  • Understand how a stack uses Last In, First Out (LIFO) order.
  • Learn stack operations (like push, pop, and peek) through game functions like adding to stack
  • Understand how to optimize stacks by gaining new upgrades to earn more knowledge points

How to Play

  1. Click start in the game embedded below.
  2. Click the box to add items to your stack
  3. Gain knowledge points by clicking (watch out for stack overflow!)
  4. Buy upgrades with your knowledge points to optimize your stack
Game Status: Not Started
Points: --
Stack Depth: --
Max Depth: --
Overflows: --

Use these buttons to toggle the in-game leaderboard and chatbot.

Building the Calculator

Now let’s build a calculator that converts regular math expressions to RPN and solves them.

We’ll use 3 key classes:

  1. Token
    • Stores an operator symbol (like +, -, *)
    • Stores operator priority/order
  2. TermOrOperator
    • Represents one piece of the expression
    • Can be either a number or an operator
  3. Tokens
    • A lookup collection of operators/their functions
    • Uses a Map so the calculator can quickly find operator rules
    • Keeps operator setup organized and easy to read

Then the Calculator class uses these 3 classes to tokenize, convert to RPN, and evaluate the final result!

Step 1: Token Class

What we’re doing: Creating a Token class to represent operator symbols and their math behavior.

Objective: Define precedence and calculation rules so later classes can convert and evaluate expressions correctly.

Code Runner Challenge

Token

View IPYNB Source 
// CODE_RUNNER: Token
import java.util.function.BiFunction;

// Token = one operator rule in our RPN lesson
class Token {
    private final Character token;  // operator symbol (+, -, *, /, etc.)
    private final int precedence;   // smaller number å= higher priority
    private final BiFunction<Double, Double, Double> calculation;
    private final int numArgs;      // 2 for normal operators, 1 for unary like sqrt

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

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

    // Full operator token (provided for reference)
    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 this.token;
    }

    public int getPrecedence() {
        return this.precedence;
    }

    public int getNumArgs() {
        return this.numArgs;
    }

    public boolean isPrecedent(Token other) {
        return this.precedence > other.getPrecedence();
    }

    public Double calculate(Double a, Double b) {
        return this.calculation.apply(a, b);
    }

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

public class Main {
    public static void main(String[] args) {
        Token plus = new Token('+', 4, (a, b) -> a + b, 2);
        Token multiply = new Token('*', 3, (a, b) -> a * b, 2);

        System.out.println("Token example: " + plus);
        System.out.println("Precedence of +: " + plus.getPrecedence());
        System.out.println("Arguments for +: " + plus.getNumArgs());
        System.out.println("Does + come after * in stack precedence? " + plus.isPrecedent(multiply));

        // Student check-in: change these tokens and explain why precedence output changes.
    }
}

main.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Step 2: TermOrOperator Class

What we’re doing: Building a class that can store either a number (term) or an operator.

Objective: Let the calculator treat every piece of an expression in a consistent way during tokenizing and RPN conversion.

Code Runner Challenge

TermOrOperator

View IPYNB Source 
// CODE_RUNNER: TermOrOperator
import java.util.function.BiFunction;

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 this.token;
    }

    public int getPrecedence() {
        return this.precedence;
    }

    public int getNumArgs() {
        return this.numArgs;
    }

    public boolean isPrecedent(Token other) {
        return this.precedence > other.getPrecedence();
    }

    public Double calculate(Double a, Double b) {
        return this.calculation.apply(a, b);
    }

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

// A term in math can be a value (like 42) or an operator (like +)
class TermOrOperator extends Token {
    private final String value;

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

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

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

    // Constructor for operators with custom arg count
    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 this.value;
    }

    public String toString() {
        if (this.value == null) {
            return super.toString();
        }
        return this.value;
    }
}

public class Main {
    public static void main(String[] args) {
        TermOrOperator numberTerm = new TermOrOperator("42");
        TermOrOperator plusOperator = new TermOrOperator('+', 4, (a, b) -> a + b);

        System.out.println("Number term: " + numberTerm);
        System.out.println("Operator term: " + plusOperator);

        // Student check-in: create a square-root token using numArgs = 1.
    }
}

main.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Step 3: Tokens Lookup Class

What we’re doing: Creating a Tokens map that stores operators and separators for quick lookup.

Objective: Keep operator setup organized so the final Calculator can efficiently find rules during parsing and evaluation.

Code Runner Challenge

Tokens

View IPYNB Source 
// CODE_RUNNER: Tokens
import java.util.HashMap;
import java.util.Map;
import java.util.function.BiFunction;

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 this.token;
    }

    public int getPrecedence() {
        return this.precedence;
    }

    public int getNumArgs() {
        return this.numArgs;
    }

    public boolean isPrecedent(Token other) {
        return this.precedence > other.getPrecedence();
    }

    public Double calculate(Double a, Double b) {
        return this.calculation.apply(a, b);
    }

    public String toString() {
        return this.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 precedence, BiFunction<Double, Double, Double> calculation) {
        super(token, precedence, calculation, 2);
        this.value = null;
    }

    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 this.value;
    }

    public String toString() {
        if (this.value == null) {
            return super.toString();
        }
        return this.value;
    }
}

// Tokens = quick lookup table for operators and separators
class Tokens {
    private final Map<Character, TermOrOperator> map;

    public Tokens() {
        this.map = new HashMap<>();
    }

    public void put(Character token) {
        this.map.put(token, new TermOrOperator(token));
    }

    public void put(Character token, int precedence, BiFunction<Double, Double, Double> calculation, int numArgs) {
        this.map.put(token, new TermOrOperator(token, precedence, calculation, numArgs));
    }

    public void put(Character token, int precedence, BiFunction<Double, Double, Double> calculation) {
        this.map.put(token, new TermOrOperator(token, precedence, calculation));
    }

    public TermOrOperator get(Character token) {
        return this.map.get(token);
    }

    public boolean contains(Character token) {
        return this.map.containsKey(token);
    }

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

public class Main {
    public static void main(String[] args) {
        Tokens operators = new Tokens();
        operators.put('+', 4, (a, b) -> a + b);
        operators.put('√', 1, (a, b) -> Math.sqrt(a), 1);

        System.out.println("Contains +: " + operators.contains('+'));
        System.out.println("Contains √: " + operators.contains('√'));
        System.out.println("Stored tokens: " + operators);

        // Student check-in: add '-' and test contains('-').
    }
}

main.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Final step: Create the Calculator

What we’re doing: Combining all the things from the last 3 steps Token, TermOrOperator, and Tokens into one calculator workflow.

Objective: Tokenize expressions, convert to RPN with the Shunting Yard Algorithm, evaluate with a stack, and return intermediate steps plus the final result.

Code Runner Challenge

Calculator

View IPYNB Source 
// CODE_RUNNER: Calculator
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
import java.util.function.BiFunction;

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 this.token;
    }

    public int getPrecedence() {
        return this.precedence;
    }

    public int getNumArgs() {
        return this.numArgs;
    }

    public boolean isPrecedent(Token other) {
        return this.precedence > other.getPrecedence();
    }

    public Double calculate(Double a, Double b) {
        return this.calculation.apply(a, b);
    }

    public String toString() {
        return this.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 precedence, BiFunction<Double, Double, Double> calculation) {
        super(token, precedence, calculation, 2);
        this.value = null;
    }

    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 this.value;
    }

    public String toString() {
        if (this.value == null) {
            return super.toString();
        }
        return this.value;
    }
}

class Tokens {
    private final Map<Character, TermOrOperator> map;

    public Tokens() {
        this.map = new HashMap<>();
    }

    public void put(Character token) {
        this.map.put(token, new TermOrOperator(token));
    }

    public void put(Character token, int precedence, BiFunction<Double, Double, Double> calculation, int numArgs) {
        this.map.put(token, new TermOrOperator(token, precedence, calculation, numArgs));
    }

    public void put(Character token, int precedence, BiFunction<Double, Double, Double> calculation) {
        this.map.put(token, new TermOrOperator(token, precedence, calculation));
    }

    public TermOrOperator get(Character token) {
        return this.map.get(token);
    }

    public boolean contains(Character token) {
        return this.map.containsKey(token);
    }

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

// Put it all together:
// part 1 - tokenize infix expression
// part 2 - convert to RPN (postfix)
// part 3 - evaluate RPN using a stack
class Calculator {
    private final String expression;
    private final ArrayList<TermOrOperator> terms = new ArrayList<>();
    private final ArrayList<TermOrOperator> rpnTerms = new ArrayList<>();
    private final Tokens operators = new Tokens();
    private final Tokens separators = new Tokens();
    private Double result = 0.0;

    public Calculator(String expression) {
        initOperators();
        initSeparators();
        this.expression = expression;
        termTokenizer();
        termsToRPN();
        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));
        operators.put('√', 1, (a, b) -> Math.sqrt(a), 1);
    }

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

    private void termTokenizer() {
        int start = 0;
        StringBuilder multiCharTerm = new StringBuilder();

        for (int i = 0; i < this.expression.length(); i++) {
            Character c = this.expression.charAt(i);

            if (operators.contains(c) || separators.contains(c)) {
                if (multiCharTerm.length() > 0) {
                    this.terms.add(new TermOrOperator(this.expression.substring(start, i)));
                }

                TermOrOperator t = operators.get(c);
                if (t == null) {
                    t = separators.get(c);
                }

                if (t != null && t.getToken() != ' ') {
                    this.terms.add(t);
                }

                start = i + 1;
                multiCharTerm = new StringBuilder();
            } else {
                multiCharTerm.append(c);
            }
        }

        if (multiCharTerm.length() > 0) {
            this.terms.add(new TermOrOperator(this.expression.substring(start)));
        }
    }

    private void termsToRPN() {
        Stack<TermOrOperator> operatorStack = new Stack<>();

        for (TermOrOperator term : this.terms) {
            if (term.getToken() == '(') {
                operatorStack.push(term);
            } else if (term.getToken() == ')') {
                while (!operatorStack.isEmpty() && operatorStack.peek().getToken() != '(') {
                    rpnTerms.add(operatorStack.pop());
                }
                if (!operatorStack.isEmpty()) {
                    operatorStack.pop();
                }
            } else if (operators.contains(term.getToken())) {
                while (!operatorStack.isEmpty()
                        && operators.contains(operatorStack.peek().getToken())
                        && term.isPrecedent(operatorStack.peek())) {
                    rpnTerms.add(operatorStack.pop());
                }
                operatorStack.push(term);
            } else {
                rpnTerms.add(term);
            }
        }

        while (!operatorStack.isEmpty()) {
            rpnTerms.add(operatorStack.pop());
        }
    }

    private void rpnToResult() {
        Stack<Double> calcStack = new Stack<>();

        for (TermOrOperator term : this.rpnTerms) {
            if (term.getToken() != null && operators.contains(term.getToken())) {
                Double operand1 = 0.0;
                Double operand2 = 0.0;

                if (term.getNumArgs() == 1) {
                    operand1 = calcStack.pop();
                } else {
                    operand2 = calcStack.pop();
                    operand1 = calcStack.pop();
                }

                calcStack.push(term.calculate(operand1, operand2));
            } else {
                calcStack.push(Double.valueOf(term.getValue()));
            }
        }

        this.result = calcStack.pop();
    }

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

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

        Calculator parenthesisMath = new Calculator("(100 + 200) * 3");
        System.out.println("Parenthesis Math\n" + parenthesisMath + "\n");

        Calculator decimalMath = new Calculator("100.2 - 99.3");
        System.out.println("Decimal Math\n" + decimalMath + "\n");

        Calculator moduloMath = new Calculator("300 % 200");
        System.out.println("Modulo Math\n" + moduloMath + "\n");

        Calculator divisionMath = new Calculator("300 / 200");
        System.out.println("Division Math\n" + divisionMath + "\n");

        Calculator pythagoreanMath = new Calculator("√(3^2 + 4^2)");
        System.out.println("Pythagorean Theorem\n" + pythagoreanMath + "\n");

        // Student extension prompt:
        // Add one more test expression using nested parentheses.
    }
}

main.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Debrief: How RPN Evaluation Works (Step by Step)

Let’s trace through a simple example: 5 2 + 3 * (which equals 21)

Expression: 5 2 + 3

Step 1: Read 5 → Push to stack

Stack: [5]

Step 2: Read 2 → Push to stack

Stack: [5, 2]

Step 3: Read + → Pop two operands, calculate, push result Pop 2 and 5 → 5 + 2 = 7

Stack: [7]

Step 4: Read 3 → Push to stack

Stack: [7, 3]

Step 5: Read * → Pop two operands, calculate, push result Pop 3 and 7 → 7 * 3 = 21

Stack: [21]

Final Result: 21

Submit Assignment

Click to upload or drag and drop
PDF, ZIP, images, or documents (Max 10MB per file)

Course Timeline