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 + (6*3) + 4 18 + 4 22

2. 10 2 8 * + 3 - 10+(2*8)-3 10+16-3 23

3. 15 3 / 4 2 * + (15/3)+(4*2) 5+8 13

4. 7 3 2 * + 5 - 7+(3*2)-5 7+6-5 8

5. 9 3 + 2 ^ (9+3)^2 12^2 144

Answers Here for Popcorn Hack

1. 6 3 * 4 + (6*3) + 4 18 + 4 22

2. 10 2 8 * + 3 - 10+(2*8)-3 10+16-3 23

3. 15 3 / 4 2 * + (15/3)+(4*2) 5+8 13

4. 7 3 2 * + 5 - 7+(3*2)-5 7+6-5 8

5. 9 3 + 2 ^ (9+3)^2 12^2 144

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

HW

import java.util.*;

public class PrefixCalculator {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter prefix expression: ");
        String expression = scanner.nextLine();
        System.out.println(expression);
        scanner.close();

        try {
            double result = evaluatePrefix(expression);
            System.out.println("Result: " + result);
        } catch (Exception e) {
            System.out.println("Invalid expression!");
        }
    }

    public static double evaluatePrefix(String expr) {
        Stack<Double> stack = new Stack<>();
        String[] tokens = expr.split("\\s+");
        List<String> operators = Arrays.asList("+", "-", "*", "/", "^");

        for (int i = tokens.length - 1; i >= 0; i--) {
            String token = tokens[i];

            if (!operators.contains(token)) {
                stack.push(Double.parseDouble(token));
            } else {
                double operand1 = stack.pop();
                double operand2 = stack.pop();

                switch (token) {
                    case "+": stack.push(operand1 + operand2); break;
                    case "-": stack.push(operand1 - operand2); break;
                    case "*": stack.push(operand1 * operand2); break;
                    case "/": stack.push(operand1 / operand2); break;
                    case "^": stack.push(Math.pow(operand1, operand2)); break;
                    default: throw new IllegalArgumentException("Invalid operator: " + token);
                }
            }
        }

        return stack.pop();
    }
}

PrefixCalculator calc = new PrefixCalculator();
calc.main(null);

Enter prefix expression: + 3 * 5 2
Result: 13.0