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 int evaluatePrefix(String expression) {
        Stack<Integer> stack = new Stack<>();
        String[] tokens = expression.split(" ");

        // Read from right to left
        for (int i = tokens.length - 1; i >= 0; i--) {
            String token = tokens[i];

            // If token is a number, push it to the stack
            if (isNumeric(token)) {
                stack.push(Integer.parseInt(token));
            } else {
                // Operator: Pop two numbers from the stack, apply operation, and push result
                int num1 = stack.pop();
                int num2 = stack.pop();
                int result = applyOperator(token, num1, num2);
                stack.push(result);
            }
        }

        // The final result is the only element left in the stack
        return stack.pop();
    }

    private static boolean isNumeric(String str) {
        return str.matches("-?\\d+"); // Matches integers (including negative numbers)
    }

    private static int applyOperator(String operator, int num1, int num2) {
        return switch (operator) {
            case "+" -> num1 + num2;
            case "-" -> num1 - num2;
            case "*" -> num1 * num2;
            case "/" -> num1 / num2; // Assume valid input (no division by zero)
            case "^" -> (int) Math.pow(num1, num2);
            default -> throw new IllegalArgumentException("Invalid operator: " + operator);
        };
    }

    public static void main(String[] args) {
        String prefixExpression = "+ * 2 3 5"; // Equivalent to (2 * 3) + 5
        int result = evaluatePrefix(prefixExpression);
        System.out.println("Result: " + result); // Output: 11
    }
}
PrefixCalculator.main(null);