Page 2 - DATA STRUCTURE-STACKS & QUEUES

print("4.Exit")
ch=int(input("\nChoice: "))

if ch==1:
PUSH()
elif ch==2:
POP()
elif ch==3:
Display()
elif ch==4:
print("Program over")
break
else:
print("Wrong choice! Try again")

Application of Stack
Can be used for converting a mathematical expression into postfix form.
Mathematical expression can be written in prefix/infix/postfix notation.
• infix  (A + B)/(C – D)*E
• postfix  AB+CD–/E*
• prefix  */+AB–CDE
Can be used for evaluating a mathematical expression(in postfix form)

A) Algorithm to find equivalent postfix notation of an infix notation(let Q).
1. Push “(” on to the STACK and add “)” to the end of Q.
2. Scan Q from left to write and repeat steps 3 to 6 for each element of Q until the STACK is
empty
3. If an operand is encountered add it to P (postfix expression).
4. If a left parenthesis is encountered push it onto the stack.
5. If an operator is encountered, then
a. Repeatedly pop from STACK and add to P each operator (from the top of STACK)
which has same precedence as or higher precedence than the operator encountered
b. Add the encountered operator to the STACK
[end of if structure]
6. If a right parenthesis is encountered, then:
a. Repeatedly pop from the STACK and add it to P each operator (from the top of the
STACK) until a left parenthesis is encountered.
b. Remove the left parenthesis (don’t add it to P)
[end of if structure]
[end of step 2 loop]
7. Exit

Example:

Application of Stack (from infix to postfix conversion)
(A+B)*C+D/(B+A*C)-D