DATA

STRUCTURES
AND
APPLICATIONS
NAGARATHNA C
BCS304
10/04/2024
ASSISTANT PROFESSOR
CSE, SCE
1
 Objectives and Course Outcomes

Course objectives:

CLO 1. To explain fundamentals of data structures and their applications.

CLO 2. To illustrate representation of Different data structures such as Stack, Queues,

Linked Lists, Trees and Graphs.

CLO 3. To Design and Develop Solutions to problems using Linear Data Structures

CLO 4. To discuss applications of Nonlinear Data Structures in problem solving.

CLO 5. To introduce advanced Data structure concepts such as Hashing and Optimal Binary
Search Trees

10/04/2024 Nagarathna C, SCE, Bangalore 2

 Course Outcomes

CO 1. Explain different data structures and their applications.

CO 2. Apply Arrays, Stacks and Queue data structures to solve the given
problems.

CO 3. Use the concept of linked list in problem solving.

CO 4. Develop solutions using trees and graphs to model the real-world

problem.

CO 5. Explain the advanced Data Structures concepts such as Hashing

Techniques and Optimal Binary Search Trees.

10/04/2024 Nagarathna C, SCE, Bangalore 3

 Module-1

MODULE 1

INTRODUCTION TO DATA STRUCTURES: Data Structures, Classifications (Primitive

& Non-Primitive), Data structure Operations Review of pointers and dynamic Memory
Allocation

ARRAYS and STRUCTURES: Arrays, Dynamic Allocated Arrays, Structures and Unions,
Polynomials, Sparse Matrices, representation of Multidimensional Arrays, Strings
STACKS: Stacks, Stacks Using Dynamic Arrays, Evaluation and conversion of Expressions

10/04/2024 Nagarathna C, SCE, Bangalore 4

 INTRODUCTION TO DATA STRUCTURES

Data: Collection of raw facts.

Data structure is representation of the logical relationship

existing between individual elements of data.

Data structure is a specialized format for organizing and

storing data in memory that considers not only the elements
stored but also their relationship to each other.

10/04/2024 Nagarathna C, SCE, Bangalore 5

 INTRODUCTION TO DATA STRUCTURES

The choice of a particular data model depends on the two

considerations:

1. It must be rich enough in structure to mirror the actual

relationships of the data in the real world.

2. The structure should be simple enough that one can

effectively process the data whenever necessary.

10/04/2024 Nagarathna C, SCE, Bangalore 6

 INTRODUCTION TO DATA STRUCTURES

• Data structure affects the design of both structural & functional aspects of a
program.

Program=algorithm + Data Structure

• Algorithm is a step by step procedure to solve a particular function.

algorithm is a set of instruction written to carry out certain tasks & the data
structure is the way of organizing the data with their logical relationship
retained.
• To develop a program of an algorithm, we should select an appropriate data
structure for that algorithm.
• Therefore algorithm and its associated data structures from a program.

10/04/2024 Nagarathna C, SCE, Bangalore 7

 BASIC TERMINOLOGY

Elementary Data Organization

Data: Data are simply values or sets of values.

Data items: Data items refers to a single unit of values

Entity: An entity is something that has certain attributes or properties which may be

Field: is a single elementary unit of information representing an attribute of an entity.

Record: is the collection of field values of a given entity.

assigned values.

File: is the collection of records of the entities in a given entity set.

10/04/2024 Nagarathna C, SCE, Bangalore 8

 CLASSIFICATION OF DATA STRUCTURE

Data structure are normally divided into two broad categories:

• Primitive Data Structure

• Non-Primitive Data Structure

10/04/2024 Nagarathna C, SCE, Bangalore 9

 CLASSIFICATION OF DATA STRUCTURE

10/04/2024 Nagarathna C, SCE, Bangalore 10

 CLASSIFICATION OF DATA STRUCTURE

10/04/2024 Nagarathna C, SCE, Bangalore 11

 CLASSIFICATION OF DATA STRUCTURE: Primitive DS

• There are basic structures and directly operated upon

by the machine instructions.

• In general, there are different representation on

different computers.

• Integer, Floating-point number, Character constants,

string constants, pointers etc, fall in this category.

10/04/2024 Nagarathna C, SCE, Bangalore 12

 CLASSIFICATION OF DATA STRUCTURE: Non Primitive DS

• There are more sophisticated data structures.

• These are derived from the primitive data structures.
• The non-primitive data structures emphasize on structuring of a group
of homogeneous (same type) or heterogeneous (different type) data
items.
• Lists, Stack, Queue, Tree, Graph are example of non-primitive data
structures.
• The design of an efficient data structure must take operations to be
performed on the data structure.

10/04/2024 Nagarathna C, SCE, Bangalore 13

 Linear Data Structure:

A data structure is said to be linear if its elements form a sequence or a linear list.
There are basically two ways of representing such linear structure in memory.

1. One way is to have the linear relationships between the elements represented by
means of sequential memory location. These linear structures are called arrays.

2. The other way is to have the linear relationship between the elements represented
by means of pointers or links. These linear structures are called linked lists.

The common examples of linear data structure are Arrays, Queues, Stacks, Linked
lists

10/04/2024 Nagarathna C, SCE, Bangalore 14

 Non-Linear Data Structure:

• A data structure is said to be non-linear if the data are not arranged in

sequence or a linear.

• The insertion and deletion of data is not possible in linear fashion.

• This structure is mainly used to represent data containing a hierarchical

relationship between elements.

• Trees and graphs are the examples of non-linear datastructure.

10/04/2024 Nagarathna C, SCE, Bangalore 15

 DIFFERENT BETWEEN THEM

• A primitive data structure is generally a basic structure

that is usually built into the language, such as an
integer, a float.

• A non-primitive data structure is built out of primitive

data structures linked together in meaningful ways,
such as a or a linked-list, binary search tree, AVL
Tree, graph etc.

10/04/2024 Nagarathna C, SCE, Bangalore 16

 CLASSIFICATION OF DATA STRUCTURE: NON PRMITIVE DS

The most commonly used operation on data structure are

broadly categorized into following types:

• Create
• Selection
• Updating
• Searching
• Sorting
• Merging
• Destroy or Delete

10/04/2024 Nagarathna C, SCE, Bangalore 17

 REVIEW OF POINTERS AND DYNAMIC MEMORY ALLOCATION

Pointer: A pointer is a special variable which contains address of a

memory location. Using this pointer, the data can be accessed.

10/04/2024 Nagarathna C, SCE, Bangalore 18

 REVIEW OF POINTERS AND DYNAMIC MEMORY ALLOCATION

General form of pointer declaration is –

type* name;

where type represent the type to which pointer thinks it is pointing to.

Pointers to machine defined as well as user-defined types can be made Pointer

Intialization:

variable_type *pointer_name = 0;

or variable_type *pointer_name = NULL;

char *pointer_name = "string value here";

10/04/2024 Nagarathna C, SCE, Bangalore 19

 DYNAMIC MEMORY ALLOCATION

This is process of allocating memory-space during execution-time (or run-

time).

• This is used if there is an unpredictable storage requirement.

• Memory-allocation is done on a heap.

• Memory management functions include:

→ malloc (memory allocate)

→ calloc (contiguous memory allocate)

→ realloc (resize memory)

→ free (deallocate memory)

10/04/2024 Nagarathna C, SCE, Bangalore 20

 DYNAMIC MEMORY ALLOCATION

• malloc function is used to allocate required

amount of memory-space during run-time.

• If memory allocation succeeds, then address of

first byte of allocated space is returned. If
memory allocation fails, then NULL is returned.

• free() function is used to deallocate(or free) an

area of memory previously allocated by
malloc() or calloc(). Allocation and deallocation of memory

10/04/2024 Nagarathna C, SCE, Bangalore 21

 DANGLING REFERENCE

Whenever all pointers to a dynamically allocated area of storage are lost, the
storage is lost to the program. This is called a dangling reference.
POINTERS CAN BE DANGEROUS
• Set all pointers to NULL when they are not actually pointing to an
object.
• Use explicit type casts when converting between pointer types.
• Pointers have same size as data type 'int'.

10/04/2024 Nagarathna C, SCE, Bangalore 22

 ALGORITHM SPECIFICATION

An algorithms must satisfy the following criteria:

1. Input: There are zero or more quantities that are externally supplied.
2. Output: At least one quantity is produced.
3. Definiteness: Each instruction is clear and unambiguous
4. Finiteness: If we trace out the instructions of an algorithm, then for all
cases, the algorithm terminates after a finite number of steps.
5. Effectiveness: Every instruction must be basic enough to be carried out, in
principle, by a person using only pencil and paper.

10/04/2024 Nagarathna C, SCE, Bangalore 23

 ALGORITHM SPECIFICATION

Algorithm 1.1: Selection sort algorithm.

Algorithm 1.2: finding the smallest integer.

Algorithm 1.3: Binary search

Algorithm 1.4: Permutations

10/04/2024 Nagarathna C, SCE, Bangalore 24

 RECURSIVE FUNCTIONS

• A function calls itself either directly or indirectly during execution.

• Recursive-algorithms when compared to iterative-algorithms are normally

compact and easy to understand.

Various types of recursion

1) Direct recursion: where a recursive-function invokes itself.

10/04/2024 Nagarathna C, SCE, Bangalore 25

 RECURSIVE FUNCTIONS

2) Indirect recursion: A function which contains a call to another function which in turn calls
another function and so on and eventually calls the first function.

10/04/2024 Nagarathna C, SCE, Bangalore 26

 RECURSIVE FUNCTIONS

10/04/2024 Nagarathna C, SCE, Bangalore 27

 ARRAYS

ARRAYS

 An Array is defined as, an ordered set of similar data items. All the data items of an
array are stored in consecutive memory locations.
 The data items of an array are of same type and each data items can be accessed
using the same name but different index value.

 An array is a set of pairs, such that each index has a value associated with it. It can be
called as corresponding or a mapping

10/04/2024 Nagarathna C, SCE, Bangalore 28

 ARRAYS

10/04/2024 Nagarathna C, SCE, Bangalore 29

 ARRAYS

Example: Program to find sum of n numbers

one-dimensional array
int list[5]; //array of 5 integers

int *plist[5]; //array of 5 pointers to integers

• Address of first element list[0] is called base-address.

• Memory-address of list[i] can be computed by compiler

as

+i*sizeof(int) where =base address

10/04/2024 Nagarathna C, SCE, Bangalore 30

 ARRAYS

Program to print both address of ith element of given array & the value found at that address:

DYNAMICALLY ALLOCATED ARRAYS ONE-DIMENSIONAL ARRAYS

10/04/2024 Nagarathna C, SCE, Bangalore 31

 ARRAYS

TWO DIMENSIONAL ARRAYS

• These are created by using the concept of array of arrays.

• A 2-dimensional array is represented as a 1-dimensional array in which each element

has a pointer to a 1-dimensional array as shown below

int x[5][7]; //we create a 1-dimensional array x whose length is 5;

//each element of x is a 1-dimensional array whose length is 7.

• Address of x[i][j] = x[i]+j*sizeof(int)

10/04/2024 Nagarathna C, SCE, Bangalore 32

 ARRAYS

Prg: Dynamically create a two-dimensional array

CALLOC

• These functions → allocate user-specified amount of memory & → initialize the allocated memory to 0.

• On successful memory-allocation, it returns a pointer to the start of the new block. On failure, it returns the
value NULL.

• To create clean and readable programs, a CALLOC macro can be created

10/04/2024 Nagarathna C, SCE, Bangalore 33

 ARRAYS

REALLOC

• These functions resize memory previously allocated by either malloc or calloc.

For example,

realloc(p,s); //this changes the size of memory-block pointed at by p to s < oldSize,

//the rightmost oldSize-s bytes of old block are freed..

• When s>oldSize, the additional s-oldSize have an unspecified value and when s

• On successful resizing, it returns a pointer to the start of the new block. On failure, it returns the value NULL.

• To create clean and readable programs, the REALLOC macro can be created

10/04/2024 Nagarathna C, SCE, Bangalore 34

 STRUCTURES AND UNIONS

A structure (called a record in many other programming languages) is a collection of data items,
where each item is identified as to its type and name.
struct {
char name[10];
int age;
float salary;

} person;

 Dot operator(.) is used to access a particular member of the structure.

strcpy(person.name,"james") ;
person.age
person.salary = 35000;

10/04/2024 Nagarathna C, SCE, Bangalore 35

 STRUCTURES AND UNIONS

Unions

 This is similar to a structure, but the fields of a union must share their memory
space. This means that only one field of the union is "active" at any given
time.
Self-Referential Structures

• A self-referential structure is one in which one or more of its components is a

pointer to itself.

• These require dynamic storage management routines (malloc & free) to explicitly
obtain and release memory.

10/04/2024 Nagarathna C, SCE, Bangalore 36

 STRUCTURES AND UNIONS

typedef struct list

{
char data;
list *link; // list is a pointer to a list structure
};

10/04/2024 Nagarathna C, SCE, Bangalore 37

 STRUCTURES AND UNIONS

•Consider three structures and values assigned to their respective fields:

item1.link=&item2;
item2.link=&item3;
•We can attach these structures together as follows

List item1,item2,item3;
item1.data='a';
item2.data='b';
item3.data='c';
item1.link=item2.link=item3.link=NULL;

10/04/2024 Nagarathna C, SCE, Bangalore 38

 POLYNOMIALS ABSTRACT DATA TYPE

 A polynomial is a sum of terms, where each term has a form ax e ,

where x=variable, a=coefficient and e=exponent.

 Two example polynomials are:

 The largest (or leading) exponent of a polynomial is called its degree.

 Coefficients that are zero are not displayed.

 The term with exponent equal to zero does not show the variable since x raised to a
power of zero is 1.

10/04/2024 Nagarathna C, SCE, Bangalore 39

 POLYNOMIALS ABSTRACT DATA TYPE

• There are standard mathematical definitions for the sum and product of polynomials.
• Assume that we have two polynomials
• A(x)= ∑ai x i & B(x)= ∑bi x i

10/04/2024 Nagarathna C, SCE, Bangalore 40

 POLYNOMIALS ABSTRACT DATA TYPE

10/04/2024 Nagarathna C, SCE, Bangalore 41

 POLYNOMIAL REPRESENTATION:

• One way to represent polynomials in C is to use typedef to create the type polynomial
as below:
#define MAX-DEGREE 101 /*Max degree of polynomial+1*/
typedef struct
{
int degree;
float coef[MAX-DEGREE];
} polynomial;

• Now if a is a variable and is of type polynomial and n < MAX_DEGREE,

• the polynomial A(x) = Σai xi would be represented as:
a.degree = n
a.coef[i] = an-i , 0 ≤ i ≤ n

10/04/2024 Nagarathna C, SCE, Bangalore 42

 POLYNOMIAL REPRESENTATION:

This representation leads to very simple algorithms for most of the operations, it wastes a lot
of space
To preserve space an alternate representation that uses only one global array, terms to store all
polynomials.
The C declarations needed are:

MAX_TERMS 100 /*size of terms array*/

typedef struct
{
float coef;
int expon;
} polynomial;

polynomial terms[MAX-TERMS];
int avail = 0;

10/04/2024 Nagarathna C, SCE, Bangalore 43

 POLYNOMIAL REPRESENTATION:

Consider the two polynomials

A(x) = 2x1000+ 1
B(x) = x4 + 10x3 + 3x2 + 1

10/04/2024 Nagarathna C, SCE, Bangalore 44

 Course Outcomes

10/04/2024 Nagarathna C, SCE, Bangalore 45

 POLYNOMIAL REPRESENTATION:

void attach(float coefficient, int exponent)

{
if (avail >= MAX-TERMS)
{
fprintf(stderr,"Too many terms in the polynomial\n");
exit(EXIT_FAILURE);
}
terms[avail].coef = coefficient;
terms[avail++].expon = exponent;
}

/* add a new term to the polynomial */

10/04/2024 Nagarathna C, SCE, Bangalore 46

 SPARSE MATRICES

• A matrix contains m rows and n columns of elements

• If m equals n, the matrix is square.

10/04/2024 Nagarathna C, SCE, Bangalore 47

 SPARSE MATRICES

What is Sparse Matrix?

A matrix which contains many zero entries or very few non-zero entries is called as
Sparse matrix.
Sparse Matrix Representation
• An element within a matrix can characterize by using the triple This means that, an
array of triples is used to represent a sparse matrix.

• Organize the triples so that the row indices are in ascending order.

• The operations should terminate, so we must know the number of rows and columns,
and the number of nonzero elements in the matrix.

10/04/2024 Nagarathna C, SCE, Bangalore 48

 SPARSE MATRICES

SparseMatrix Create(maxRow, maxCol) ::=

#define MAX_TERMS 101 /* maximum number of terms +1*/

typedef struct
{
int col;
int row;
int value;
} term;

term a[MAX_TERMS];

10/04/2024 Nagarathna C, SCE, Bangalore 49

 SPARSE MATRICES

• The representation of matrix in the array “a”

a[0].row contains the number of rows, a[0].col
contains the number of columns and a[0].value
contains the total number of nonzero entries.

• Positions 1 through 8 store the triples representing

the nonzero entries.

• The row index is in the field row, the column

index is in the field col, and the value is in the
field value. The triples are ordered by row and
within rows by columns.
10/04/2024 Nagarathna C, SCE, Bangalore 50
 TRANSPOSING A MATRIX

• To transpose a matrix, interchange the rows and columns.

• This means that each element a[i][j] in the original matrix becomes
element a[j][i] in the transpose matrix.
• A good algorithm for transposing a matrix:
for each row i
take element and store it as
element<i,j,value> of the transpose;
• If we process the original matrix by the row indices it is difficult to
know exactly where to place element <i,j,value> in the transpose
matrix until we processed all the elements that precede it.

10/04/2024 Nagarathna C, SCE, Bangalore 51

 TRANSPOSING A MATRIX

• This can be avoided by using the column indices to determine the

placement of elements in the transpose matrix.
• for all elements in column j
place element <i,j,value> in
element <j,i,value>

10/04/2024 Nagarathna C, SCE, Bangalore 52

 TRANSPOSING A MATRIX

The columns within each row of the transpose matrix will be arranged in ascending order.

10/04/2024 Nagarathna C, SCE, Bangalore 53

 STRING

• Each programming languages contains a character set that is used to communicate

with the computer.
• The character set include the following:
• Alphabet: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Digits: 0 1 2 3 4 5 6 7 8 9
• Special characters: + - / * ( ) , . $ = ‘ _ (Blank space)
• String: A finite sequence S of zero or more Characters is called string.
• Length: The number of characters in a string is called length of string.
• Empty or Null String: The string with zero characters.

10/04/2024 Nagarathna C, SCE, Bangalore 54

 STRING

• Concatenation:
• Let S1 and S2 be the strings.The string consisting of the characters
of S1 followed by the character S2 is called Concatenation of S1
and S2.
• Ex: ‘THE’ // ‘END’ = ‘THEEND’ ‘THE’ // ‘ ’ // ‘END’ = ‘THE END’

• Substring: A string Y is called substring of a string S if there exist

string X and Z such that S = X // Y // Z If X is an empty string, then Y
is called an Initial substring of S, and Z is an empty string then Y is
called a terminal substring of S.
• Ex: ‘BE OR NOT’ is a substring of ‘TO BE OR NOT TO BE’
‘THE’ is an initial substring of ‘THE END’

10/04/2024 Nagarathna C, SCE, Bangalore 55

 STRING

Declaration 1:
#define MAX_SIZE 100 /* maximum size of string */
char s[MAX_SIZE] = {“dog”};
char t[MAX_SIZE] = {“house”};

10/04/2024 Nagarathna C, SCE, Bangalore 56

 STRING

Declaration 2:
char s[ ] = {“dog”};
char t[ ] = {“house”};

Using these declarations, the C compiler will allocate just enough space
to hold each word including the null character.

10/04/2024 Nagarathna C, SCE, Bangalore 57

 STRING

structure String is objects: a finite set of zero or more characters.

functions: for all s, t ꞒString, i, j, m Ꞓ non-negative integers

• String Null(m) = return a string whose maximum length is m characters, but is initially
set to NULL We write NULL “ ”

• Integer Compare(s,t)= if s equals t

return 0
else if s precedes t
return -1
else
return +1

10/04/2024 Nagarathna C, SCE, Bangalore 58

 STRING

• Boolean IsNull(s) = if (Compare(s, NULL))

return FALSE
else
return TRUE
• Integer Length(s) = if (Compare(s, NULL))
return the number of characters in s
else
return 0.
• String Concat(s, t) = if (Compare(s, NULL))
return a string whose elements are those of s
followed by those of t
else
return s.

10/04/2024 Nagarathna C, SCE, Bangalore 59

 STRING

10/04/2024 Nagarathna C, SCE, Bangalore 60

 STRING

Assume that we have two strings, say string i and string 2, and that we want to
insert string 2 into string 1 starting at the ith position of string 1.

10/04/2024 Nagarathna C, SCE, Bangalore 61

 STRING

10/04/2024 Nagarathna C, SCE, Bangalore 62

 STRING

Assume that we have two strings, string and pat, where pat is a pattern to be searched for in
string. The easiest way to determine if pat is in string is to use the built-in function strstr. If
we have the following declarations:

10/04/2024 Nagarathna C, SCE, Bangalore 64

 Course Outcomes

10/04/2024 Nagarathna C, SCE, Bangalore 65

 STRING: Pattern matching by checking end indices first

10/04/2024 Nagarathna C, SCE, Bangalore 66

 STRING

10/04/2024 Nagarathna C, SCE, Bangalore 67

 STRING: Knuth, Morris, Pratt pattern matching algorithm

10/04/2024 Nagarathna C, SCE, Bangalore 68

 THE STACK ABSTRACT DATA TYPE

• This is an ordered-list in which insertions(called push) and deletions(called pop) are

made at one end called the top

• Since last element inserted into a stack is first element removed, a stack is also known
as a LIFO list(Last In First Out).

• When an element is inserted in a stack, the concept is called push, and when an
element is removed from the stack, the concept is called pop.

• Trying to pop out an empty stack is called underflow and trying to push an element in
a full stack is called overflow.

10/04/2024 Nagarathna C, SCE, Bangalore 69

 THE STACK ABSTRACT DATA TYPE

10/04/2024 Nagarathna C, SCE, Bangalore 70

 SYSTEM STACK

A stack used by a program at run-time to process function-calls is called system-stack.

• When functions are invoked, programs

→ create a stack-frame (or activation-record) &

→ place the stack-frame on top of system-stack

• Initially, stack-frame for invoked-function contains only

→ pointer to previous stack-frame &

→ return-address

• A new stack-frame is then

→ created for the invoked-function &

→ placed on top of the system-stack

10/04/2024 Nagarathna C, SCE, Bangalore 71
 SYSTEM STACK

10/04/2024 Nagarathna C, SCE, Bangalore 72

10/04/2024 Nagarathna C, SCE, Bangalore 73
 ARRAY REPRESENTATION OF STACKS

•Stacks may be represented in the computer in various ways such as one-way linked
list (Singly linked list) or linear array.
•Stacks are maintained by the two variables such as TOP and MAX_STACK_SIZE.
•TOP which contains the location of the top element in the stack. If TOP= -1, then it
indicates stack is empty.
•MAX_STACK_SIZE which gives maximum number of elements that can be stored
in stack.
Stack can represented using linear array as shown below

10/04/2024 Nagarathna C, SCE, Bangalore 74

 THE STACK ABSTRACT DATA TYPE

Main stack operations

– Push (int data): Inserts data onto stack.

– int Pop(): Removes and returns the last inserted element from the stack.

• Auxiliary stack operations

– int Top(): Returns the last inserted element without removing it.

– int Size(): Returns the number of elements stored in the stack.

– int IsEmptyStack(): Indicates whether any elements are stored in the stack or not.

– int IsFullStack(): Indicates whether the stack is full or not.

10/04/2024 Nagarathna C, SCE, Bangalore 75

 THE STACK ABSTRACT DATA TYPE

10/04/2024 Nagarathna C, SCE, Bangalore 76

 Add an item to a stack

10/04/2024 Nagarathna C, SCE, Bangalore 77

 Delete an item in a stack

10/04/2024 Nagarathna C, SCE, Bangalore 78

 STACK USING DYNAMIC ARRAYS

Stack CreateS(max-stack-size') ::=

#define MAX—STACK—SIZE 100 /*maximum stack size */
typedef struct
{
int key;
/* other fields */
} element;

element stack[MAX—STACK—SIZE];
int top - -1;
Boolean IsEmpty(Stack) ::= top <0;
Boolean IsFulI(Stack) ::= top >= MAX-STACK-SIZE-1;

10/04/2024 Nagarathna C, SCE, Bangalore 79

 STACK USING DYNAMIC ARRAYS

STACK APPLICATIONS: POLISH NOTATION

Expressions: It is sequence of operators and operands that reduces to a single value after evaluation is
called an expression.
X=a/b–c+d*e–a*c

10/04/2024 Nagarathna C, SCE, Bangalore 80

 STACK USING DYNAMIC ARRAYS

 Infix Expression: In this expression, the binary operator is placed in-between the operand.
The expression can be parenthesized or un- parenthesized.
Example: A + B
Here, A & B are operands and + is operand
 Prefix or Polish Expression: In this expression, the operator appears before its operand.

Example: + A B
Here, A & B are operands and + is operand
 Postfix or Reverse Polish Expression: In this expression, the operator appears after its
operand.

Example: A B +
Here, A & B are operands and + is operand

10/04/2024 Nagarathna C, SCE, Bangalore 81

 STACK USING DYNAMIC ARRAYS

10/04/2024 Nagarathna C, SCE, Bangalore 82

 STACK USING DYNAMIC ARRAYS: INFIX TO POSTFIX CONVERSION

An algorithm to convert infix to a postfix expression as follows:

1. Fully parenthesize the expression.

2. Move all binary operators so that they replace their corresponding right
Parentheses.

3. Delete all parentheses.

10/04/2024 Nagarathna C, SCE, Bangalore 83

 STACK USING DYNAMIC ARRAYS

Function to convert from infix to postfix

10/04/2024 Nagarathna C, SCE, Bangalore 84

 STACK USING DYNAMIC ARRAYS

10/04/2024 Nagarathna C, SCE, Bangalore 85

 STACK USING DYNAMIC ARRAYS

The expression a*(b +c)*d which results abc +*d* in postfix

Function to convert from infix to postfix

10/04/2024 Nagarathna C, SCE, Bangalore 86