Polish Notation for Data Structure in C Language
Normally in an arithmetic expression the operator is placed in between the operands or expression. Such an expression is called as INFIX expression. In an INFIX expression according to the need the parentheses are placed according to the need. The parentheses are placed to find the value overhauling the operator hierarchy. Considering the operator hierarchy it is not possible to find the value of INFIX expression in one scan. Several scans are needed if an INFIX expression contains different hierarchy operators.
Following is a simple list of binary operators with hierarchy. Binary operators are those which involve two operands or expressions to frame an expression.
Level 1 ! Exponent (to find power, A ! B, A to the power B)
Level 2 */ Multiplication, Division, same hierarchy
Level 3 +-Addition, Subtraction, same hierarchy
In an INFIX expression, if the different operators are used to frame the expression ,then the expressions involving highest hierarchy are evaluated first scanning from left to right. The resulting expression is again evaluated for the next expression or value. If any parentheses are there they are removed by finding the value within the parentheses. So an expression is evaluated after multiple passes.
For example consider an expression:
6 * 3 ! 2 / (3+6)
After first pass 6 * 3 ! 2 / 9
After second pass 6 * 9 / 9
After third pass 6 Final value
In computer it consumes much time. In order to overcome these difficulties French mathematician Polish has given different ways of writing an INFIX expression. He has given parentheses free notation called Polish notation in which the operator is placed before the operands, such notation is called as ‘Polish Notation’. As the operators are placed before the operands the resulting expression is called as PREFIX expression.
If the operators are placed after the operands the resulting notation is called as RPN, Reverse Polish Notation and the resulting expression is called as POSTFIX expression.
INFIX - Operators in between operands / sub expressions
PREFIX -Operators before operands / sub expressions
POSTFIX -Operators after operands / sub expression