What are the applications of stack explain prefix, postfix and infix notation with suitable example?
Answer: – Three applications of stacks are presented here. These examples are central to many activities that a computer must do and deserve time spent with them.
- Expression evaluation
- Backtracking (game playing, finding paths, exhaustive searching)
- Memory management, run-time environment for nested language features.
Infix to Postfix Conversion: –
Procedure for Postfix Conversion: –
- Scan the Infix string from left to right.
- Initialize an empty stack.
- If the scanned character is an operand, add it to the Postfix string.
- If the scanned character is an operator and if the stack is empty push the character to stack.
- If the scanned character is an Operator and the stack is not empty, compare the precedence of the character with the element on top of the stack. If top Stack has higher precedence over the scanned character pop the stack else push the scanned character to
- stack. Repeat this step until the stack is not empty and top Stack has precedence over the character.
- Repeat 4 and 5 steps till all the characters are scanned.
- After all characters are scanned, we have to add any character that the stack may have to the Postfix string.
- If stack is not empty add top Stack to Postfix string and Pop the stack.
- Repeat this step as long as stack is not empty.
Infix to Prefix Conversion: –
Algorithm of Infix to Prefix: –
Step 1. Push “)” onto STACK, and add “(“ to end of the A Step 2. Scan A from right to left and repeat step 3 to 6 for each element of A until the STACK is empty Step 3. If an operand is encountered add it to B Step 4. If a right parenthesis is encountered push it onto STACK Step 5. If an operator is encountered then: a. Repeatedly pop from STACK and add to B each operator (on the top of STACK) which has same or higher precedence than the operator. b. Add operator to STACK Step 6. If left parenthesis is encontered then a. Repeatedly pop from the STACK and add to B (each operator on top of stack until a left parenthesis is encounterd) b. Remove the left parenthesis Step 7. Exit
Postfix to Infix Conversion: –
Algorithm of Postfix to Infix: –
Expression = abc-+de-fg-h+/*
1.While there are input symbol left 2. Read the next symbol from input. 3. If the symbol is an operand Push it onto the stack. 4. Otherwise, the symbol is an operator. 5. If there are fewer than 2 values on the stack Show Error /* input not sufficient values in the expression */ 6. Else Pop the top 2 values from the stack. Put the operator, with the values as arguments and form a string. Encapsulate the resulted string with parenthesis. Push the resulted string back to stack. 7. If there is only one value in the stack That value in the stack is the desired infix string. 8. If there are more values in the stack Show Error /* The user input has too many values */
Prefix to Infix Conversion: –
Algorithm of Prefix to Infix: –
This algorithm is a non-tail recursive method. 1.The reversed input string is completely pushed into a stack. prefixToInfix(stack) 2.IF stack is not empty a. Temp -->pop the stack b. IF temp is a operator Write a opening parenthesis to output prefixToInfix(stack) Write temp to output prefixToInfix(stack) Write a closing parenthesis to output c. ELSE IF temp is a space -->prefixToInfix(stack) d. ELSE Write temp to output IF stack.top NOT EQUAL to space -->prefixToInfix(stack)