Scribd
Upload
54 views

Infix To Postfix: CSC-114 Data Structure and Algorithms

The document discusses converting infix notation to postfix notation. It explains that postfix notation rearranges the order of operators and operands in an expression according to precedence rules while keeping the relative order of operands. An algorithm is presented that uses a stack to convert an infix expression to postfix by pushing and popping operators from the stack. Examples are provided to demonstrate applying the algorithm to fully parenthesized infix expressions and converting them to equivalent postfix expressions.

Uploaded by

Umair Tariq
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
54 views

Infix To Postfix: CSC-114 Data Structure and Algorithms

The document discusses converting infix notation to postfix notation. It explains that postfix notation rearranges the order of operators and operands in an expression according to precedence rules while keeping the relative order of operands. An algorithm is presented that uses a stack to convert an infix expression to postfix by pushing and popping operators from the stack. Examples are provided to demonstrate applying the algorithm to fully parenthesized infix expressions and converting them to equivalent postfix expressions.

Uploaded by

Umair Tariq
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
You are on page 1/ 50

Edited with the trial version of

Foxit Advanced PDF Editor


To remove this notice, visit:
www.foxitsoftware.com/shopping

Infix to Postfix

CSC-114 Data Structure and Algorithms

Slides credit: Ms. Saba Anwar


Infix to Postfix Conversion
 Infix Expression: a + b * c  Infix Expression: (a +b) * c
 Precedence of * is higher than +, So  Convert addition
convert the multiplication ( a b +)* c
a + (b c * )  Convert the multiplication
 Convert the addition (a b + c * )
a (b c * ) +  Remove parenthesis
 Remove parenthesis  Posfix Expression: a b + c*
 Postfix Expression: a b c * +
Keep in Mind:
1. Relative order of variables is not changed
2. No parenthesis in postfix/prefix
3. Operators are arranged according to precedence
4. If same precedence operators, then evaluate left to right
2 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015
More Examples
 Infix Postfix
 (a + b) * (c – d) ab+cd-*
 a – b / (c + d * e) abcde*+/-
 ((a + b) * c – (d – e))/(f + g) ab+c*de--fg+/
 (300+23)*(43-21)/(84+7) 300 23 + 43 21 -* 84 7 + /

 Can we use stack to convert an infix expression into post fix expression

3 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Algorithm
 Input: a infix expression string
 Output: a postfix expression string of given input Keep in Mind:
 Steps: 1. Relative order of variables is
1. Let P is string, and S is character stack not changed
2. While(input expression has more characters)
2. No parenthesis in postfix
3. Read the next character
4. If character is an operand 3. Operators are arranged
5. append it to P according to precedence
6. Else If character is an operator 4. If same precedence
7. pop S, until top of the S has an element of lower precedence
operators, then evaluate left
8. append popped character to P
9. Then push the character to S
to right
10. Else If character is “(“
11. Push it to S
12. Else If character is ‘)’
13. pop S until we find the matching ‘(’
14. append popped character to P
15. pop “(“ // ‘(’ has the lowest precedence when in the stack but has the highest precedence when in the input
16. End If
17. End While
18. Pop until the stack is empty and append popped character to P

4 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-1
3+4*5/6
 Stack:  Output:

5 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-1
3+4*5/6
 Stack:  Output: 3

6 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-1
3+4*5/6
 Stack:  Output: 3

7 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-1
3+4*5/6
 Stack:  Output: 3 4

8 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-1
3+4*5/6
 Stack:  Output: 3 4

*
+

9 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-1
3+4*5/6
 Stack:  Output: 3 4 5

*
+

10 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-1
3+4*5/6
 Stack:  Output: 3 4 5 *

11 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-1
3+4*5/6
 Stack:  Output: 3 4 5 *

/
+

12 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-1
3+4*5/6
 Stack:  Output: 3 4 5 * 6

/
+

13 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-1
3+4*5/6
 Stack:  Output: 3 4 5 * 6 / +

14 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output:

/
+

15 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output:

16 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output:

17 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output:

(
(

18 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output:

(
(
(

19 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output: 1

(
(
(

20 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output: 1

+
(
(
(

21 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output: 1 2

+
(
(
(

22 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output: 1 2 +

(
(

23 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output: 1 2 +

*
(
(

24 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output: 1 2 + 3

*
(
(

25 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output: 1 2 + 3 *

26 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output: 1 2 + 3 *

27 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix Conversion
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output: 1 2 + 3 *

+
(

28 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output: 1 2 + 3 *

+
(

29 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output: 1 2 + 3 * +

30 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output: 1 2 + 3 * +

31 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output: 1 2 + 3 * +

32 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output: 1 2 + 3 * +

(
/

33 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output: 1 2 + 3 * + 2

(
/

34 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output: 1 2 + 3 * + 2

+
(
/

35 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output: 1 2 + 3 * + 2 3

+
(
/

36 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output: 1 2 + 3 * + 2 3 +

37 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output: 1 2 + 3 * + 2 3 +

38 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-2
(((1 + 2) * 3) + 6) / (2 + 3)
 Stack:  Output: 1 2 + 3 * + 2 3 + /

39 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-3
3+4-1*5/6
 Stack:  Output:3

40 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-3
3+4-1*5/6
 Stack:  Output:3

41 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-3
3+4-1*5/6
 Stack:  Output:3

42 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-3
3+4-1*5/6
 Stack:  Output:3 4

43 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-3
3+4-1*5/6
 Stack:  Output:3 4 +

44 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-3
3+4-1*5/6
 Stack:  Output:3 4 + 1

45 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-3
3+4-1*5/6
 Stack:  Output:3 4 + 1

*
-

46 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-3
3+4-1*5/6
 Stack:  Output:3 4 + 1 5

*
-

47 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-3
3+4-1*5/6
 Stack:  Output:3 4 + 1 5 *

/
-

48 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-3
3+4-1*5/6
 Stack:  Output:3 4 + 1 5 * 6

/
-

49 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015


Infix to Postfix: Example-3
3+4-1*5/6
 Stack:  Output:3 4 + 1 5 * 6 / -

50 Saba Anwar, Computer Science Department- CIIT Lahore 19/10/2015

You might also like