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

Here are the answers for converting the postfix expressions to infix notation:

  1. 6 3 * 4 + = (6 * 3) + 4

  2. 10 2 8 * + 3 - = (10 + (2 * 8)) - 3

  3. 15 3 / 4 2 * + = (15 / 3) + (4 * 2)

  4. 7 3 2 * + 5 - = (7 + (3 * 2)) - 5

  5. 9 3 + 2 ^ = (9 + 3)^2

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

homework here:

import java.util.Stack;
import java.util.Scanner;

public class PrefixCalculator {
    
    public static double evaluatePrefix(String expression) {
        // Remove all spaces from the expression
        expression = expression.replaceAll("\\s+", "");
        
        // Create a stack to store operands
        Stack<Double> stack = new Stack<>();
        
        // Process the expression from right to left
        for (int i = expression.length() - 1; i >= 0; i--) {
            char c = expression.charAt(i);
            
            // If the character is a digit, push it to the stack
            if (Character.isDigit(c)) {
                stack.push((double)(c - '0'));
            }
            // If the character is an operator, perform the operation
            else if (isOperator(c)) {
                // Pop two operands from stack
                double operand1 = stack.pop();
                double operand2 = stack.pop();
                
                // Perform operation based on operator
                double result = performOperation(c, operand1, operand2);
                
                // Push result back to stack
                stack.push(result);
            }
        }
        
        // The final result will be at the top of the stack
        return stack.pop();
    }
    
    private static boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
    }
    
    private static double performOperation(char operator, double operand1, double operand2) {
        switch (operator) {
            case '+': return operand1 + operand2;
            case '-': return operand1 - operand2;
            case '*': return operand1 * operand2;
            case '/': return operand1 / operand2;
            case '^': return Math.pow(operand1, operand2);
            default: throw new IllegalArgumentException("Invalid operator: " + operator);
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        System.out.println("Prefix Calculator");
        System.out.println("Examples: *35 means 3*5, *-752 means (7-5)*2");
        System.out.print("Enter a prefix expression: ");
        
        String expression = scanner.nextLine();
        
        try {
            double result = evaluatePrefix(expression);
            System.out.println("Result: " + result);
        } catch (Exception e) {
            System.out.println("Error evaluating expression: " + e.getMessage());
        }
        
        scanner.close();
    }
}

PrefixCalculator.main(null);

Prefix Calculator
Examples: *35 means 3*5, *-752 means (7-5)*2
Enter a prefix expression: Result: 3.0