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:
- Convert Infix to Postfix: Use a stack to convert the infix expression to postfix notation.
- 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:
- Initialize an Empty Stack: Use a stack to keep track of operators and parentheses.
- Initialize an Output List: Use a list to build the postfix expression.
- Process Each Token: Iterate through each token in the infix expression.
- Handle Operands: Append operands directly to the output list.
- Handle Left Parenthesis: Push left parentheses onto the stack.
- Handle Right Parenthesis: Pop from the stack to the output list until a left parenthesis is encountered.
- 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.
- 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:
- Initialize an Empty Stack: Use a stack to keep track of operands.
- Process Each Token: Iterate through each token in the postfix expression.
- Push Operands: If the token is an operand, push it onto the stack.
- 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.
- 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.