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.