In-Pre-Post Fix Expressions

Definition
• A tree t is a finite nonempty set of elements.

• One of these elements is called the root.
• The remaining elements, if any, are
partitioned into trees, which are called the
subtrees of t.
Binary Tree
• Finite (possibly empty) collection of elements.

• A nonempty binary tree has a root element.
• The remaining elements (if any) are partitioned
into two binary trees.
• These are called the left and right subtrees of
the binary tree.
Differences Between A Tree & A Binary Tree
• No node in a binary tree may have a degree

more than 2, whereas there is no limit on
the degree of a node in a tree.
• A binary tree may be empty; a tree cannot
be empty.
Differences Between A Tree & A Binary Tree
• The subtrees of a binary tree are ordered;

those of a tree are not ordered.
a a
b b
• Are different when viewed as binary trees.

• Are the same when viewed as trees.
Arithmetic Expressions
• (a + b) * (c + d) + e – f/g*h + 3.25
• Expressions comprise three kinds of entities.
 Operators (+, -, /, *).
 Operands (a, b, c, d, e, f, g, h, 3.25, (a + b), (c + d),
etc.).
 Delimiters ((, )).
Operator Degree
• Number of operands that the operator requires.

• Binary operator requires two operands.
 a+b
 c/d
 e-f
• Unary operator requires one operand.
 +g
 -h
Infix Form
• Normal way to write an expression.

• Binary operators come in between their left and
right operands.
 a*b
 a+b*c
 a*b/c
 (a + b) * (c + d) + e – f/g*h + 3.25
Operator Priorities
• How do you figure out the operands of an

operator?
 a+b*c
 a*b+c/d
• This is done by assigning operator priorities.
 priority(*) = priority(/) > priority(+) = priority(-)
• When an operand lies between two operators,
the operand associates with the operator that
has higher priority.
Tie Breaker
• When an operand lies between two operators

that have the same priority, the operand
associates with the operator on the left.
 a+b-c
 a*b/c/d
Delimiters
• Subexpression within delimiters is treated

as a single operand, independent from the
remainder of the expression.
 (a + b) * (c – d) / (e – f)
Infix Expression Is Hard To Parse
• Need operator priorities, tie breaker, and

delimiters.
• This makes computer evaluation more
difficult than is necessary.
• Postfix and prefix expression forms do not
rely on operator priorities, a tie breaker, or
delimiters.
• So it is easier for a computer to evaluate
expressions that are in these forms.
Postfix Form
• The postfix form of a variable or constant is
the same as its infix form.
 a, b, 3.25
• The relative order of operands is the same
in infix and postfix forms.
• Operators come immediately after the
postfix form of their operands.
 Infix = a + b
 Postfix = ab+
Postfix Examples
• Infix = a + b * c
 Postfix = a b c * +
• Infix = a * b + c
 Postfix = a b * c +
• Infix = (a + b) * (c – d) / (e + f)
 Postfix = a b + c d - * e f + /
Unary Operators
• Replace with new symbols.

 + a => a @
 + a + b => a @ b +
 - a => a ?
 - a-b => a ? b -
Operators Priorities(high to low)
Operator Priority
Unary minus,!(logical not) 1
^ or $ (exponent) 2
*, / , % 3
+, - 4
<,<=,>=,> 5
==,!= 6
&& 7
|| 8
INFIX to POSTFIX conversion
1. Fully Paranthesize the expression according
to the order of precedence of operators
2. Move all the operators so that they replace
the corresponding right parantheces
3. Replace unary operator with any symbol
@,? etc. to differentiate it from binary
operators
4. Delete all the parantheses
Example
A/B-C+D*E-A*C
•Fully Paranthecize the expression
In order of precedence of operators
((((A/B)-C)+(D*E))-
(A*C))
((((AB/C-(DE*+(AC*-
Post fix: AB/C-DE*+AC*-
Example
• Move Operators
replacing the
corresponding right
Parantheces
((((AB/C-(DE*(AC*-
•Remove all parantheses
• Post Fix : AB/C-DE*AC*-+
INFIX to PREFIX conversion
1. Fully Paranthecize the expression
according to the order of precedence of
operators
2. Move all the operators so that they replace
the corresponding left parantheses
3. Replace unary operator with any symbol
@,? etc. to differentiate it from binary
operators
4. Delete all the parantheces
Example
A/B-C+D*E-A*C
•Fully Paranthecize the expression
In order of precedence of operators
((((A/B)-C)+(D*E))-(A*C))
-+-/ABC)*DE))*AC))
PREFIX: -
+-/ABC*DE*AC
Example
• Move Operators
replacing the
crresponding left
Parantheces
-+-/AB)C)*DE))*AC))
•Remove all Parantheses
Pre Fix expression: +-/ABC-*DE*AC
Examples
1. A*B*C
2. -A+B-C+D
3. A*-B+C
4. (A+B)*D+E/(F+A*D)+C
5. A&&B||C||!(E>F)
6. !(A&&!((B<C)||(C>D)))||(C<E)
Steps for Converting infix expression to
postfix form
Assume array ‘a’ contains the infix
expression and array ‘b’ is for the postfix
expression and initially stack is empty
•Scan the infix array ‘a’ , for each char a[i]
•If a[i] is ‘(‘ push it on to the stack
•If a[i] is operand , write it into b[j]
•If a[i] is operator , compare its priority with
the priority of operator on stack top.
oIf priority of a[i] is greater push a[i] on to
the stack
postfix form…
o Otherwise delete each operator from the stack and
write in b[j] until we get an operator whose
priority is less than or equal to that of a[i],
then Push a[i] onto stack
• If a[i] is ‘)’ delete each operator from stack and
write in b[j] until we encounter a
‘(‘ on stack top
Delete ‘(‘ from stack but don’t write in b[j]
• If a[i]=‘\0’(end of array ‘a’) then delete each
operator fromstack and write in b[j] until stack
becomes empty
• Append a ‘\0’ at end of array b
prefix form
Assume array ‘a’ contains the REVERSED
infix expression and array ‘b’ is for the prefix
expression and initially stack is empty
•Scan the infix array ‘a’ , for each char a[i]
•If a[i] is ‘)‘ push it on to the stack
•If a[i] is operand , write it into b[j]
•If a[i] is operator , compare its priority with
the priority of operator on stack top.
oIf priority of a[i] is greater or equal to the
operator on the top of the stack push a[i] on to
the stack
prefix form…
o Otherwise delete each operator from the
stack and write in b[j] until we get an
operator on stack top whose priority is less
than that of a[i]
• If a[i] is ‘(’ delete each operator from stack
and write in b[j] until we encounter a
‘)‘ on stack top
Delete ‘)‘ from stack but don’t write in b[j]
• If a[i]=‘\0’(end of array ‘a’) then delete
each operator fromstack and write in b[j]
until stack becomes empty
prefix form…
• Append a ‘\0’ at end of array b
• Finally REVERSE array ‘b’ to get the
prefix expression
Example: Left as Exercise

Postfix Evaluation
• Scan postfix expression from left to right

pushing operands on to a stack.
• When an operator is encountered, pop as
many operands as this operator needs;
evaluate the operator; push the result on to
the stack.
• This works because, in postfix, operators
come immediately after their operands.
Postfix Evaluation
• (a + b) * (c – d) / (e + f)
• ab+cd-*ef+/
• ab+cd-*ef+/
• ab+cd-*ef+/
• ab+cd-*ef+/
b
a
stack
Postfix Evaluation
• (a + b) * (c – d) / (e + f)
• ab+cd-*ef+/
• ab+cd-*ef+/
• ab+cd-*ef+/
• ab+cd-*ef+/ d
• ab+cd-*ef+/ c
• ab+cd-*ef+/ (a + b)
• ab+cd-*ef+/ stack
Postfix Evaluation
• (a + b) * (c – d) / (e + f)
• ab+cd-*ef+/
• ab+cd-*ef+/
(c – d)
(a + b)
stack
Postfix Evaluation
• (a + b) * (c – d) / (e + f)
• ab+cd-*ef+/
• ab+cd-*ef+/
• ab+cd-*ef+/
• ab+cd-*ef+/ f
• ab+cd-*ef+/ e
(a + b)*(c – d)
stack
Postfix Evaluation
• (a + b) * (c – d) / (e + f)
• ab+cd-*ef+/
• ab+cd-*ef+/
• ab+cd-*ef+/
• ab+cd-*ef+/
• ab+cd-*ef+/ (e + f)
• ab+cd-*ef+/ (a + b)*(c – d)
stack
Prefix Form
• The prefix form of a variable or constant is
the same as its infix form.
 a, b, 3.25
• The relative order of operands is the same in
infix and prefix forms.
• Operators come immediately before the
prefix form of their operands.
 Infix = a + b
 Postfix = ab+
 Prefix = +ab

In-Pre-Post Fix Expressions

Uploaded by

Copyright:

Available Formats

In-Pre-Post Fix Expressions

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

In-Pre-Post Fix Expressions

Uploaded by

Copyright:

Available Formats

Definition

• A tree t is a finite nonempty set of elements.

• Finite (possibly empty) collection of elements.

• No node in a binary tree may have a degree

• The subtrees of a binary tree are ordered;

• Are different when viewed as binary trees.

• Number of operands that the operator requires.

• Normal way to write an expression.

• How do you figure out the operands of an

• When an operand lies between two operators

• Subexpression within delimiters is treated

• Need operator priorities, tie breaker, and

• Replace with new symbols.

Example: Left as Exercise

• Scan postfix expression from left to right

You might also like