Computer Science A

Course Progress 0/0
Week 25 Calculator Enactment 1

Calculator Enactment 1

10 min read

%%html <!DOCTYPE html>

Reverse Polish Notation (RPN) & Postfix Evaluation

Understanding Stacks and Queues

  • Stack (LIFO - Last In, First Out): Think of stacking cards. The last one placed is the first one removed.
  • Queue (FIFO - First In, First Out): Think of a line at a store. The first one in is the first one out.

What is Reverse Polish Notation (RPN)?

  • Infix Notation: Standard mathematical notation where operators are between operands. (e.g., 3 + 5 * 8)
  • Postfix Notation (RPN): Operators come after the operands. (e.g., 35+8* instead of (3+5)*8)

Example Conversions:

  1. 3 * 5 → 35*
  2. (3 + 5) * 8 → 35+8*

Postfix Expression Evaluation

Example: Solve 8 9 + 10 3 * 8 *

Step-by-Step Calculation:

  1. 8 9 + → 17
  2. 10 3 * → 30
  3. 30 8 * → 240
  4. Final result: 17 240 (Not combined yet, needs more context)

Try this: Solve 8 2 ^ 8 8 * +

Step-by-Step Calculation:

  1. 8 2 ^ → 64 (Exponentiation: 8^2 = 64)
  2. 8 8 * → 64
  3. 64 64 + → 128 (Final result)

Why Use Postfix Notation?

  • Follows PEMDAS naturally (Parentheses, Exponents, Multiplication/Division, Addition/Subtraction).
  • Operators go into a stack, while numerals go into a queue.
  • Easier to evaluate expressions using stacks, reducing complexity in parsing.

Popcorn Hack - Convert to Infix!

Convert the following postfix expressions into infix notation:

  1. 6 3 * 4 +
  2. 10 2 8 * + 3 -
  3. 15 3 / 4 2 * +
  4. 7 3 2 * + 5 -
  5. 9 3 + 2 ^

Answers Here for Popcorn Hack

Infix to RPN

  • For every “token” in infix 824-E9-D4-F-D60-A-4941-B42-F-32-C730-BD9-DA5.png 85-DC050-E-F993-400-D-8608-179-A68144-DC4.png
    • If token is number: push into queue
    • Else if token is operator
      • While the stack isn’t empty, and the operator at the top of the stack has greater or equal “precedence” to the current token, pop values from stack into the queue.
      • Then push the “token” into the stack.
    • Else if token is “(“
      • Push token into stack
    • Else if token is “)”
      • Pop elements from stack to queue until you reach the “(“
      • Remove “(“ from the stack 99638-DD9-D95-C-48-B4-A8-E5-A406-EBA93-F44.png

Evaluate the RPN

  • Make new stack
  • For every token in queue
    • If token is number: push into stack
    • If token is operator:
      • Take 2 nums from top of the stack
      • Use the operator: [num1] (operator) [num2]
      • Put result into stack
  • When stack only has 1 element, you have your answer!

A117-BCA3-60-D8-41-F6-BFFD-FD10-C7453-D5-D.png

Homework:

  • Instead of making a calculator using postfix, make a calculator that uses prefix (the operation goes before the numerals)
  • Prefix: 35 becomes *35, (7-5)2 becomes *2-75

Code Runner Challenge

Calculator that evaluates infix expressions using Reverse Polish Notation (RPN)

View IPYNB Source 
// CODE_RUNNER: Calculator that evaluates infix expressions using Reverse Polish Notation (RPN)

public class RPNCalculator {

    // ─────────────────────────────────────────────
    //  STACK (LIFO) - built from scratch
    // ─────────────────────────────────────────────
    static class Stack {
        private double[] data = new double[100];
        private int top = -1;

        void push(double val) { data[++top] = val; }
        double pop()          { return data[top--]; }
        double peek()         { return data[top]; }
        boolean isEmpty()     { return top == -1; }

        public String toString() {
            String s = "[";
            for (int i = 0; i <= top; i++)
                s += (data[i] % 1 == 0 ? (int) data[i] : data[i]) + (i < top ? ", " : "");
            return s + "]";
        }
    }

    // ─────────────────────────────────────────────
    //  STRING STACK - for operators and infix building
    // ─────────────────────────────────────────────
    static class StringStack {
        private String[] data = new String[100];
        private int top = -1;

        void push(String val) { data[++top] = val; }
        String pop()          { return data[top--]; }
        String peek()         { return data[top]; }
        boolean isEmpty()     { return top == -1; }
    }

    // ─────────────────────────────────────────────
    //  QUEUE (FIFO) - built from scratch
    // ─────────────────────────────────────────────
    static class Queue {
        private String[] data = new String[200];
        private int front = 0, back = 0;

        void enqueue(String val) { data[back++] = val; }
        String dequeue()         { return data[front++]; }
        boolean isEmpty()        { return front == back; }
        int size()               { return back - front; }

        public String toString() {
            String s = "[";
            for (int i = front; i < back; i++)
                s += data[i] + (i < back - 1 ? ", " : "");
            return s + "]";
        }
    }

    // ─────────────────────────────────────────────
    //  PRECEDENCE HELPER
    // ─────────────────────────────────────────────
    static int precedence(String op) {
        switch (op) {
            case "+": case "-": return 1;
            case "*": case "/": case "%": return 2;
            case "^": return 3;
            default: return -1;
        }
    }

    static boolean isOperator(String token) {
        return precedence(token) != -1;
    }

    static boolean isNumber(String token) {
        try { Double.parseDouble(token); return true; }
        catch (NumberFormatException e) { return false; }
    }

    // ─────────────────────────────────────────────
    //  STACK DEMO
    // ─────────────────────────────────────────────
    static void stackDemo() {
        System.out.println("=== STACK DEMO (LIFO) ===");
        Stack stack = new Stack();
        int[] items = {10, 20, 30, 40};
        for (int item : items) {
            stack.push(item);
            System.out.println("  push(" + item + ") -> stack = " + stack);
        }
        System.out.println();
        while (!stack.isEmpty()) {
            double val = stack.pop();
            System.out.println("  pop() = " + (int) val + " -> stack = " + stack);
        }
    }

    // ─────────────────────────────────────────────
    //  QUEUE DEMO
    // ─────────────────────────────────────────────
    static void queueDemo() {
        System.out.println("\n=== QUEUE DEMO (FIFO) ===");
        Queue queue = new Queue();
        String[] items = {"A", "B", "C", "D"};
        for (String item : items) {
            queue.enqueue(item);
            System.out.println("  enqueue(" + item + ") -> queue = " + queue);
        }
        System.out.println();
        while (!queue.isEmpty()) {
            String val = queue.dequeue();
            System.out.println("  dequeue() = " + val + " -> queue = " + queue);
        }
    }

    // ─────────────────────────────────────────────
    //  CALCULATOR FUNCTIONS
    // ─────────────────────────────────────────────
    static double add(double a, double b)      { return a + b; }
    static double subtract(double a, double b) { return a - b; }
    static double multiply(double a, double b) { return a * b; }
    static double divide(double a, double b) {
        if (b == 0) { System.out.println("Error: Cannot divide by zero!"); return 0; }
        return a / b;
    }
    static double power(double a, double b)  { return Math.pow(a, b); }
    static double modulo(double a, double b) { return a % b; }
    static double floorDiv(double a, double b) { return Math.floor(a / b); }

    static void calculatorDemo() {
        System.out.println("\n=== CALCULATOR FUNCTIONS ===");
        System.out.println("  add(10, 5)       = " + add(10, 5));
        System.out.println("  subtract(10, 5)  = " + subtract(10, 5));
        System.out.println("  multiply(10, 5)  = " + multiply(10, 5));
        System.out.println("  divide(10, 5)    = " + divide(10, 5));
        System.out.println("  power(2, 8)      = " + power(2, 8));
        System.out.println("  modulo(17, 5)    = " + modulo(17, 5));
        System.out.println("  floorDiv(17, 5)  = " + floorDiv(17, 5));
    }

    // ─────────────────────────────────────────────
    //  TOKENIZER
    // ─────────────────────────────────────────────
    static String[] tokenize(String expression) {
        String expr = expression.replace(" ", "");
        String[] temp = new String[200];
        int count = 0;
        int i = 0;
        while (i < expr.length()) {
            char c = expr.charAt(i);
            if (Character.isDigit(c) || c == '.') {
                int j = i;
                while (j < expr.length() && (Character.isDigit(expr.charAt(j)) || expr.charAt(j) == '.'))
                    j++;
                temp[count++] = expr.substring(i, j);
                i = j;
            } else {
                temp[count++] = String.valueOf(c);
                i++;
            }
        }
        String[] result = new String[count];
        for (int k = 0; k < count; k++) result[k] = temp[k];
        return result;
    }

    // ─────────────────────────────────────────────
    //  INFIX TO RPN (Shunting-Yard)
    // ─────────────────────────────────────────────
    static Queue infixToRPN(String expression) {
        String[] tokens = tokenize(expression);
        Queue outputQueue = new Queue();
        StringStack opStack = new StringStack();

        for (String token : tokens) {
            if (isNumber(token)) {
                outputQueue.enqueue(token);
            } else if (isOperator(token)) {
                while (!opStack.isEmpty()
                        && !opStack.peek().equals("(")
                        && isOperator(opStack.peek())
                        && precedence(opStack.peek()) >= precedence(token)) {
                    outputQueue.enqueue(opStack.pop());
                }
                opStack.push(token);
            } else if (token.equals("(")) {
                opStack.push(token);
            } else if (token.equals(")")) {
                while (!opStack.isEmpty() && !opStack.peek().equals("("))
                    outputQueue.enqueue(opStack.pop());
                if (!opStack.isEmpty()) opStack.pop();
            }
        }
        while (!opStack.isEmpty())
            outputQueue.enqueue(opStack.pop());

        return outputQueue;
    }

    // ─────────────────────────────────────────────
    //  APPLY OPERATOR
    // ─────────────────────────────────────────────
    static double applyOp(String op, double a, double b) {
        switch (op) {
            case "+": return add(a, b);
            case "-": return subtract(a, b);
            case "*": return multiply(a, b);
            case "/": return divide(a, b);
            case "%": return modulo(a, b);
            case "^": return power(a, b);
            default:  throw new RuntimeException("Unknown operator: " + op);
        }
    }

    // ─────────────────────────────────────────────
    //  EVALUATE RPN
    // ─────────────────────────────────────────────
    static double evaluateRPN(Queue tokens, boolean verbose) {
        Queue copy = new Queue();
        String[] snapshot = new String[tokens.size()];
        int n = tokens.size();
        for (int i = 0; i < n; i++) {
            snapshot[i] = tokens.dequeue();
            copy.enqueue(snapshot[i]);
        }
        if (verbose) System.out.println("  Tokens: " + copy);

        Stack stack = new Stack();
        for (String token : snapshot) {
            if (isNumber(token)) {
                stack.push(Double.parseDouble(token));
                if (verbose) System.out.println("  PUSH " + token + " -> stack = " + stack);
            } else if (isOperator(token)) {
                double b = stack.pop();
                double a = stack.pop();
                double result = applyOp(token, a, b);
                stack.push(result);
                if (verbose) {
                    String as = a % 1 == 0 ? String.valueOf((int) a) : String.valueOf(a);
                    String bs = b % 1 == 0 ? String.valueOf((int) b) : String.valueOf(b);
                    String rs = result % 1 == 0 ? String.valueOf((int) result) : String.valueOf(result);
                    System.out.println("  " + as + " " + token + " " + bs + " = " + rs + " -> stack = " + stack);
                }
            }
        }
        double answer = stack.pop();
        if (verbose) System.out.println("  Answer: " + (answer % 1 == 0 ? (int) answer : answer));
        return answer;
    }

    // ─────────────────────────────────────────────
    //  FULL CALCULATOR
    // ─────────────────────────────────────────────
    static double rpnCalculator(String expression) {
        System.out.println("\nExpression : " + expression);
        Queue rpn = infixToRPN(expression);
        System.out.println("RPN tokens : " + rpn);
        double result = evaluateRPN(rpn, true);
        System.out.println("Final Answer: " + (result % 1 == 0 ? (int) result : result));
        return result;
    }

    // ─────────────────────────────────────────────
    //  POSTFIX TO INFIX
    // ─────────────────────────────────────────────
    static String postfixToInfix(String[] tokens) {
        StringStack stack = new StringStack();
        for (String token : tokens) {
            if (!isOperator(token)) {
                double d = Double.parseDouble(token);
                stack.push(d % 1 == 0 ? String.valueOf((int) d) : token);
            } else {
                String b = stack.pop();
                String a = stack.pop();
                stack.push("(" + a + " " + token + " " + b + ")");
            }
        }
        return stack.pop();
    }

    // ─────────────────────────────────────────────
    //  POPCORN HACK
    // ─────────────────────────────────────────────
    static void popcornHack() {
        System.out.println("\n=== POPCORN HACK: Postfix -> Infix ===");

        String[][] problems = {
            {"6", "3", "*", "4", "+"},
            {"10", "2", "8", "*", "+", "3", "-"},
            {"15", "3", "/", "4", "2", "*", "+"},
            {"7", "3", "2", "*", "+", "5", "-"},
            {"9", "3", "+", "2", "^"}
        };

        String[] postfixStrs = {
            "6 3 * 4 +",
            "10 2 8 * + 3 -",
            "15 3 / 4 2 * +",
            "7 3 2 * + 5 -",
            "9 3 + 2 ^"
        };

        System.out.printf("  %-3s %-28s %-32s %s%n", "#", "Postfix", "Infix", "Value");
        System.out.println("  " + "─".repeat(70));

        for (int i = 0; i < problems.length; i++) {
            String infix = postfixToInfix(problems[i]);
            Stack stk = new Stack();
            for (String t : problems[i]) {
                if (isOperator(t)) {
                    double b = stk.pop(), a = stk.pop();
                    stk.push(applyOp(t, a, b));
                } else {
                    stk.push(Double.parseDouble(t));
                }
            }
            double val = stk.pop();
            String valStr = val % 1 == 0 ? String.valueOf((int) val) : String.valueOf(val);
            System.out.printf("  %-3d %-28s %-32s = %s%n", i + 1, postfixStrs[i], infix, valStr);
        }
    }

    // ─────────────────────────────────────────────
    //  MAIN
    // ─────────────────────────────────────────────
    public static void main(String[] args) {
        RPNCalculator calc = new RPNCalculator();

        calc.stackDemo();
        calc.queueDemo();
        calc.calculatorDemo();

        System.out.println("\n=== RPN EVALUATOR EXAMPLES ===");
        System.out.println("--- 8 9 + 10 3 * 8 * ---");
        Queue q1 = new Queue();
        for (String t : new String[]{"8","9","+","10","3","*","8","*"}) q1.enqueue(t);
        calc.evaluateRPN(q1, true);

        System.out.println("\n--- 8 2 ^ 8 8 * + ---");
        Queue q2 = new Queue();
        for (String t : new String[]{"8","2","^","8","8","*","+"}) q2.enqueue(t);
        calc.evaluateRPN(q2, true);

        System.out.println("\n=== FULL CALCULATOR ===");
        for (String expr : new String[]{"(3 + 5) * 8", "8^2 + 8*8", "10 + 2 * 8 - 3", "(9 + 3)^2"})
            calc.rpnCalculator(expr);

        calc.popcornHack();

        System.out.println("\n=== TRY YOUR OWN ===");
        String myExpression = "(100 - 4 * 5) ^ 2 / 10"; // change this!
        calc.rpnCalculator(myExpression);
    }
}

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

Course Timeline