Computer Science A

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

Understanding Reverse Polish Notation (RPN)

13 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)

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