Stack

State TRUE or FALSE for the following cases:

(a) Stack is a linear data structure.

(b) Stack does not follow LIFO rule.

(c) PUSH operation may result into underflow condition.

(d) In POSTFIX notation for expression, operators are placed after operands.

Answer

(a) True
Reason — A stack is a linear data structure following the Last In, First Out (LIFO) principle, where elements are arranged sequentially.

(b) False
Reason — A stack follows the Last In, First Out (LIFO) rule. In a stack, the last element added is the first one to be removed from the stack.

(c) False
Reason — When attempting to remove an element (POP operation) from an empty stack, it leads to an underflow condition, resulting in an exception being raised.

(d) True
Reason — In POSTFIX notation for expression, operators are placed after the corresponding operands.

Find the output of the following code:

result = 0
numberList = [10, 20, 30]
numberList.append(40)
result = result + numberList.pop()
result = result + numberList.pop()
print("Result=", result)

Answer

Result= 70

The code initializes result to 0 and creates a list [10, 20, 30]. It appends 40 to the list and then performs two pop() operations on the list, which removes and returns the last element (40 and 30). These values are added to result, resulting in result being 70. Finally, the code prints "Result=" followed by the value of result, which is 70.

Find the output of the following code:

answer = []; output = ''
answer.append('T')
answer.append('A')
answer.append('M')
ch = answer.pop()
output = output + ch
ch = answer.pop()
output = output + ch
ch = answer.pop()
output = output + ch
print("Result=", output)

Answer

Result= MAT

The code initializes an empty list answer and an empty string output. It appends the characters 'T', 'A', and 'M' to the answer list. After appending, answer list becomes ['T', 'A', 'M'].
After that, three pop() operations are performed on answer, removing and returning the last element each time ('M', 'A', and 'T' respectively). These characters are concatenated to the output string. So, output string becomes MAT which is printed as the final output.

Write a program to reverse a string using stack.

Answer

def push(stack, item):
    stack.append(item)

def pop(stack):
    if stack == []:
        return
    return stack.pop()

def reverse(string):
    n = len(string)
    stack = []
    for i in range(n):
        push(stack, string[i])
    string = ""
    for i in range(n):
        string += pop(stack)
    return string

string = input("Enter a string: ")
print("String:", string)
reversedStr = reverse(string)
print("Reversed String:", reversedStr)

Enter a string: Hello world
String: Hello world
Reversed String: dlrow olleH

For the following arithmetic expression:

((2 + 3) * (4 / 2)) + 2

Show step-by-step process for matching parentheses using stack data structure.

Answer

For matching parentheses, we can push in the stack for each opening parenthesis of the expression and pop from the stack for each closing parenthesis.

Scanning from left to right:

Empty stack => Balanced Parentheses

Evaluate following postfix expression while showing status of stack after each operation given A = 3, B = 5, C = 1, D = 4.

AB + C *

Answer

AB + C * = 35 + 1 *

Scanning from left to right :

Hence, AB + C * = 35 + 1 * = 8

Evaluate following postfix expression while showing status of stack after each operation given A = 3, B = 5, C = 1, D = 4.

AB * C / D *

Answer

AB * C / D * = 35 * / 4 *

Scanning from left to right :

Hence, AB * C / D * = 35 * / 4 * = 60

Convert the following infix notation to postfix notation, showing stack and string contents at each step.

A + B - C * D

Answer

Given,

A + B - C * D

Scanning from left to right :

Postfix notation of A + B - C * D = AB+CD*-

Convert the following infix notation to postfix notation, showing stack and string contents at each step.

A * (( C + D)/E)

Answer

Given,

A * (( C + D)/E)

Scanning from left to right:

Postfix notation of A * (( C + D)/E) = ACD+E/*

Write a program to create a Stack for storing only odd numbers out of all the numbers entered by the user. Display the content of the Stack along with the largest odd number in the Stack. (Hint. Keep popping out the elements from stack and maintain the largest element retrieved so far in a variable. Repeat till Stack is empty)

Answer

def push(stack, item):
    stack.append(item)

def pop(stack):
    if stack == []:
        return
    return stack.pop()

def oddStack(num):
    if num % 2 == 1:
        push(stack, num)

def GetLargest(stack):
    elem = pop(stack)
    large = elem
    while elem != None:
        if large < elem:
            large = elem
        elem = pop(stack)
    return large

n = int(input("How many numbers?"))
stack = []
for i in range(n):
    number = int(input("Enter number:"))
    oddStack(number)
print("Stack created is", stack)
bigNum = GetLargest(stack)
print("Largest number in stack", bigNum)

How many numbers?8
Enter number:1
Enter number:2
Enter number:3
Enter number:4
Enter number:5
Enter number:6
Enter number:7
Enter number:8
Stack created is [1, 3, 5, 7]
Largest number in stack 7