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

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

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

class EvaluatePrefix {
    public static Double evaluatePrefix(String prefix) {
        Stack<Double> calcStack = new Stack<Double>();
        String[] tokens = prefix.split(" ");

        for (int i = tokens.length - 1; i >= 0; i--) {
            String token = tokens[i];
            if (token.equals("+")) {
                double a = calcStack.pop();
                double b = calcStack.pop();
                calcStack.push(a + b);
            } else if (token.equals("-")) {
                double a = calcStack.pop();
                double b = calcStack.pop();
                calcStack.push(a - b);
            } else if (token.equals("*")) {
                double a = calcStack.pop();
                double b = calcStack.pop();
                calcStack.push(a * b);
            } else if (token.equals("/")) {
                double a = calcStack.pop();
                double b = calcStack.pop();
                calcStack.push(a / b);
            } else {
                calcStack.push(Double.parseDouble(token));
            }
        }
        return calcStack.pop();
    }

    public static void main(String[] args) {
        String prefix = "* + 2 3 4";
        System.out.println(evaluatePrefix(prefix));
    }
}

// Basically this just takes in a string of postfix characters separated by spaces (so it's easier to separate them into tokens) and evaluates the expression to a number, I made a sample input and output below

// Input: "* + 2 3 4"
// Output: 20.0
// Explanation: (2 + 3) * 4 = 20
EvaluatePrefix.main(new String[0]);

20.0