In polish notation, the operator is placed before the operands. Polish notation has types called Infix, Postfix, and Prefix notation.
Infix Notation: In this notation, the operator symbol is placed between its two operands. For example, to add A to B we can write as A + B, to subtract D from C we write as C – D.
Polish (Prefix) Notation: In this notation named after the Polish mathematician Jan Lukasiewicz the operator symbol is placed before its two operands. For example, to add A to B we can write as + AB or + BA, to subtract D from C we have to write as -CD not as -DC In order to translate an arithmetic expression in infix notation to polish notation, we do step by step using brackets ([]) to indicate the partial translation. The fundamental property of polish notation is that the order in which the operations are to perform is completely determined by the positions of the operators and operands in the expression. Accordingly one never needs parentheses when writing expressions in polish notation.
This notation is also called prefix notation.
Reverse Polish (Postfix) Notation: In this notation, the operator symbol is placed its two operands. For example, to add A to B we can write as AB + or BA +, to subtract D from C we have to write as CD- not as DC In order to translate an arithmetic expression in infix notation to reverse polish notation we do step by step using brackets (11) to indicate the partial translation. Like polish notation here too one never needs the use parentheses when writing expressions in polish notation.
This notation is frequently called postfix (or suffix) notation.
Usage of the stack in procedure call for saving return address: Stacks are frequently used to indicate the order of the procedure calls. Suppose that while processing some procedure A if we are required to move on to procedure B, whose completion is required in order to complete procedure A. Then we place procedure A in the STACK and begin procedure B.
However, suppose that while processing B we are led to procedure C, for some reason Then we place B on the STACK above, and begin process C Now if we are able to complete procedure C then we may continue to procedure B, which is on the top of the STACK. Hence we remove procedure B from the STACK and begin procedure B. Now when we complete procedure 8 then we remove the procedure. A from the STACK leaving STACK empty Finally after completing procedure A we stop. At each stage of the above processing, the stack automatically maintains the order that is required to complete the processing.
Infix to postfix algorithm
INTOPOST(Q,P)
Suppose Q is an arithmetic expression written in infix notation. this algorithm finds the equivalent postfix expression P.
1. Push “(” onto STACK, and add “)” to the end of Q.
2. Scan Q from left to right 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.
4. If a left parenthesis is encountered, push it onto STACK.
5. If an operator ⊗ is encountered, then.
(a) Repeatedly pop from STACK and add to P each operator ( on the top of STACK ) which has the same precedence as or higher precedence than ⊗.
(b) Add x to STACK.
[End of If structure.]
6. If a right parenthesis is encountered, then:
(a) Repeatedly pop from STACK and add to P each operator ( on the top of STACK ) until a left parenthesis is encountered.
(b) Remove the left parenthesis. [Do not add the left parenthesis to P.]
[End of If structure.]
[End of Step 2 loop.]
7. Exit
Infix to prefix Algorithm
INTOPRE(Q,P)
Suppose Q is an arithmetic expression written in infix notation this algorithm finds the equivalent prefix expression P.
1. Push “)” onto STACK, and add “(” to the beg of Q.
2. Scan Q from right to left 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.
4. If a right parenthesis is encountered, push it onto STACK.
5. If an operator x is encountered, then:
(a) Repeatedly pop from STACK and add to P each operator (on the top of STACK) which has higher precedence than x.
(b) Add x to STACK
[End of If structure.]
6. If a left parenthesis is encountered, then:
(a) Repeatedly pop from STACK and add to P each operator (on the top of STACK ) until a right parenthesis is encountered.
(b) Remove the right parenthesis. [Do not add the right parenthesis to P. ]
[End of If structure.]
[End of step 2 loop.]
7. Reverse P.
8. Exit.
Evaluate a postfix expression algorithm
EVALPOST (P, VALUE)
This algorithm finds the VALUE of an arithmetic expression P written in postfix notation.
1. Add a right parenthesis”)” at the end of P. [This acts as a sentinel.]
2. Scan P from left to right and Repeat Steps 3 and 4 for each element of P until the sentinel”)” is encountered.
3. If an operand ⊗ is encountered, put it on STACK.
4. If an operator is encountered, then:
(a) Remove the two top elements of STACK, where A is the top element and B is the next-to-top element.
(b) Evaluate B ⊗ A.
(c) Place the result of (b) back on STACK.
[End of If structure.]
[End of Step 2 loop.]
5. Set VALUE equal to the top element on STACK.
6. Exit
Evaluate a prefix expression algorithm
EVALPRE (P, VALUE)
This algorithm finds the VALUE of an arithmetic expression P written in prefix notation.
1. Add a left parenthesis “(” at the beg of P. [This acts as a sentinel.]
2. Scan P from right to left and Repeat Steps 3 and 4 for each element of P until the sentinel “(” is encountered.
3. If an operand is encountered, put it on STACK.
4. If an operator ⊗ is encountered, then:
(a) Remove the two top elements of STACK, where A is the top element and B is the next-to-top element.
(b) Evaluate A ⊗ B
(c) Place the result of (b) back on STACK.
[End of If structure.]
[End of Step 2 loop.]
5. Set VALUE equal to the top element on STACK
6. Exit