Expression Evaluation using Stack

Expression Evaluation Problem using Stack

The Expression Evaluation problem involves evaluating a mathematical expression represented in infix notation using stacks. This involves two main steps: converting the infix expression to postfix (Reverse Polish Notation) and then evaluating the postfix expression.

---

Step-by-Step Process

Consider an infix expression:

"3 + 5 * ( 2 - 8 )"

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

1. Convert Infix to Postfix: Use a stack to convert the infix expression to postfix notation.
2. Evaluate the Postfix Expression: Use a stack to evaluate the postfix expression.

---

Step 1: Convert Infix to Postfix

To convert an infix expression to postfix notation, follow these steps:

1. Initialize an Empty Stack: Use a stack to keep track of operators and parentheses.
2. Initialize an Output List: Use a list to build the postfix expression.
3. Process Each Token: Iterate through each token in the infix expression.
4. Handle Operands: Append operands directly to the output list.
5. Handle Left Parenthesis: Push left parentheses onto the stack.
6. Handle Right Parenthesis: Pop from the stack to the output list until a left parenthesis is encountered.
7. Handle Operators: Pop from the stack to the output list while the stack's top has operators of higher or equal precedence, then push the current operator onto the stack.
8. Pop Remaining Operators: After processing all tokens, pop any remaining operators from the stack to the output list.

After performing these steps, the infix expression will be converted to postfix:

Input: "3 + 5 * ( 2 - 8 )"
Output: "3 5 2 8 - * +"

---

Step 2: Evaluate the Postfix Expression

To evaluate the postfix expression, 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 postfix expression.
3. Push Operands: 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:

Input: "3 5 2 8 - * +"
Output: -13

---

Pseudo Code

Convert Infix to Postfix

Function infix_to_postfix(expression):
    # Initialize an empty stack and an empty output list
    stack = []
    output = []
    # Define precedence levels for operators
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    # Process each token in the expression
    For token in expression:
        If token.isalnum():
            output.append(token)
        Elif token == '(':
            stack.append(token)
        Elif token == ')':
            While stack and stack[-1] != '(':
                output.append(stack.pop())
            stack.pop()  # Remove the left parenthesis
        Else:
            While stack and stack[-1] != '(' and precedence[token] <= precedence[stack[-1]]:
                output.append(stack.pop())
            stack.append(token)
    While stack:
        output.append(stack.pop())
    Return output

Evaluate Postfix Expression

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}
    # Process each token in the expression
    For token in expression:
        If token in operators:
            b = stack.pop()
            a = stack.pop()
            result = operators[token](a, b)
            stack.append(result)
        Else:
            stack.append(int(token))
    Return stack.pop()

---

Python Program to Solve the Expression Evaluation Problem 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 convert infix expression to postfix expression using a stack
def infix_to_postfix(expression):
    stack = Stack()
    output = []
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    for token in expression:
        if token.isalnum():
            output.append(token)
        elif token == '(':
            stack.push(token)
        elif token == ')':
            while not stack.is_empty() and stack.peek() != '(':
                output.append(stack.pop())
            stack.pop()  # Remove the left parenthesis
        else:
            while not stack.is_empty() and stack.peek() != '(' and precedence[token] <= precedence[stack.peek()]:
                output.append(stack.pop())
            stack.push(token)
    while not stack.is_empty():
        output.append(stack.pop())
    return output

# 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}
    for token in expression:
        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:
infix_expression = "3 + 5 * ( 2 - 8 )"
print(f"Infix expression: {infix_expression}")  # Output: Infix expression: 3 + 5 * ( 2 - 8 )
postfix_expression = infix_to_postfix(infix_expression.split())
print(f"Postfix expression: {' '.join(postfix_expression)}")  # Output: Postfix expression: 3 5 2 8 - * +
result = evaluate_postfix(postfix_expression)
print(f"Result: {result}")  # Output: Result: -13

This Python program defines a stack with methods for pushing, popping, peeking, checking if the stack is empty, and traversing the stack. The infix_to_postfix function converts a given infix expression to postfix notation using the stack, and the evaluate_postfix function evaluates the postfix expression using the stack to obtain the result.