PREFIX, POSTFIX, INFIX
NOTATION
INFIX NOTATION
To add A, B, we write
A+B
To multiply A, B, we write
A*B
The operators ('+' and '*') go in between the
operands ('A' and 'B')
This is "Infix" notation.
PREFIX NOTATION
Instead of saying "A plus B", we could say "add
A,B " and write
+AB
"Multiply A,B" would be written
*AB
This is Prefix notation.
POSTFIX NOTATION
Another alternative is to put the operators after
the operands as in
AB+
and
AB*
This is Postfix notation.
The terms infix, prefix, and postfix tell us
whether the operators go between, before, or
after the operands.
Pre A In B Post
PARENTHESES
Evaluate 2+3*5.
+ First:
(2+3)*5 = 5*5 = 25
* First:
2+(3*5) = 2+15 = 17
Infix notation requires Parentheses.
WHAT ABOUT PREFIX NOTATION?
+2*35=
=+2*35
= + 2 15 = 17
*+235=
=*+235
= * 5 5 = 25
No parentheses needed!
POSTFIX NOTATION
235*+=
=235*+
= 2 15 + = 17
23+5*=
=23+5*
= 5 5 * = 25
No parentheses needed here either!
CONCLUSION:
Infix is the only notation that requires
parentheses in order to change the order in which
the operations are done.
FULLY PARENTHESIZED EXPRESSION
A FPE has exactly one set of Parentheses
enclosing each operator and its operands.
Which is fully parenthesized?
(A+B)*C
( ( A + B) * C )
( ( A + B) * ( C ) )
INFIX TO PREFIX CONVERSION
Move each operator to the left of its operands &
remove the parentheses:
( ( A + B) * ( C + D ) )
INFIX TO PREFIX CONVERSION
Move each operator to the left of its operands &
remove the parentheses:
(+A B *(C+D))
INFIX TO PREFIX CONVERSION
Move each operator to the left of its operands &
remove the parentheses:
*+A B (C+D)
INFIX TO PREFIX CONVERSION
Move each operator to the left of its operands &
remove the parentheses:
*+A B +C D
Order of operands does not change!
INFIX TO POSTFIX
(((A+B)*C)-((D+E)/F))
A B+C* D E+F/-
Operand order does not change!
Operators are in order of evaluation!
EXAMPLE: POSTFIX EXPRESSIONS
Postfix
notation is another way of writing
arithmetic expressions.
Inpostfix notation, the operator is written
after the two operands.
infix: 2+5 postfix: 2 5 +
Expressions are evaluated from left to right.
Precedence rules and parentheses are never
needed!!
EXAMPLE: POSTFIX EXPRESSIONS
(CONT.)
CONVERSION OF INFIX TO POSTFIX
Expressions can be represented in prefix, postfix or infix notations.
Conversion from one form of the expression to another form may be
accomplished using a stack.
We do not know what to do if an operator is read as an input character.
By implementing the priority rule for operators, we have a solution to this
problem.
The Priority rule: we should perform comparative priority check if an
operator is read, and then push it. If the stack top contains an operator of
priority higher than or equal to the priority of the input operator, then we
pop it and print it. We keep on performing the priority check until the top
of stack either contains an operator of lower priority or if it does not
contain an operator.
Eg: (A*B)+C
Element Stack Postfix Action
$ $ Work stack
( $ ( Push (
A $ ( A Print A
* $ ( * Push(*)
B $ ( * AB Print B
) $ AB* Pop *,( print *
+ $ + Push +
C $ + AB*C Print C
$ AB*C+ Pop +
EVALUATION OF POSTFIX EXPRESSION
Postfix expression is easily evaluated by the compiler by using stack.
The procedure for the evaluation of postfix expression is given below:
procedure eval(E)
x=getnextchar(E);
case x:
x is an operand: push x into stack S.
x is an operator: pop elements, perform operation and
push result into stack.
x is null: pop stack and print result
end case
End procedure
Eg: AB*C+ A=2, B=3, C=5
Element Stack Action
A Push A
A
B Push B
A B
* 6 Pop A and B, A*B,
push 6
C 6 C Push C
+ 11 Pop C and 6,
C+6, push 11
$
Pop
Result:11
CONVERSION OF INFIX TO POSTFIX
Expressions can be represented in prefix, postfix or infix notations.
Conversion from one form of the expression to another form may be
accomplished using a stack.
We do not know what to do if an operator is read as an input character.
By implementing the priority rule for operators, we have a solution to this
problem.
The Priority rule: we should perform comparative priority check if an
operator is read, and then push it. If the stack top contains an operator of
priority higher than or equal to the priority of the input operator, then we
pop it and print it. We keep on performing the priority check until the top
of stack either contains an operator of lower priority or if it does not
contain an operator.
INFIX TO PREFIX AND POSTFIX USING
STACKS
Infix: (((2 + 7) - ((5 * 13) / 9)) - 19)
Prefix: - - + 27 / * 513 9 19
Postfix: 27+ 513* 9/ - 19-
Infix: (( 4 + ( 10 * 2 ) ) *2)
Prefix: * + 4 * 102 2
Postfix: 4102*+2*
Infix: ( ( ( 6 + 3) + 5 ) + 8 )
Prefix: + + + 63 5 8
Postfix: 63 + 5 + 8 +
INFIX TO PREFIX WITH FPE APPROACH
INFIX TO POSTFIX USING STACKS AND FPE
Class Assignment 2 - Due date 3-4-2023
a*b/c/d
(a*(b / (c / d)))
(a* ((b / c) / d))
((a*b) / (c / d))
((a*(b / c)) / d)
(((a*b) / c) / d)