Evaluate Postfix Expression using Stack

Evaluating Postfix Expression using Stack

Evaluating a postfix expression (also known as Reverse Polish Notation) involves processing the expression from left to right and using a stack to handle operands and operators. This ensures that the expression is evaluated in the correct order without the need for parentheses.

---

Step-by-Step Process

Consider a postfix expression:

"5 6 2 + * 12 4 / -"

To evaluate this postfix expression using a stack, follow these steps:

1. Initialize an Empty Stack: Use a stack to keep track of operands.
2. Process Each Token: Iterate through each token in the expression.
3. Push Operands onto the Stack: If the token is an operand, push it onto the stack.
4. Evaluate Operators: If the token is an operator, pop the necessary number of operands from the stack, perform the operation, and push the result back onto the stack.
5. Final Result: After processing all tokens, the final result will be at the top of the stack.

After performing these steps, the result of the postfix expression will be evaluated.

---

Pseudo Code

Function evaluate_postfix(expression):
    # Initialize an empty stack
    stack = []
    # Define operators and their corresponding operations
    operators = {'+': lambda a, b: a + b,
                 '-': lambda a, b: a - b,
                 '*': lambda a, b: a * b,
                 '/': lambda a, b: a / b}
    # Split the expression into tokens
    tokens = expression.split()
    # Process each token
    For token in tokens:
        If token in operators:
            # Pop two operands from the stack
            b = stack.pop()
            a = stack.pop()
            # Perform the operation and push the result back onto the stack
            result = operators[token](a, b)
            stack.append(result)
        Else:
            # Push operand onto the stack
            stack.append(int(token))
    # The final result is at the top of the stack
    Return stack.pop()

---

Python Program to Evaluate Postfix Expression using Stack

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, data):
        self.stack.append(data)

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        return None

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        return None

    def is_empty(self):
        return len(self.stack) == 0

    def traverse(self):
        for item in reversed(self.stack):
            print(item, end=" -> ")
        print("None")

# Function to evaluate a postfix expression using a stack
def evaluate_postfix(expression):
    stack = Stack()
    operators = {'+': lambda a, b: a + b,
                 '-': lambda a, b: a - b,
                 '*': lambda a, b: a * b,
                 '/': lambda a, b: a / b}
    tokens = expression.split()
    for token in tokens:
        if token in operators:
            b = stack.pop()
            a = stack.pop()
            result = operators[token](a, b)
            stack.push(result)
        else:
            stack.push(int(token))
    return stack.pop()

# Example usage:
postfix_expression = "5 6 2 + * 12 4 / -"
print(f"Postfix expression: {postfix_expression}")  # Output: Postfix expression: 5 6 2 + * 12 4 / -
result = evaluate_postfix(postfix_expression)
print(f"Result: {result}")  # Output: Result: 46

This Python program defines a stack with methods for pushing, popping, peeking, checking if the stack is empty, and traversing the stack. The evaluate_postfix function uses the stack to evaluate a given postfix expression by processing each token, performing operations with operands from the stack, and returning the final result.