1)What is Infix notation ?
For most common arithmatic operation, the operator symbol is placed between its two operands. This is called Infix notation. For example,
A + B, C - D, E / F
With this notation we must distinguish between
(A+B)*C and A+(B*C)
by using either parentheses or some operator convention such as the usual precedence levels.
Accordingly, the order of the operators and operands in an arithmatic expression does not
uniquely determine the order in which the operations are to be performed.
2)Write short notes on Prefix & Postfix notation ?
Polish/ Prefix notation: Polish notation named after the Polish mathematician Jan Lukasiewicz,
refers to the notation in which the operator symbol is placed before its two operands.
For example, +AB, -CD, *EF
With this notation the following Infix expression written into Polish notation like this:
(A+B)*C = (+AB) * C = *+ ABC
A+(B*C) = A + (*BC) = +A *BC
The fundamental property of Polish notation is that the order in which the operations are
to be performed is completely determined by the position of the operators and operands in the expression.
Accordingly, one never needs parentheses when written expression in Polish/ Prefix notation.
Reverse Polish/ Postfix notation: This is refers to the analogous notation in which the operator symbol is placed after its two operands.
This notation is frequently called Postfix or Suffix notation.
For example, AB+, CD-, EF*
With this notation the following Infix expression written into Reverse Polish notation like this:
(A+B)*C = (AB+) * C = AB+ C*
A+(B*C) = A + (BC*) = ABC*+
Again, one never needs parentheses when written expression in Reverse Polish/ Postfix notation.
3)How computer evaluates an arithmatic expression written in Infix notation ?
The computer usually evaluates an arithmatic expression written in Infix notation in two steps. Fisrt it converts the expression to Postfix notation and then it evalutes the Postfix expression. In each step, the STACK is the main tool that is used to accomplish the given task.
4)Write the Infix to Postfix Convertion Algorithm.
POLISH (Q,P)
Suppose Q is an arithmatic 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 Operator ⛒ .
(b) Add Operator ⛒ 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.
5)Find the Postfix notation of the following Infix expression ?
i) (A+B)/(C+D)
ii) (A+B)*C
iii)D+(E*F)/G