RPN Calculator Lesson

5 min read

Building a Reverse Polish Notation (RPN) Calculator in Java
- Advantages of RPN:
- By the end of this lesson, you will:
1. How Reverse Polish Notation Works
Creating the Calculator Structure
- This now correctly reflects the actual methods in the code:
- Code Runner Challenge

Building a Reverse Polish Notation (RPN) Calculator in Java

In this lesson, we will build a Reverse Polish Notation (RPN) calculator using Java.

RPN is a mathematical notation where operators come after operands.

Example:

Standard notation: 3 + 4
RPN notation: 34+

Advantages of RPN:

No need for parentheses
Simple evaluation using a stack
Used in some calculators and programming languages

By the end of this lesson, you will:

Understand how RPN works
Learn how stacks help evaluate expressions
Build a working RPN calculator in Java

1. How Reverse Polish Notation Works

In RPN, numbers are pushed onto a stack, and operators pop numbers from the stack, perform a calculation, and push the result back.

Example Expression: 5 2 + 3 *

Step-by-step:

Step	Stack
push 5	[5]
push 2	[5,2]
+	pop 5 and 2 → push 7 → [7]
push 3	[7,3]
*	pop 7 and 3 → push 21

Final result: 21

Creating the Calculator Structure

We will create a Calculator class that evaluates mathematical expressions using Reverse Polish Notation (RPN).

The program works in three major steps:

Tokenize the expression
The input string is broken into individual terms and operators (numbers, +, -, *, /, parentheses, etc.).
Convert the expression to Reverse Polish Notation (RPN)
Using a stack, the program rearranges the tokens so that operator precedence and parentheses are handled correctly.
Evaluate the RPN expression
Another stack is used to compute the result by:
- pushing numbers onto the stack
- applying operators to the top values
- pushing the result back onto the stack

By the end of this process, the stack contains a single value — the final result of the expression.

This now correctly reflects the actual methods in the code:

termTokenizer() → tokenize expression

termsToRPN() → convert to RPN using stack

rpnToResult() → evaluate RPN with stack

Code Runner Challenge

RPN Calculator Demo

View IPYNB Source

// CODE_RUNNER: RPN Calculator Demo

import java.util.*;

/*
 Reverse Polish Notation Calculator Demo
 All required classes are included in a single source so it runs in CodeRunner.
*/

interface BinaryOp {
    double apply(double a, double b);
}

class TermOrOperator {

    private Character token;
    private String value;
    private int precedence;
    private int numArgs;
    private BinaryOp operation;

    public TermOrOperator(String value) {
        this.value = value;
    }

    public TermOrOperator(Character token, int precedence,
                          BinaryOp operation,
                          int numArgs) {
        this.token = token;
        this.precedence = precedence;
        this.operation = operation;
        this.numArgs = numArgs;
    }

    public TermOrOperator(Character token) {
        this.token = token;
    }

    public Character getToken() {
        return token;
    }

    public String getValue() {
        return value;
    }

    public int getNumArgs() {
        return numArgs;
    }

    public boolean isPrecedent(TermOrOperator other) {
        return this.precedence >= other.precedence;
    }

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

    public String toString() {
        if (value != null) return value;
        return token.toString();
    }
}

class Tokens {

    private HashMap<Character, TermOrOperator> map = new HashMap<>();

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

    public void put(Character token, int precedence, BinaryOp op) {
        map.put(token, new TermOrOperator(token, precedence, op, 2));
    }

    public void put(Character token, int precedence, BinaryOp op, int args) {
        map.put(token, new TermOrOperator(token, precedence, op, args));
    }

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

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

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 seperators = new Tokens();
    private Double result = 0.0;

    public Calculator(String expression) {

        initOperators();
        initSeperators();

        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 initSeperators() {

        seperators.put(' ');
        seperators.put('(');
        seperators.put(')');
    }

    private void termTokenizer() {

        int start = 0;
        StringBuilder multiCharTerm = new StringBuilder();

        for (int i = 0; i < expression.length(); i++) {

            Character c = expression.charAt(i);

            if (operators.contains(c) || seperators.contains(c)) {

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

                TermOrOperator t = operators.get(c);
                if (t == null) t = seperators.get(c);

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

                start = i + 1;
                multiCharTerm = new StringBuilder();

            } else {
                multiCharTerm.append(c);
            }
        }

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

    private void termsToRPN() {

        Stack<TermOrOperator> operatorStack = new Stack<>();

        for (TermOrOperator term : terms) {

            if (term.getToken() != null && term.getToken() == '(') {

                operatorStack.push(term);

            } else if (term.getToken() != null && term.getToken() == ')') {

                while (operatorStack.peek().getToken() != '(') {
                    rpnTerms.add(operatorStack.pop());
                }
                operatorStack.pop();

            } else if (term.getToken() != null && 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 : rpnTerms) {

            if (term.getToken() != null && operators.contains(term.getToken())) {

                Double a = 0.0, b = 0.0;

                if (term.getNumArgs() == 1) {

                    a = calcStack.pop();

                } else {

                    b = calcStack.pop();
                    a = calcStack.pop();
                }

                calcStack.push(term.calculate(a, b));

            } else {

                calcStack.push(Double.valueOf(term.getValue()));
            }
        }

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

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

        System.out.println();

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

        System.out.println();

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

        System.out.println();

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

        System.out.println();

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

        System.out.println();

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

Calculator.main(null);

Lines: 1 Characters: 0

Output

Click "Run" in code control panel to see output ...

Computer Science A