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.

  1. Expression evaluation
  2. Backtracking (game playing, finding paths, exhaustive searching)
  3. Memory management, run-time environment for nested language features.

Infix to Postfix Conversion: –

Procedure for Postfix Conversion: –

  1. Scan the Infix string from left to right.
  2. Initialize an empty stack.
  3. If the scanned character is an operand, add it to the Postfix string.
  4. If the scanned character is an operator and if the stack is empty push the character to stack.
  5. 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
  6. stack. Repeat this step until the stack is not empty and top Stack has precedence over the character.
  7. Repeat 4 and 5 steps till all the characters are scanned.
  8. After all characters are scanned, we have to add any character that the stack may have to the Postfix string.
  9. If stack is not empty add top Stack to Postfix string and Pop the stack.
  10. 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)
Advertisements