Page 503 - Computer science 868 Class 12
P. 503
55 default:System.out.println("EXIT from Menu");
56 }
57 }while(ch>=1&&ch<=3);
58 }
59 }
13.1.2 Applications of Stack
The following are the applications of the Stack.
• Conversion of infix expressions to prefix and postfix forms
• Reversing the String
• Recursion [Application of stack in recursion is explained in details in Chapter 10 of this book]
Conversion of Infix expression to postfix and prefix notations
The notation for basic arithmetic expressions can be of three types depending on the placement of operators in
between the operands. They are:
• Infix notation: This is the general way of writing an arithmetic expression in which the operator is placed in between
the operands. For example: A+B or X*Y etc.
• Prefix notation: In this notation, the operator is placed in front of the operand.
For example: +AB or *XY etc. The operation is performed by the operator placed before the two operands.
Prefix notation is also known as polish notation.
• Postfix notation: In this notation, the operator is placed after the operands. The arithmetic operation is performed
by the operator following it. For example: AB+ or XY* etc.
Postfix notation is also known as reverse polish notation.
The algorithm to convert an Infix expression to its Postfix form is given below.
Step 1: Start.
Step 2: Repeat Step 3 to step 7 by reading the infix expression from left to right one element at a time.
Step 3: If the symbol scanned is an operand, append it to the postfix expression.
Step 4: If the symbol scanned is a left parenthesis, then push it to the stack.
Step 5: If the symbol scanned is a right parenthesis, then pop one operator at a time from the top and append it to
the postfix string until the matching left parenthesis is reached. The brackets are discarded.
Step 6: If the symbol scanned is an operator and has precedence higher than the operator currently at the top, then
push the new operator onto the stack.
Step 7: If the symbol scanned is an operator and has precedence lower or equal to the operator currently at the top,
then the operators are popped one by one until we get an operator with lower precedence than the new
scanned operator. The operators popped are appended to the postfix expression.
Step 8: When the infix string is fully scanned, the stack may still contain some operators. All the remaining operators
should be popped and appended to the postfix string.
Step 9: Stop.
501
Data Structures 501

