Scribd
Upload
47 views16 pages

Lec01-Data Structure-Week 4 & 5

Uploaded by

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

Lec01-Data Structure-Week 4 & 5

Uploaded by

bwork4758
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 16

INFIX, PREFIX &

POSTFIX
Instructor: Abid Ali
ARITHMETIC EXPRESSION IN
STACK
 An arithmetic expression is an expression built up of using numbers that
can either be constants or variables, arithmetic operators (such as +, , -, / )
and parentheses.
OR
 An expression is defined as a combination of some operands and
operators.
 For Example
2 + 3
operand operator operand

a + b
operand operator operand
EVALUATING ARITHMETIC
EXPRESSION
 There are 3 different ways to evaluate Arithmetic expression

1. Infix notation
2. Postfix notation
3. Prefix notation
INFIX NOTATION
 In this notation, operators are written in between the operands.
 We write expression in infix notation, e.g. a +b OR 2 + 3 where operators
are used in-between operands.
 It is easy for us humans to read, write, and speak in infix notation but the
same does not go well with computing devices.
 An algorithm to process infix notation could be difficult and costly in terms
of time and space consumption.
 In Infix notation operands does not always has to be constants or variables.
 Operands can be an expression itself.

(a + b) * 3
 Here (a + b) and 3 are operands and * is operator.
 We can also have a further complex expression

(a + b) * (p + q)
 Here (a + b) (p + q) are operands and * is operator.
PREFIX NOTATION
 The arithmetic operator appears directly after the two operands to which it
applies.
 Prefix notation is also known as Polish Notation. In this notation,
operator is prefixed to operands, i.e. operator is written ahead of operands.
 For example, +ab.
 This is equivalent to its infix notation a + b

 In Prefix notation operands does not always has to be constants or


variables.
 Operands can be an expression itself.

*(a + b) 3
 Here (a + b) and 3 are operands and * is operator.
 We can also have a further complex expression

*(a + b) (p + q)
 Here (a + b) (p + q) are operands and * is operator.
POSTFIX NOTATION
 This notation style is known as Reversed Polish Notation.
 In this notation style, the operator is postfixed to the operands i.e., the
operator is written after the operands.
 For example, ab+.
 This is equivalent to its infix notation a + b.

 The expression to multiply two X and Y is written in postfix notation as:


XY*
 In Postfix notation operands does not always has to be constants or variables.
 Operands can be an expression itself.

(a + b) 3 *
 Here (a + b) and 3 are operands and * is operator.
 We can also have a further complex expression

(a + b) (p + q) *
 Here (a + b) (p + q) are operands and * is operator.
CONVERTING INFIX TO
POSTFIX
 Convert (A+B)*C/D to its equivalent Postfix
 To convert infix notation to postfix, we must follow the following steps

 Step 1
 (A+B)*C/D
 Convert (A+B) to postfix first because A+B have high precedence. (It’s a simple
math rule to solve equations which are in brackets first).
 So
 (A+B)*/C will become AB+*C/D. ---------------------Eq 1
 AB+ * /C.
Operand operator operand
 Step 2
 Assume AB+ = x
 Putting value of x in Eq 1 so Eq 1 will become
x * C/D ---------------------Eq 2
 Operand operator operand
 Step 3
 Convert Eq 2 again to Postfix
 x c * /D ---------------------Eq 3
 Step 4
 Assume x c * = y
 So Eq 3 will become
 y/D ---------------------Eq 4
 Step 5
 Putting value of “y” in Eq4
 xc* D/ ---------------------Eq 5
 Step 6
 Putting value of “x” in Eq 5
AB+C* D/
CONVERTING INFIX TO
PRETFIX
 Convert (A+B)*C/D to its equivalent Prefix
 To convert infix notation to prefix, we must follow the following steps

 Step 1
 (A+B)*C/D
 Convert (A+B) to prefix first because A+B have high precedence. (It’s a simple
math rule to solve equations which are in brackets first).
 So
 (A+B)*/C will become +AB*C/D. ---------------------Eq 1
 +AB * /C.
Operand operator operand
 Step 2
 Assume +AB = x
 Putting value of x in Eq 1, so Eq 1 will become
x * C/D ---------------------Eq 2
 Operand operator operand
 Step 3
 Convert Eq 2 again to Prefix
 * x c /D ---------------------Eq 3
 Step 4
 Assume * x c = y
 So Eq 3 will become
 y/D ---------------------Eq 4
 Step 5
 Convert Eq 4 again to Prefix
 /yD ---------------------Eq 5

 Step 6
 Putting value of “y” in Eq5
 /*xc D ---------------------Eq 6
 Step 7
 Putting value of “x” in Eq 6
/*+ABC D
 So the Postfix and Prefix of Infix

(A+B)*C/D
Is
AB+C* D/
and
/*+ABC D
respectively

You might also like