Practical Programs
Program 1: Two Stacks in One Array
# Program 1: Implement two stacks in an array
class TwoStacks:
def __init__(self, n):
self.size = n
self.arr = [None] * n
self.top1 = -1
self.top2 = n
def push1(self, x):
if self.top1 < self.top2 - 1:
self.top1 += 1
self.arr[self.top1] = x
else:
print("Stack Overflow")
def push2(self, x):
if self.top1 < self.top2 - 1:
self.top2 -= 1
self.arr[self.top2] = x
else:
print("Stack Overflow")
def pop1(self):
if self.top1 >= 0:
x = self.arr[self.top1]
self.top1 -= 1
return x
else:
return "Stack Underflow"
def pop2(self):
if self.top2 < self.size:
x = self.arr[self.top2]
self.top2 += 1
return x
else:
return "Stack Underflow"
# Example Output
ts = TwoStacks(5)
ts.push1(10)
ts.push2(20)
ts.push1(30)
print(ts.pop1()) # 30
print(ts.pop2()) # 20
Program 2: Queue using Array
# Program 2: Implement Queue using Array
class Queue:
def __init__(self, n):
self.size = n
self.queue = [None] * n
self.front = self.rear = -1
def enqueue(self, x):
if (self.rear + 1) % self.size == self.front:
return "Queue Overflow"
elif self.front == -1:
self.front = self.rear = 0
else:
self.rear = (self.rear + 1) % self.size
self.queue[self.rear] = x
def dequeue(self):
if self.front == -1:
return "Queue Underflow"
elif self.front == self.rear:
x = self.queue[self.front]
self.front = self.rear = -1
return x
else:
x = self.queue[self.front]
self.front = (self.front + 1) % self.size
return x
# Example Output
q = Queue(5)
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
print(q.dequeue()) # 10
print(q.dequeue()) # 20
Program 3: Infix to Postfix and Evaluation
# Program 3: Convert infix to postfix and evaluate postfix
def precedence(op):
if op == '+' or op == '-':
return 1
if op == '*' or op == '/':
return 2
return 0
def infix_to_postfix(expression):
result = []
stack = []
for char in expression:
if char.isdigit():
result.append(char)
elif char == '(':
stack.append(char)
elif char == ')':
while stack and stack[-1] != '(':
result.append(stack.pop())
stack.pop()
else:
while stack and precedence(stack[-1]) >= precedence(char):
result.append(stack.pop())
stack.append(char)
while stack:
result.append(stack.pop())
return "".join(result)
def evaluate_postfix(expression):
stack = []
for char in expression:
if char.isdigit():
stack.append(int(char))
else:
val2 = stack.pop()
val1 = stack.pop()
if char == '+':
stack.append(val1 + val2)
elif char == '-':
stack.append(val1 - val2)
elif char == '*':
stack.append(val1 * val2)
elif char == '/':
stack.append(val1 // val2)
return stack[-1]
# Example Output
exp = "3+(2*5)"
postfix = infix_to_postfix(exp)
print(postfix) # 325*+
print(evaluate_postfix(postfix)) # 13
