Scribd
Upload
10 views12 pages

DS Lab2

The document provides an overview of infix, postfix, and prefix operators in mathematical expressions. It includes examples of postfix evaluation with and without stacks, as well as the conversion of infix expressions to postfix using stacks. Additionally, it explains the process of converting infix to prefix notation through a series of steps.

Uploaded by

mosalah
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
10 views12 pages

DS Lab2

The document provides an overview of infix, postfix, and prefix operators in mathematical expressions. It includes examples of postfix evaluation with and without stacks, as well as the conversion of infix expressions to postfix using stacks. Additionally, it explains the process of converting infix to prefix notation through a series of steps.

Uploaded by

mosalah
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

THE BRITISH UNIVERSITY IN EGYPT

18CSCI01C
Semester 2

Introduction to Data Structure and


Algorithm Design

LAB 2

1
Infix operator:
It is the normal expression for mathematical operations
X + Y while + is operator and “X”, “Y” are operands.
Postfix operator:
Simply is putting the Operators AFTER Operands
X Y + while + is operator and “X”, “Y” are operands.
Prefix operator:
Simply is putting the Operators BEFORE Operands
+ X Y while + is operator and “X”, “Y” are operands.

1- Postfix Evaluation without stacks


Examples

 45+

Answer: 9

 62/5+

Answer:
35+
8

 4572+-*

Answer:
459-*
4 -4 *
-16.

2
2-Postfix evaluation with stacks

9 – ((3 * 4) + 8) / 4

3
The code of evaluating the postfix through stack:

4
’

5
6
3- Infix to postfix conversion without stack
NOTE:
-Put into your consideration to put the higher mathematical priority first such as “(), *, /” and the lower
priority second such as “+, -“
- (A + B) * C – (D – E) * (F + G)
- (AB+) * C – (D – E) * (F + G)
- (AB+) * C – (DE-) * (F + G)
- (AB+) * C – (DE-) * (F G+)
- (AB+) * C – (DE-) * (F G+)

- AB+ C* – (DE-) * (F G+)

- AB+ C* – DE- F G+*

- AB+ C* DE- F G+*-

7
4- Infix to postfix conversion with stack
((A- (B+C)) * D) * (E+F)
Or
((A- (B+C)) * D) * (E+F))

Scanned Symbol Stack Postfix Expression


( (
( ((
A (( A
- ((- A
( ((-( A
B ((-( AB
+ ((-(+ AB
C ((-(+ ABC
) ((- ABC+
) ( ABC+-
* (* ABC+-
D (* ABC+-D
) ABC+-D*
* * ABC+-D*
( *( ABC+-D*
E *( ABC+-D*E
+ *(+ ABC+-D*E
F *(+ ABC+-D*EF
) * ABC+-D*EF+
END OF CHARACTERS The stack is empty. ABC+-D*EF+*

8
5- Prefix notation.
Simply is putting the Operators BEFORE Operands.
NOTE:
Prefix go through three states:
1- Reverse the infix itself, which means put the right expression left and the left expression right.
2- Performing the postfix operation on the reversed infix.
3- Reverse the postfix expression to get the prefix expression
Example:
(A – B / C) * (A/ K – L)
Step 1:
(L-K/A) * (C/B-A)
Step 2:
Define your parentheses
[(L-K/A)] * [(C/B-A)]
= [(L- (KA /))] * [ (CB/)-A]
= [LKA /-] * [CB / A -]
=LKA/–CB/A–*
Step 3:
= * – A / B C – /A K
How to evaluate pre-fix during the stack according to this expression
+ - 2 7 * 8 / 4 12

9
10
Appndx

11
12

You might also like