Calculator Enactment

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
  • 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

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!

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

import java.util.Stack;

public class PrefixCalculator {

    public static void main(String[] args) {
        String infixExpr = "3*5"; // TEST CASE

        String prefixExpr = infixToPrefix(infixExpr);
        System.out.println("Prefix: " + prefixExpr);

        double result = evaluatePrefix(prefixExpr);
        System.out.println("Result: " + result);
    }

    public static String infixToPrefix(String infix) {
        Stack<Character> operators = new Stack<>();
        Stack<String> operands = new Stack<>();

        for (int i = 0; i < infix.length(); i++) {
            char c = infix.charAt(i);

            if (Character.isDigit(c)) {
                StringBuilder num = new StringBuilder();
                while (i < infix.length() && Character.isDigit(infix.charAt(i))) {
                    num.append(infix.charAt(i++));
                }
                i--;
                operands.push(num.toString());
            }
            else if (c == '(') {
                operators.push(c);
            }
            else if (c == ')') {
                while (operators.peek() != '(') {
                    pushOperator(operators, operands);
                }
                operators.pop();
            }
            else if (isOperator(c)) {
                while (!operators.isEmpty() && precedence(c) <= precedence(operators.peek())) {
                    pushOperator(operators, operands);
                }
                operators.push(c);
            }
        }

        while (!operators.isEmpty()) {
            pushOperator(operators, operands);
        }

        return operands.pop();
    }

    private static void pushOperator(Stack<Character> operators, Stack<String> operands) {
        String op1 = operands.pop();
        String op2 = operands.pop();
        char op = operators.pop();
        operands.push(op + " " + op2 + " " + op1);
    }

    public static double evaluatePrefix(String prefixExpr) {
        String[] tokens = prefixExpr.split(" ");
        Stack<Double> stack = new Stack<>();

        for (int i = tokens.length - 1; i >= 0; i--) {
            String token = tokens[i];
            if (isNumber(token)) {
                stack.push(Double.parseDouble(token));
            } else {
                double a = stack.pop();
                double b = stack.pop();
                stack.push(applyOp(token.charAt(0), a, b));
            }
        }
        return stack.pop();
    }

    private static boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }

    private static boolean isNumber(String s) {
        return s.matches("\\d+");
    }

    private static int precedence(char op) {
        if (op == '*' || op == '/') return 2;
        if (op == '+' || op == '-') return 1;
        return 0;
    }

    private static double applyOp(char op, double a, double b) {
        switch (op) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
            case '/': return a / b;
            default: throw new RuntimeException("Unknown operator");
        }
    }
}
PrefixCalculator.main(new String[]{});

Prefix: * 3 5
Result: 15.0