Scribd
Upload
8 views3 pages

Prefix Infix Postfix Notes

The document explains Infix, Prefix, and Postfix notations, detailing their structures and evaluation orders with examples and expression trees. It also provides conversion algorithms for transforming Infix expressions into Postfix and Prefix notations. Additionally, it summarizes expression tree traversal types associated with each notation.

Uploaded by

Rajini Gadlay
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views3 pages

Prefix Infix Postfix Notes

The document explains Infix, Prefix, and Postfix notations, detailing their structures and evaluation orders with examples and expression trees. It also provides conversion algorithms for transforming Infix expressions into Postfix and Prefix notations. Additionally, it summarizes expression tree traversal types associated with each notation.

Uploaded by

Rajini Gadlay
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Prefix, Infix, and Postfix Notations (Diagram-Based

Explanation)

1. Infix Notation
In Infix notation, the operator is written between operands.

Example:
A + B

Diagram:
Operand Operator Operand
A + B

Example 2:
A + B * C

Expression Tree:
+
/ \
A *
/ \
B C

Evaluation Order:
Step 1: B * C
Step 2: A + Result

Problem: Computers must follow operator precedence and parentheses.

2. Prefix Notation (Polish Notation)


In Prefix notation, the operator comes before operands.

General Form:
Operator Operand Operand

Example:
Infix: A + B
Prefix: + A B

Example 2:
Infix: (A + B) * C

Expression Tree:
*
/ \
+ C
/ \
A B

Prefix (Preorder Traversal):


* + A B C

3. Postfix Notation (Reverse Polish Notation)


In Postfix notation, the operator comes after operands.

General Form:
Operand Operand Operator

Example:
Infix: A + B
Postfix: A B +
Example 2:
Infix: (A + B) * C

Expression Tree:
*
/ \
+ C
/ \
A B

Postfix (Postorder Traversal):


A B + C *

Comparison Table

Notation Operator Position Example


Infix Between operands A+B
Prefix Before operands +AB
Postfix After operands AB+

Infix → Postfix Conversion Steps


Algorithm (Stack Method)
1. Scan expression left to right
2. If operand → add to output
3. If operator → push to stack
4. If higher precedence operator → pop stack operator
5. If '(' → push to stack
6. If ')' → pop until '('

Example:
Infix: A + B * C

Scan | Stack | Output


A - A
+ + A
B + AB
* +* AB
C +* ABC

Result Postfix: ABC*+

Infix → Prefix Conversion Steps


Steps:
1. Reverse the infix expression
2. Replace ( with ) and ) with (
3. Convert to postfix
4. Reverse the result to obtain prefix

Example:
Infix: (A + B) * C

Reverse:
C * (B + A)

Postfix:
C B A + *

Prefix:
* + A B C
Expression Tree Traversal Summary
Traversal Types:
Preorder → Root Left Right → Prefix
Inorder → Left Root Right → Infix
Postorder → Left Right Root → Postfix

You might also like