Vision, Mission, PO,CO AND

CO-PO MAPPING
Department of Master of Computer Applications
Bangalore Institute of Technology

Presentation on Awareness of
Outcome Based Education (OBE)
and
National Board of Accreditation(NBA)
 Overview
1. National Board of Accreditation (NBA)
2. Bloom’s Taxonomy of Learning
3. Outcome Based Education (OBE)
4. Vision and Mission of the Institute
5. Vision and Mission of the Department
6. Program Educational Objectives (PEO’s)
7. Program Outcomes (PO’s)
8. Course Learning Objectives (CLO’s)

9.Course Outcomes (CO’s)

3
National Board of Accreditation – Washington
Accord (NBA – WA)

 Washington Accord – (ABET – US) : ABET accreditation

provides assurance that a college or university program
meets the quality standards of the profession for which that
program prepares its graduates.
 Promoting international quality standards for technical
education in India
 Recognition by stakeholders (Students, Faculty, Support
Staff, Industry and Employers, Parents, Government, and
Society)
 Washington accord: India a signatory nation
 Recognition of graduates globally
4
Why is accreditation important?

 Accreditation helps prospective students and their

parents choose quality college programmes
 Accreditation enables employers to recruit graduates they
know are well prepared.
 Accreditation gives colleges and universities a structured
mechanism to assess, evaluate and improve the quality of
their programmes.
 Accreditation benefits society as a whole.

5
Bloom’s Taxonomy of Learning

Teaching with
the Revised Bloom's
Taxonomy

6
Bloom’s Taxonomy of Learning

 Taxonomy = Classification

 Classification of thinking

 Six cognitive levels

of complexity

7
 Original Terms New
Terms

•Creating
• Evaluation
• Synthesis •Evaluating

• Analysis
•Analysing
• Application
•Applying
• Comprehension •Understanding
• Knowledge
•Remembering
8
What Is Outcome Based Education?

 Outcome based education is student centered

instruction that focuses on measuring
student performance i.e. outcomes.
 Outcomes include knowledge skills and
attitudes
 Outcome based accreditation – focus remains
on evaluation of outcomes of the program,
though input and output parameters are also
important
9
What Is Outcome Based Education?

 Students are expected to be able to do more challenging tasks other

than memorize and reproduce what was taught.

 Students should be able to: write project proposals, complete

projects, analyze case studies, give case presentations, show
their abilities to think, question, research, and make decisions
based on the findings.

 Be more creative, able to analyze and synthesize information.

 Able to plan and organize tasks, able to work in a team as a

community or in entrepreneurial service teams to propose solutions
to problems and market their solutions
10
What Is Outcome Based Education?

Starting with a clear picture of what is important for

students to be able to do…

Then organizing the curriculum, delivery and assessment

to make sure learning happens…

In a nutshell, learner-centric approach to education

It’s not what Teachers teach, It’s more of what

students LEARN

NO OBE = NO ACCREDITATION

11
Study Program and Professional:
• Knowledge, skill
Accreditation Program
• Competence
Educational
• Self Development
Objectives
• Responsibility
Curriculu • Ethics
m
Governance
& Financial Faculty

3-5 yrs
Std. Teaching,
Support Learning
Graduates with
ability in:
Facilities
• Specific knowledge
Program
• Design
Outcomes
• Communication
• Teamwork
• Management
• Life long learning
Vision and Mission of the Institute

Vision of the Institute

To establish and develop the Institute as a centre

of higher learning, ever abreast with expanding
horizon of knowledge in the field of engineering
and technology, with entrepreneurial thinking,
leadership excellence for life-long success and
solve societal problem.
13
Vision and Mission of the Institute

Mission of the Institute

 M1. Provide high quality education in the engineering disciplines from
the undergraduate through doctoral levels with creative academic and
professional programs.
 M2. Develop the Institute as a leader in Science, Engineering,
Technology and management, Research and apply knowledge for the
benefit of society.
 M3. Establish mutual beneficial partnerships with industry, alumni,
local, state and central governments by public service assistance and
collaborative research.
 M4. Inculcate personality development through sports, cultural and
extracurricular activities and engage in the social, economic and
professional challenges.
14
Vision, Mission of Department
Vision

• To transform young graduates into skilled

computer professionals to meet Industrial

and Societal needs.

Vision, Mission of Department
Mission
 To enhance the Teaching learning process to meet quality
education in the field of Computer applications

 To impart the knowledge in current technologies to meet

the industrial needs

 To inculcate ethical values and leadership qualities for the

betterment of society
 MCA Department PEOs

• PEO1: To develop quality application software with

innovative ideas to meet the industrial requirements

• PEO2: To imbibe the current technologies and to adopt in

computing profession as per the changing needs

• PEO3: To progress in their career with leadership qualities

and ethical values that enhances self and societal growth
Program Outcomes(POs)
The graduates will have an ability to
PO1: Apply knowledge of computing fundamentals, computing
specialization, mathematics and domain knowledge to provide IT
solutions

PO2: Identify, analyze and solve IT problems using fundamental

principles of mathematics and computing sciences

PO3: Design, Develop and evaluate software solutions to meet

societal and environmental concerns
Program Outcomes(POs)
The graduates will have an ability to
PO4: Conduct investigations of complex problems using research
based knowledge and methods to provide valid conclusions.

PO5: Select and apply appropriate techniques and modern tools

for complex computing activities

PO6: Understand professional ethics, cyber regulations and

responsibilities
Program Outcomes(POs)
The graduates will have an ability to
PO7: Involve in life-long learning for continual development as
an IT professional.

PO8: Apply and demonstrate computing and management

principles to manage projects in multidisciplinary environments
by involving in different roles

PO9: Comprehend& write effective reports and make quality

presentations.
Program Outcomes(POs)
The graduates will have an ability to
PO10: Understand the impact of IT solutions on socio-
environmental issues

PO11: Work collaboratively as a member or leader in

multidisciplinary teams.

PO12: Identify potential business opportunities and innovate to

create value for the society and seize that opportunity
 Syllabus
Data Structures with Algorithms
[As per Choice Based Credit System (CBCS) scheme]
Subject Code: 20MCA11
CIE Marks: 40 SEE Marks: 60 SEE Hours: 03
Course learning objectives:
This course (20MCA11) will enable student to
• Familiarize the knowledge of various types of data structures, operations and
algorithms sorting and searching operations.
• Use the concepts of Stack, Queue, Lists, Trees, Hashing, Searching and
Sorting techniques
• Build solutions for real world problems using concepts of data structures
• Familiarize with different strategies of algorithms.
• Can apply different strategies to solve applications.
 Syllabus
MODULE 1
Classification of Data Structures: Primitive and Non- Primitive,
Linear and Nonlinear; Data structure Operations,

Stack: Definition, Representation, Operations.

Applications: Polish and reverse polish expressions, Infix to postfix
conversion, evaluation of postfix expression, infix to prefix, postfix
to infix conversion.
 Lab Syllabus
MODULE 1
1. Write a C program to Implement the following searching techniques
a. Linear Search b. Binary Search.
2. Write a C program to implement the following sorting algorithms
using user defined functions: a. Bubble sort (Ascending order) b.
Selection sort (Descending order).
3. Write a C Program implement STACK with the following operations
a. Push an Element on to Stack b. Pop an Element from Stack
4. Implement a Program in C for converting an Infix Expression to
Postfix Expression.
5. Implement a Program in C for evaluating an Postfix Expression.
Syllabus
MODULE 2

Recursion - Factorial, GCD, Fibonacci Sequence, Tower of Hanoi.

Queue: Definition, Representation, Queue Variants: Circular

Queue, Priority Queue, Double Ended Queue;

Applications of Queues. Programming Examples.

Syllabus
MODULE 3
Linked List : Limitations of array implementation,

Memory Management: Static (Stack) and Dynamic (Heap) Memory

Allocation, Memory management functions. Definition, Representation,

Operations: getnode() and freenode() operations,

Types: Singly Linked List. Linked list as a data Structure, Inserting and
removing nodes from a list, Linked implementations of stacks, Header
nodes, Array implementation of lists.
Lab Syllabus
MODULE 3

6.
Write a C program to simulate the working of a singly linked list
providing the following operations:
a. Display & Insert
b. Delete from the beginning/end
c. Delete a given element
 Syllabus
MODULE 4

Introduction, Fundamentals of the Analysis of Algorithm

Efficiency Notion of Algorithm, Fundamentals of Algorithmic
Problem Solving, Important Problem Types,

Analysis Framework, Asymptotic Notations and Basic

efficiency classes, Mathematical analysis of Recursive and
Non-recursive algorithms.
 Syllabus
Module-5:
Brute Force: Selection Sort and Bubble Sort, Sequential Search,
Exhaustive search and String Matching.

Divide-and-Conquer: Mergesort, Quicksort, Binary Search, Binary tree

Traversals and related properties.

Decrease-and-Conquer: Insertion Sort, Depth First and Breadth First

Search, Topological sorting.

Greedy Technique: Prim’s Algorithm, Kruskal’s Algorithm, Dijkstra’s

Algorithm.
 Lab Syllabus
Module-5:
7. Obtain the Topological ordering of vertices in a given graph with the
help of a c programming.

8. Check whether a given graph is connected or not using DFS method

using C programming.

9. From a given vertex in a weighted connected graph, find shortest paths

to other vertices Using Dijkstra's algorithm (C programming)

10. Find Minimum Cost Spanning Tree of a given undirected graph using
Kruskal's algorithm ( C programming)
 Syllabus
Text Books:
1. Introduction to the Design and Analysis of Algorithms. AnanyLevitin, Pearson
Education, 2nd Edition.

2. Programming in ANSI C, Balaguruswamy, McGraw Hill Education .

3. Data Structures Using C and C++ by YedidyahLangsam and Moshe J. Augenstein

and Aaron M Tenanbanum, 2nd Edition, Pearson Education Asia, 2002.

4. Introduction to Data Structure and Algorithms with C++ by Glenn W. Rowe.

 Course Outcomes(COs)
CO No. Statement Bloom’s POs
Cognitive Levels

1 Ability to analyze and implement the concepts of Understanding PO1,PO2,PO3

Analysis,
linear data structures like Stack, Queue and Linked Design
List
2 Ability to Compute the efficiency of algorithms in Understanding PO1,PO2,PO3
Applying, Designing
terms of asymptotic notations for the recursive and
non-recursive algorithms.
3 Ability to implement different strategies of Algorithms Understanding PO1,PO2,PO3
Applying, Designing
like Brute force, Divide and conquer, Decrease and
conquer and Greedy technique.
 CO-PO Mapping
PO4 PO5 PO6 PO6 PO7 PO PO PO10 PO11 PO12
PO1 PO PO 8 9
2 3

CO1 3 3 3

CO2 3 3 3
CO3 3 3 3
Question Paper Pattern:

•
 DATA STRUCTURES
DEFINITION:

“The logical & Mathematical representation of data

in computer memory is called as Data Structure”.

OR

“A data structure is a method of storing data in

a computer so that it can be used efficiently”.
The Data Structures mainly deal with:

• The study of how the data is organized in the

memory.

• How efficiently the data can be stored in the

memory.

• How efficiently the data can be retrieved &

manipulated.
The Data Structure can be divided into

Primitive
The Primitive Data Structures are data
structures that can be manipulated directly by
machine instructions.
Ex: int, float, char, double.

Non-Primitive
Non-primitive data structures cannot be
manipulated directly by machine instructions.
Ex: linear and Non linear
Non primitive :

Linear Data Structures :

A data structure is said to be linear if its
elements form a sequence, or, in other words, a linear list.
Example : Arrays, Stacks, Quees, lists

Non linear Data Structures :

A data structure is said to be non linear if
its elements are stored randomly in memory.
Example : Graphs, Trees, Files
 Data Structure Operations

The most commonly used operations on data structures

• Insertion / Creation
• Deletion
• Traversing
• Searching
• Sorting
• Merging.
 ADT – Abstract Data Types

• An abstract data type is a mathematical model for data types. (

Logical Model).

• Data structure is a physical model for data types.

• In ADT data types is defined by its behavior (semantics) and

possible operations on data.
 ADT – Abstract Data Types

Definition ( ADT ) :
• ADT is a class of objects whose logical behavior is defined by a set
of values and set of operations.
• Data structure is an implementation of a ADT.

Possible values
Behavior

Functions/Modules
Operations
 STACKS

Def:
A stack is a special type of data structure, where
elements are inserted from one end and elements are
deleted from the same end.

The position from where elements are inserted and

from where elements are deleted is called top of the stack.

Stack is also called as Last In First Out(LIFO) data

structures.
Stack operations:

1. Push( Inserting an element on top of the stack)

2. Pop(Deleting an element from top of the stack)

3. Display(Display contents of stack).

Push Operation:

Inserting an element into the stack is called push

operation.
Only one item is inserted at a time & item has to be
inserted only from top of the stack.

Empty Stack Stack With elements

4 4
3 3 top12
2 2 05
1 1 15
0 0 24
top = -1
Inserting an element to stack : (push operation )

4 4 4 4
3 3 3 3
2 2 2 top 30 2
20 20
1 2 top 1 1
10 10 10
0 top 0 0 0
top=-1

4 top 50 4
40
top 3 40 3
30
2 30 2
20
1 20 1
10
0 10 0

* If we try to insert one more element it results in a “ overflow of Stack”

// C function for Push Operation.

void push() //function ---1

{
/* check for overflow of stack */
if (top == stack_size-1)
{
printf(“ stack overflow);
return;
}
top = top+1;
S[top] = item;
}
Pop operation:

Deleting an element from the stack is called “ Pop operation”.

Only one item is deleted from the stack and the item has
to be deleted only from top of the stack.
Deleting an element to stack : (pop operation )

top 50 4 4 4 4
40 3 top 40 3 3 3
30 2 30 2 top 30 2 2
20 20 20
20 1 2 1 top 1
10 10 10
10 0 0 0 0

4 4
3 3
2 2
1 1
10
top 0 0
top = -1
* If we try to delete one more element it results in a “ underflow of Stack”
// C function to delete an item from stack.

int pop() //function----2

{
int item_deleted;
if (top == -1)
{
printf(“ Stack Underflow “);
return 0;
}
item_deleted = S[top--];
return item_deleted;
}
Display stack items:
The contents of the stack are displayed from the bottom
to top.
// C function to display the contents of stack/

Void display() //function----3

{
int i;
if ( top == -1 )
{ Printf(“ stack is empty”); }
for( i=0; i<=top; i++ )
{
printf(“%d”, S[i]);
}
}
// C program to implement stack using arrays;

#include <stdio.h>
#include < process.h>
#define STACK_SIZE 5;

int top;
int s[10];
int item;

//function ---1
//function----2
//function----3
Void main()
{
int item;
int item_deleted;
int choice;

top = -1;
for( ; ; )
{
printf(“1. push, 2. pop, 3. Display, 4. Exit”);
printf(“enter the choice”);
Scanf(“%d”,&choice);
Switch(choice)
{
Case 1:
printf(“ Enter the item to be inserted”);
Scanf( “%d”, &item);
push();
break;
Case 2:
item_deleted = pop();
if (item_deleted == 0)
printf(“stack is empty”);
else
printf(“Item deleted= %d”, item_deleted);
break;
 Case 3:
display();
break;
default:
exit(0);
}
}
}
Applications of stack:

The various applications in which stacks are used are :

1.Conversion of expressions
2. Evaluation of expressions
3.recursion
Conversion of expressions

The sequence of operators and operands that reduces to a

single value after evaluation is called an expression.

There are three different types of expressions:

Prefix Expression:
Postfix expression:
Infix expression:
 Infix expression:
In an expression, if an operator is in the b/w two
operands, the expression is called an infix expression.
Ex: a+b, (a-b), (a+b*c-(d*f))
Postfix expression:
In an expression, if an operator follows the two
operands ( operator comes after the two operands ) , the
expression is called “postfix expression”. It is also called as
“Suffix expression”.
Ex: ab+, ab-, (a+b*c) ab*c+
Prefix Expression:
In an expression, if an operator precede the two
operands(i.e., operator comes before the two operands), the
expression is called “Prefix Expression”.
Ex: +ab, -ab….
Precedence and Associativity of the operator :

•While evaluating the expressions, some expressions are given

precedence over other expression and are evaluated first and
some are evaluated later.

“ The rules that determines the order in which the

different operators are evaluated are called precedence rules
Or precedence operators”.

Ex : 6 * (2 + 3) – 5 6 * (2 + 3) – 5
6*5–5 6*5–5
30 – 5 6*0
25 0
 The below table shows arithmetic operators along with
priority values,

Description Operator Priority

Exponentiation $ 6
Multiplication * 4
Division / 4
Mod % 4
Addition + 2
Substraction - 2
Associativity of the operator :

“ The order in which the operators with same precedence

are evaluated in an expression is called associativity of the
operator”.

In such cases the precedence rules are considered with

associativity.

The associativity can be classified into two types,

left to right associative ( left associative)

right to left associative (right associative).
left to right associative ( left associative) :

In an expression, if there are two or more operators

having the same priority and are evaluated from left to right ,
then the operators are called left associative operators.

Right to left associative (right associative) :

In an expression, if there are two or more operators

having the same priority and are evaluated from right to left ,
then the operators are called right associative operators.
 The below table shows arithmetic operators along with
priority values and there associativity.

Description Operator Priority Associativity

Exponentiation $ 6 Right to left

Multiplication * 4 Left to right
Division / 4 Left to right
Mod % 4 Left to right
Addition + 2 Left to right
Subtraction - 2 Left to right
Conversion from Infix to Postfix expression :
Manual method:
Ex: 1) (( A+(B-C)*D)^E+F)
Sol: (( A+(B-C)*D)^E+F) T1 = B-C  BC-
T1
(( A+T1*D)^E+F) T2 = T1*D T1D*
T2
(( A+T2)^E+F) T3 = A+T2 AT2+
T3
T3^E+F T4 = T3^E T3E^
T4
T4+F
T4F+
 Now substitute the values of T4,T3,T2,T1 we get postfix
expression,
 T4F+ T4 = T3E^

 T3E^F + T3 = AT2+

 AT2 + E^F + T2 = T1D*

 A T1 D * +E^F + T1 = BC-

 ABC-D*+E^F+

(( A+(B-C)*D)^E+F) = ABC-D*+E^F+
2. X ^ Y ^ Z-M +N+P/Q

 X ^ Y ^ Z-M +N+P/Q T1 = Y^Z  YZ^

T1
 X ^ T1-M +N+P/Q T2 = X^T1  XT1^
T2
 T2-M +N+P/Q T3 = P/Q  PQ/
T3
 T2-M+N+T3 T4 = T2-M  T2M-
T4
 T4+N+T3 T5 = T4+N  T4N+
T5
 T5+T3
 T5T3+
 By substituting the values of T5,T4,T3,T2,T1 we get
postfix expression,
 T5T3+ T5 = T4N+ and T3 = PQ/

T4N +PQ/+ T4 = T2M-

T2M-N+PQ/+ T2 = XT1^

XT1^M-N+PQ/+ T1 = YZ^

 XYZ^^M-N+PQ/+

X ^ Y ^ Z-M +N+P/Q = XYZ^^M-N+PQ/+

•To write a program by using stack data structure,
Let us use two precedence function F and G. The
function F contains the precedence values of symbols on top of
the stack and function G contains the precedence values of
symbols in the input string.
Shown in below table, ( infix to postfix )

Symbols Stack precedence Input precedence Associativity

“F” “G”
+,- 2 1 Left
*,/ 4 3 Left
$ or ^ 5 6 Right
Operands 8 7 Left
( 0 9 Left
) - 0 -
# -1 -
General procedure to convert from infix to postfix form :
Step 1 :
initialize top and stack of top
top = -1
s[++top] = ‘#’
j=0
Step 2 :
As long as the precedence value of the symbol on top of
the stack is greater than the precedence value of the current
input symbol, pop an item from the stack and place it in the
postfix expression.
while ( F(s[top]) > G(symbol) )
{
postfix[ j++ ] = s[ top-- ]
}
Step 3 :
Once the condition in while loop is failed, if the
precedence of the symbol on top of the stack is not equal to
the precedence value of the current input symbol, push the
current symbol on to the stack. Otherwise , delete an item
from the stack but do not place in the postfix expression.
if ( F(s[top]) != G(symbol) )
s[++top] = symbol
else
top--;
Step 4 :
After the complete execution of step 2 and step 3, pop
remaining symbols from stack to postfix expression.
while ( s[top] != ‘#’ )
postfix[j++] = s[top--]
* complete trace of the algorithm :
(A+(B–C)*D)
Stack S[top] Symbol F(s[top]) > G(symbol) Postfix
# #
# # ( ( -1 > 9 ) push (
#( ( A ( 0 > 7 ) push A
#(A A + ( 8 > 1 ) pop A A
#( ( ( 0 > 1 ) push +
#(+ + ( ( 2 > 9 ) push ( A
#(+( ( B ( 0 > 7 ) push B A
#(+(B B - ( 8 > 1 ) pop B AB
#(+( ( ( 0 > 1 ) push -
#(+(- - C ( 2 > 7 ) push C AB
#(+(-C C ) ( 8 > 0 ) pop C ABC
#(+(- - ( 2 > 0 ) pop – ABC-
#(+( ( ( 0 = 0 ) pop (
Don’t place in postfix expr
* complete trace of the algorithm :
(A+(B–C)*D)
Stack S[top] Symbol F(s[top]) > G(symbol) Postfix

#(+ + * ( 2 > 3 ) push * ABC-

#(+* * D (4 > 7) push D ABC-

#(+*D D ) ( 8 > 0 ) pop D ABC-D

#(+* * ( 4 > 0 ) pop * ABC-D*
#(+ + ( 2 > 0 ) pop + ABC-D*+
#( ( ( 0 = 0 ) pop (
Don’t place in postfix expr

# # ABC-D*+
/* C function for stack precedence
int F (char symbol) //function 1
{
Switch (symbol)
{
Case ‘+’ :
Case ‘-‘ : return 2;
Case ‘*’ :
Case ‘/’ : return 4;
Case ‘^’ :
Case ‘$’ : return 5;
Case ‘(‘ : return 0;
Case ‘#’: return -1;
default : return 8;
}
}
/* C function for input precedence
int G (char symbol) //function 2
{
Switch (symbol)
{
Case ‘+’ :
Case ‘-’ : return 1;
Case ‘*’ :
Case ‘/’ : return 3;
Case ‘^’ :
Case ‘$’ : return 6;
Case ‘(’ : return 9;
Case ‘)’ : return 0;
default : return 7;
}
}
/* C function to convert from infix into postfix expression.

void infix_postfix(char infix[], char postfix[])

{ //function 3
int top; int j; int I;
char s[30]; char symbol;

top=-1; Step : 1
S[++top]= ‘#’;
j=0;

for(i=0; i<strlen(infix); i++)

{
Symbol=infix[i];
 /* if stack precedence greater , remove symbol from
stack and place into postfix. */

while ( F(s[top]) > G(symbol) ) step : 2

{
postfix[j] = s[top--];
j++;
}

if ( F(s[top]) != G(symbol) ) step : 3

S[++top] = symbol;
else
top--;
}
 /* pop remaining symbols and place them in
postfix expression

while ( s[top] != ’#’ ) step : 4

{
postfix[j++] = s[top--];
}

postfix[j]=’\0’;
}
// C program to convert an infix expression to postfix
expression
# include < stdio.h>
# include < string.h >
/* include function 1, function 2, function 3. */
void main ()
{
char infix[20];
char postfix[20];
printf (“ Enter the valid infix expression”);
scanf (“ %s ”, infix );
infix_postfix ( infix, postfix);
printf (“ The postfix expression is “ );
printf (“%s”,postfix);
}
•To write a program by using stack data structure,
Let us use two precedence function F and G. The
function F contains the precedence values of symbols on top of
the stack and function G contains the precedence values of
symbols in the input string.
Shown in below table, ( infix to prefix )

Symbols Stack precedence Input precedence Associativity

“F” “G”
+,- 1 2 Left
*,/ 3 4 Left
$ or ^ 6 5 Right
Operands 8 7 Left
( - 0 Left
) 0 9 -
# -1 - -
General procedure to convert from infix to postfix form :
Step 1 :
initialize top and stack of top
top = -1
s[++top] = ‘#’
j = 0.( reverse the infix expression )
Step 2 :
As long as the precedence value of the symbol on top of
the stack is greater than the precedence value of the current
input symbol, pop an item from the stack and place it in the
postfix expression.
while ( F(s[top]) > G(symbol) )
{
postfix[ j++ ] = s[ top-- ]
}
Step 3 :
Once the condition in while loop is failed, if the
precedence of the symbol on top of the stack is not equal to
the precedence value of the current input symbol, push the
current symbol on to the stack. Otherwise , delete an item
from the stack but do not place in the postfix expression.
if ( F(s[top]) != G(symbol) )
s[++top] = symbol
else
top--;
Step 4 :
After the execution of step 2 and step 3, pop remaining
symbols from stack to postfix expression.
while ( s[top] != ‘#’ )
postfix[j++] = s[top--]
* complete trace of the algorithm :
( A + ( B – C )) = ))C–B(+A(
Stack S[top] Symbol F(s[top]) > G(symbol) Postfix
# # ) -1 > 9 push ‘)’
#) ) ) 0 > 9 push ‘)’
#)) ) C 0 > 7 push ‘C’
#))C C - 8 > 2 pop ‘C’ C
#)) ) 0 > 2 push ‘-’
#))- - B 1 > 7 push ‘B’ C
#))-B B ( 8 > 0 pop ‘B’ CB
#))- - 1 > 0 pop ‘-’ CB-
#)) ) 0 > 0 pop ‘)’
#) ) + 0 > 2 push ‘+’ CB-
#)+ + A 1 > 7 push ‘+’ CB-
#)+A A ( 8 > 0 pop ‘A’ CB-A
#)+ + 1 > 0 pop ‘+’ CB-A+
#) ) 0 > 0 pop ‘)’
i.e., CB-A+ = +A-BC
/* C function for stack precedence
int F (char symbol) function 1
{
Switch (symbol)
{
Case ‘+’ :
Case ‘-‘ : return 1;
Case ‘*’ :
Case ‘/’ : return 3;
Case ‘^’ :
Case ‘$’ : return 6;
Case ‘)‘ : return 0;
Case ‘#’: return -1;
default : return 8;
}
}
/* C function for input precedence
int G (char symbol) function 2
{
Switch (symbol)
{
Case ‘+’ :
Case ‘-’ : return 2;
Case ‘*’ :
Case ‘/’ : return 4;
Case ‘^’ :
Case ‘$’ : return 5;
Case ‘(’ : return 0;
Case ‘)’ : return 9;
default : return 7;
}
}
/* C function to convert from infix into prefix expression.

void infix_prefix(char infix[], char prefix[])

{ function 3
int top; int j; int I;
char s[30]; char symbol;

top=-1; Step : 1
S[++top]= ‘#’;
j=0;
strrev ( infix );
for(i=0; I < strlen (infix); i++)
{
Symbol=infix[i];
 /* if stack precedence greater , remove symbol from
stack and place into postfix. */

while ( F(s[top]) > G(symbol) ) step : 2

{
prefix[j] = s[top--];
j++;
}

if ( F(s[top]) != G(symbol) ) step : 3

S[++top] = symbol;
else
top--;
}
 /* pop remaining symbols and place them in
postfix expression

while ( s[top] != ’#’ ) step : 4

{
prefix[j++] = s[top--];
}

prefix[j]=’\0’;

strrev (prefix );
}
// C program to convert an infix expression to prefix expression
# include < stdio.h>
# include < string.h >
/* include function 1, function 2, function 3. */
void main ()
{
char infix[20];
char prefix[20];
printf (“ Enter the valid infix expression”);
scanf (“ %s ”, infix );
infix_prefix ( infix, prefix);
printf (“ The postfix expression is “ );
printf (“%s”, prefix);
}
Evaluation of postfix expression :

Algorithm:
Step 1 : Scan the symbol from left to right.

Step 2: If the scanned symbol is an operand, push it on

to the stack.

Step 3: If the scanned symbol is an operator, pop two

elements from the stack

The first popped element is operand 2 and the

second popped element is operand1
Op2 = s[top--];
Op1 = s[top--];
Step 4: perform the indicated operation.
res = op1 op op2.

Step 5: push the result on to the stack.

Step 6: Repeat the above procedure till the end of the

i/p is encountered.
Ex: Evaluate the following postfix expression.

ABC-D*+E$F+ infix((A+(B-C)*D)$E+F)

with the values,

A=6, B=3, C=2, D=5, E=1, F=7.

Solution:
After substituting the values

632-5*+1$7+
Ex: Evaluate the following postfix expression.

Postfix Expression symbol op2 op1 res = op1 op Stack

scanned op2 contents

632-5*+1$7+ 6 6
32-5*+1$7+ 3 63
2-5*+1$7+ 2 632
-5*+1$7+ - 2 3 3–2=1 61
5*+1$7+ 5 615
*+1$7+ * 5 1 1*5=5 65
+1$7+ + 5 6 6 + 5 = 11 11
1$7+ 1 11 1
$7+ $ 1 11 11 $ 1 = 11 11
7+ 7 11 7
+ + 7 11 11 + 7 = 18 18
// c program to evaluate the postfix expression:
#include < stdio.h >
#include < math.h >
#include < string.h >
double compute(char symbol, double op1, double op2)
{
switch ( symbol)
{
Case ‘+’ : return op1+op2;
Case ‘-’ : return op1-op2;
Case ‘*’ : return op1*op2;
Case ‘/’ : return op1/op2;
Case ‘$’:
Case ‘^’: return pow(op1,op2);
} }
void main()
{
double s[20] , res , op1 , op2 ;
int top, i ;
char postfix[20] , symbol ;
top = -1;
Printf(“ enter the postfix expression”);
Scanf(“%s”, postfix);

for ( i=0; i<strlen(postfix); i++ )

{

Symbol = postfix[i];
 if ( isdigit(symbol))
S[top++]= symbol;
else
{
op2 = s[top--];
op1 = s[top--];
res = compute(symbol, op1,op2);
S[++top] = res;
}
}
res = s[top--];
printf(“ the result is %f\n”, res);
}
Ex; to check whether a give string is palindrome or not using
stack.
# include <stdio.h>
# include <string.h>

int is_palindrome( char str[])

{
int i, top = -1;
char s[30], stk_item;
/* push all the characters of the given string
for( i=0; i<strlen(str); i++ )
{
S[++top]= str[i];
}
 /* check whether the string is palindrome or not.

for (i=0; i<strlen(str);i++)

{
Stk_item = s[top--];
if (str[i] != stk_item)
return 0;
}
return 1;
}
void main()
{
Char str[20];
printf(“enter string”);
Scanf(“%s”, str);
if (is_palindrome(str))
printf(“ the string is palindrome”);
else
printf(“ the string is not a palindrome”);
}