DSA Assigment – 3
Fabiha
15436
114843
Question 1:
1- Translate by program in c sharp or python and hand, each infix expression to its equivalent
postfix expression.
i- ((A + B) / D) ^ ((E – F) * G
ii- A+B*C+D
iii-
Handwritten:
Code:
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
return None
def peek(self):
if not self.is_empty():
return self.items[-1]
return None
def precedence(op):
if op in ('+', '-'):
return 1
if op in ('*', '/'):
return 2
if op == '^':
return 3
return 0
def is_operand(char):
return char.isalpha() or char.isdigit()
def infix_to_postfix(expression):
stack = Stack()
result = []
for char in expression:
if is_operand(char):
result.append(char)
elif char == '(':
stack.push(char)
elif char == ')':
while not stack.is_empty() and stack.peek() != '(':
result.append(stack.pop())
stack.pop()
else:
while not stack.is_empty() and precedence(stack.peek()) >=
precedence(char):
result.append(stack.pop())
stack.push(char)
while not stack.is_empty():
result.append(stack.pop())
return ''.join(result)
expression1 = "((A+B)/D)^((E-F)*G)"
expression2 = "A+B*C+D"
print("Infix:", expression1)
print("Postfix of expression 1:", infix_to_postfix(expression1))
print("Infix:", expression2)
print("Postfix of expression 2:", infix_to_postfix(expression2))
Output:
Question 2:
2- Translate by program in c sharp or python and hand, each infix expression to its equivalent
prefix expression.
i. (A + B) * (C + D)
ii. A*B+C*D
iii. A+B+C+D
Handwritten:
Code:
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
return None
def peek(self):
if not self.is_empty():
return self.items[-1]
return None
def precedence(op):
if op in ('+', '-'):
return 1
if op in ('*', '/'):
return 2
if op == '^':
return 3
return 0
def is_operand(char):
return char.isalpha() or char.isdigit()
def infix_to_prefix(expression):
expression = expression[::-1]
expression = ''.join(['(' if char == ')' else ')' if char == '(' else char
for char in expression])
postfix_expression = infix_to_postfix(expression)
prefix_expression = postfix_expression[::-1]
return prefix_expression
def infix_to_postfix(expression):
stack = Stack()
result = []
for char in expression:
if is_operand(char):
result.append(char)
elif char == '(':
stack.push(char)
elif char == ')':
while not stack.is_empty() and stack.peek() != '(':
result.append(stack.pop())
stack.pop()
else:
while not stack.is_empty() and precedence(stack.peek()) >=
precedence(char):
result.append(stack.pop())
stack.push(char)
while not stack.is_empty():
result.append(stack.pop())
return ''.join(result)
expression1 = "(A+B)*(C+D)"
expression2 = "A*B+C*D"
expression3 = "A+B+C+D"
print("Infix:", expression1)
print("Prefix of expression 1:", infix_to_prefix(expression1))
print("Infix:", expression2)
print("Prefix of expression 2:", infix_to_prefix(expression2))
print("Infix:", expression3)
print("Prefix of expression 3:", infix_to_prefix(expression3))
Output:
Question 3:
3. Consider the following expression:
E: 6 + 2 ^ 3 ^ 2 – 4 * 5
Evaluate the expression E,
(a) assuming that exponentiation is performed from left to right, as are the other operations,
and
(b) assuming that exponentiation is performed from right to left.
Handwritten:
Code:
def left_to_right_exponentiation(expression):
import re
expression = re.sub(r'\^', r'**', expression)
return eval(expression)
def right_to_left_exponentiation(expression):
import re
def evaluate_expression(tokens):
tokens = tokens[::-1]
stack = []
for token in tokens:
if token.isdigit():
stack.append(int(token))
else:
a = stack.pop()
b = stack.pop()
if token == '^':
stack.append(b ** a)
elif token == '*':
stack.append(b * a)
elif token == '/':
stack.append(b / a)
elif token == '+':
stack.append(b + a)
elif token == '-':
stack.append(b - a)
return stack[0]
expression = re.sub(r'\^', r' ** ', expression)
tokens = expression.split()
i = 0
while i < len(tokens):
if tokens[i] == '**':
base = int(tokens[i - 1])
exponent = int(tokens[i + 1])
result = base ** exponent
tokens = tokens[:i - 1] + [str(result)] + tokens[i + 2:]
i -= 1
i += 1
return eval(' '.join(tokens))
expression = "6 + 2 ^ 3 ^ 2 - 4 * 5"
left_to_right_result = left_to_right_exponentiation(expression)
print(f"Result with left-to-right exponentiation: {left_to_right_result}")
right_to_left_result = right_to_left_exponentiation(expression)
print(f"Result with right-to-left exponentiation: {right_to_left_result}")
Output:
Question 4:
4. Consider each of the following postfix expressions:
P: 5 3 + 2 * 6 9 7 - / -
Q: 3 5 + 6 4 - * 4 1 – 2 ^
+
R: 3 1 + 2 ^ 7 4 – 2 * + 5
-
a) Translate by hand, each expression into infix notation and then evaluate.
b) Evaluate each postfix expression using the program in c sharp or python.
Handwritten:
Code?
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
return None
def evaluate_postfix(expression):
stack = Stack()
tokens = expression.split()
for token in tokens:
if token.isdigit():
stack.push(int(token))
else:
right_operand = stack.pop()
left_operand = stack.pop()
if token == '+':
result = left_operand + right_operand
elif token == '-':
result = left_operand - right_operand
elif token == '*':
result = left_operand * right_operand
elif token == '/':
result = left_operand / right_operand
elif token == '^':
result = left_operand ** right_operand
stack.push(result)
return stack.pop()
expression_P = "5 3 + 2 * 6 9 7 - / -"
expression_Q = "3 5 + 6 4 - * 4 1 - 2 ^ +"
expression_R = "3 1 + 2 ^ 7 4 - 2 * + 5 -"
print("Result of P:", evaluate_postfix(expression_P))
print("Result of Q:", evaluate_postfix(expression_Q))
print("Result of R:", evaluate_postfix(expression_R))
Output:
Question 5:
5. Write a program in c sharp or python to evaluate a prefix expression. Use the program in c sharp
or python to evaluate:
+ + 2 * 3 2 / 10 2
Handwritten:
Code:
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
return None
def evaluate_prefix(expression):
stack = Stack()
tokens = expression.split()[::-1]
for token in tokens:
if token.isdigit():
stack.push(int(token))
else:
left_operand = stack.pop()
right_operand = stack.pop()
if token == '+':
result = left_operand + right_operand
elif token == '-':
result = left_operand - right_operand
elif token == '*':
result = left_operand * right_operand
elif token == '/':
result = left_operand / right_operand
elif token == '^':
result = left_operand ** right_operand
stack.push(result)
return stack.pop()
expression = "+ + 2 * 3 2 / 10 2"
print("Result:", evaluate_prefix(expression))
Output:
Question 6:
6. Write a program in c sharp or python to traverse doubly linked list in forward direction.
Code:
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.prev = current
def traverse_forward(self):
current = self.head
while current:
print(current.data, end=" ")
current = current.next
print()
dll = DoublyLinkedList()
dll.append(78)
dll.append(29)
dll.append(30)
dll.append(47)
dll.append(56)
print("Doubly linked list traversal (forward):")
dll.traverse_forward()
Output:
Question 7:
7. Write a program in c sharp or python to traverse doubly linked list in backward direction.
Code:
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
new_node.prev = last_node
def traverse_backward(self):
if self.head is None:
print("Doubly linked list is empty")
return
last_node = self.head
while last_node.next:
last_node = last_node.next
print("Traversal in backward direction:")
while last_node:
print(last_node.data, end=" ")
last_node = last_node.prev
print()
dll = DoublyLinkedList()
dll.append(0)
dll.append(20)
dll.append(30)
dll.append(40)
dll.append(50)
dll.traverse_backward()
Output:
Question 8:
8. Write a program in c sharp or python to delete a node from a singly linked list from a given
location LOC.
Code:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
def delete_node(self, loc):
if self.head is None:
print("List is empty")
return
temp = self.head
if loc == 0:
self.head = temp.next
temp = None
return
for i in range(loc - 1):
temp = temp.next
if temp is None:
break
if temp is None or temp.next is None:
print("Location is beyond the list length ")
return
next = temp.next.next
temp.next = None
temp.next = next
def print_list(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.append(4)
sll.append(5)
print("ORIGINAL LIST:")
sll.print_list()
loc = 2
sll.delete_node(loc)
print(f"LIST AFTER DELEETING NODE AT LOCATION {loc}:")
sll.print_list()
Output:
Question 9:
9. Write a program to sort and print a stack in ascending order.
Code:
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
return None
def peek(self):
if not self.is_empty():
return self.items[-1]
return None
def size(self):
return len(self.items)
def print_stack(self):
print(self.items)
def sort_stack(stack):
auxiliary_stack = Stack()
while not stack.is_empty():
current = stack.pop()
while not auxiliary_stack.is_empty() and auxiliary_stack.peek() >
current:
stack.push(auxiliary_stack.pop())
auxiliary_stack.push(current)
while not auxiliary_stack.is_empty():
stack.push(auxiliary_stack.pop())
return stack
original_stack = Stack()
elements = [34, 3, 31, 98, 92, 23]
for element in elements:
original_stack.push(element)
print("")
print(" ORIGINAL STACK:")
original_stack.print_stack()
sorted_stack = sort_stack(original_stack)
print("")
print(" SORTED!")
sorted_stack.print_stack()
Output:
