4.
Implement Stack as an ADT and use it to evaluate a prefix/postfix
expression.
5. Implement Queue as an ADT.
[Link]
class Stack:
"""Class to implement Stack as an ADT."""
def __init__(self):
[Link] = []
def push(self, item):
"""Push an item onto the stack."""
[Link](item)
def pop(self):
"""Pop an item from the stack."""
if not self.is_empty():
return [Link]()
raise IndexError("Pop from empty stack")
def peek(self):
"""Peek at the top item without removing it."""
if not self.is_empty():
return [Link][-1]
raise IndexError("Peek from empty stack")
def is_empty(self):
"""Check if the stack is empty."""
return len([Link]) == 0
def size(self):
"""Return the size of the stack."""
return len([Link])
def evaluate_postfix(expression):
"""Evaluate a postfix expression using a stack."""
stack = Stack()
for char in [Link]():
if [Link]():
[Link](int(char))
else:
# Pop the top two elements for the operation
b = [Link]()
a = [Link]()
if char == '+':
[Link](a + b)
elif char == '-':
[Link](a - b)
elif char == '*':
[Link](a * b)
elif char == '/':
[Link](a / b)
return [Link]()
def evaluate_prefix(expression):
"""Evaluate a prefix expression using a stack."""
stack = Stack()
# Iterate in reverse order for prefix
for char in reversed([Link]()):
if [Link]():
[Link](int(char))
else:
# Pop the top two elements for the operation
a = [Link]()
b = [Link]()
if char == '+':
[Link](a + b)
elif char == '-':
[Link](a - b)
elif char == '*':
[Link](a * b)
elif char == '/':
[Link](a / b)
return [Link]()
# Example usage
if __name__ == "__main__":
postfix_expr = "5 1 2 + 4 * + 3 -"
print("Postfix Evaluation:", evaluate_postfix(postfix_expr))
prefix_expr = "- + 5 * 1 + 2 4 3"
print("Prefix Evaluation:", evaluate_prefix(prefix_expr))
OUTPUT
QUES5. CODE
class Queue:
"""Class to implement Queue as an ADT."""
def __init__(self):
[Link] = []
def enqueue(self, item):
"""Add an item to the rear of the queue."""
[Link](item)
def dequeue(self):
"""Remove and return an item from the front of the queue."""
if not self.is_empty():
return [Link](0)
raise IndexError("Dequeue from empty queue")
def peek(self):
"""Peek at the front item without removing it."""
if not self.is_empty():
return [Link][0]
raise IndexError("Peek from empty queue")
def is_empty(self):
"""Check if the queue is empty."""
return len([Link]) == 0
def size(self):
"""Return the size of the queue."""
return len([Link])
def display(self):
"""Display the current state of the queue."""
print("Queue:", [Link])
# Example usage
if __name__ == "__main__":
q = Queue()
[Link](10)
[Link](20)
[Link](30)
[Link]()
print("Dequeued:", [Link]())
[Link]()
print("Peek:", [Link]())
print("Size:", [Link]())
OUTPUT