A5-R5 – Data Structure Through Object Oriented Programming Language
// Question 1 Write a C++ program that reads a number from the user and counts the number of digits and sum of digits of the number
#include <iostream>
using namespace std;
int main() {
int num, digit, count = 0, sum = 0;
cout << "Enter a number: ";
cin >> num;
int temp = abs(num); // handle negative numbers
while (temp > 0) {
digit = temp % 10; // extract last digit
sum += digit; // add to sum
count++; // increase digit count
temp /= 10; // remove last digit
}
cout << "Number of digits: " << count << endl;
cout << "Sum of digits: " << sum << endl;
return 0;
}
// Q2 Breadth First Search is any search algorithm that considers neighbours of a vertex, that is, outgoing edges of the vertex's predecessor in the search, before any outgoing edges of the vertex. Extremes are searched last. This is typically implemented with a queue. Write a program in C++ to find the BFS of a given graph.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
int n = 5;
vector<vector<int>> g = {
{1,2}, {0,3,4}, {0}, {1}, {1} // adjacency list
};
vector<bool> vis(n,false);
queue<int> q;
q.push(0); vis[0]=true;
cout << "BFS: ";
while(!q.empty()){
int u=q.front(); q.pop();
cout<<u<<" ";
for(int v:g[u]) if(!vis[v]){
vis[v]=true; q.push(v);
}
}
}
// Q3 Create a class in C++ called rational1 that stores numerator and denominator. Write the
functions to input the data (ensure that denominator is not equal to 0), to display the number. Also use operator overloading to overload the arithmetic operators: +,-,*,/ and also relational operators: >,<,>=,<=,++,!=.
#include <iostream>
using namespace std;
class rational1 {
int num, den;
public:
rational1(int n=0,int d=1){ num=n; den=(d==0?1:d); }
void input(){ cin>>num>>den; if(den==0) den=1; }
void display(){ cout<<num<<"/"<<den<<endl; }
rational1 operator+(rational1 r){ return {num*r.den+r.num*den, den*r.den}; }
rational1 operator-(rational1 r){ return {num*r.den-r.num*den, den*r.den}; }
rational1 operator*(rational1 r){ return {num*r.num, den*r.den}; }
rational1 operator/(rational1 r){ return {num*r.den, den*r.num}; }
bool operator>(rational1 r){ return num*r.den > r.num*den; }
bool operator<(rational1 r){ return num*r.den < r.num*den; }
bool operator>=(rational1 r){ return !(*this<r); }
bool operator<=(rational1 r){ return !(*this>r); }
bool operator!=(rational1 r){ return num*r.den != r.num*den; }
rational1 operator++(){ num+=den; return *this; }
};
int main(){
rational1 a(1,2), b(1,3);
(a+b).display();
(a*b).display();
cout<<(a>b)<<endl;
(++a).display();
}
//Q4 In the assignment no.2, use friend function to overload operators: +,-,/,*
#include <iostream>
using namespace std;
class rational1 {
int n, d;
public:
rational1(int a=0, int b=1) { n=a; d=(b==0?1:b); }
void input() {
cout << "Enter numerator and denominator: ";
cin >> n >> d;
if(d==0) d=1;
}
void disp() { cout << n << "/" << d << endl; }
friend rational1 operator+(rational1 x, rational1 y) {
return {x.n*y.d + y.n*x.d, x.d*y.d};
}
friend rational1 operator-(rational1 x, rational1 y) {
return {x.n*y.d - y.n*x.d, x.d*y.d};
}
friend rational1 operator*(rational1 x, rational1 y) {
return {x.n*y.n, x.d*y.d};
}
friend rational1 operator/(rational1 x, rational1 y) {
return {x.n*y.d, x.d*y.n};
}
};
int main() {
rational1 a(1,2), b(1,3);
(a+b).disp();
(a-b).disp();
(a*b).disp();
(a/b).disp();
}
//Q 4 Define a class to represent a bank account. Include the following:
a. Data Members:
b. Account n.
c. Name of the account holder
d. Balance amount
e. Member Functions:
f. To assign initial data
g. To deposit an amount
h. To display the data
#include <iostream>
using namespace std;
class Bank {
int accNo;
string name;
double balance;
public:
void assign(int a, string n, double b) {
accNo = a; name = n; balance = b;
}
void deposit(double amt) {
balance += amt;
}
void display() {
cout << "Account No: " << accNo << endl;
cout << "Name: " << name << endl;
cout << "Balance: " << balance << endl;
}
};
int main() {
Bank b;
b.assign(101, "Joy", 5000);
b.deposit(2000);
b.display();
}
//Q5 Write main() function to test the above class
a. Create two derived classes from already defined class in Assignment 4 (Current
Account and Saving Account). The Saving Account should have a minimum balance.
b. Create a function to withdraw an amount from Saving account. The balance should not
be less than minimum balance after withdrawal.
c. Create a function to withdraw an amount from Current Account. The account allows
the overdraft facility.
#include <iostream>
using namespace std;
class Bank {
protected:
int accNo;
string name;
double balance;
public:
void assign(int a, string n, double b) {
accNo = a; name = n; balance = b;
}
void deposit(double amt) { balance += amt; }
void display() {
cout << "Account No: " << accNo << "\nName: " << name << "\nBalance: " << balance << endl;
}
};
// ---------- Saving Account ----------
class SavingAccount : public Bank {
double minBalance;
public:
SavingAccount(int a, string n, double b, double m) {
assign(a,n,b); minBalance = m;
}
void withdraw(double amt) {
if(balance - amt >= minBalance) balance -= amt;
else cout << "Withdrawal denied! Minimum balance must be kept.\n";
}
};
// ---------- Current Account ----------
class CurrentAccount : public Bank {
public:
CurrentAccount(int a, string n, double b) { assign(a,n,b); }
void withdraw(double amt) {
balance -= amt; // overdraft allowed
}
};
// ---------- Main Function ----------
int main() {
SavingAccount s(101,"Alice",5000,1000);
CurrentAccount c(102,"Bob",3000);
cout << "\n--- Saving Account ---\n";
s.display();
s.withdraw(4500); // Not allowed
s.withdraw(3000); // Allowed
s.display();
cout << "\n--- Current Account ---\n";
c.display();
c.withdraw(5000); // Overdraft allowed
c.display();
}
//Q6 Create a class MAT of size m*n. Define following matrix operations for MAT type objects: Sum, product, transpose
#include <iostream>
using namespace std;
class MAT {
int m, n;
int a[10][10]; // fixed size for simplicity
public:
MAT(int r=0,int c=0){ m=r; n=c; }
void input() {
cout << "Enter elements of " << m << "x" << n << " matrix:\n";
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
cin >> a[i][j];
}
void display() {
for(int i=0;i<m;i++){
for(int j=0;j<n;j++)
cout << a[i][j] << " ";
cout << endl;
}
}
// --------- Sum ---------
MAT operator+(MAT b) {
MAT res(m,n);
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
res.a[i][j]=a[i][j]+b.a[i][j];
return res;
}
// --------- Product ---------
MAT operator*(MAT b) {
MAT res(m,b.n);
for(int i=0;i<m;i++)
for(int j=0;j<b.n;j++){
res.a[i][j]=0;
for(int k=0;k<n;k++)
res.a[i][j]+=a[i][k]*b.a[k][j];
}
return res;
}
// --------- Transpose ---------
MAT transpose() {
MAT res(n,m);
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
res.a[j][i]=a[i][j];
return res;
}
};
// --------- Main ---------
int main() {
MAT A(2,2), B(2,2);
cout << "Matrix A:\n"; A.input();
cout << "Matrix B:\n"; B.input();
cout << "\nA + B:\n"; (A+B).display();
cout << "\nA * B:\n"; (A*B).display();
cout << "\nTranspose of A:\n"; A.transpose().display();
}
//Q7 Define a class String. Use overloaded == operator to compare two string type objects.
Write a program that can be used as a database of student’s information for a department. The
program should be able to dynamically allocate or deallocate storage for the student’s records
using singly linked list. The database should have the following fields: the first and last names,
a course code, and a grade for a student. The program should display the following menu:
a. Welcome to the database menu!
b. Press 1 to insert a new record
c. Press 2 to delete a record
d. Press 3 to search the database (by last name)
e. Press 4 to print a range in the database
f. Press 9 to quit
#include <iostream>
#include <string>
using namespace std;
// -------- String Class with == Overload --------
class String {
string s;
public:
String(string str=""){ s=str; }
bool operator==(String x){ return s==x.s; }
string get(){ return s; }
};
// -------- Student Node --------
struct Student {
String fname, lname, course;
char grade;
Student* next;
Student(String f,String l,String c,char g){
fname=f; lname=l; course=c; grade=g; next=NULL;
}
};
// -------- Database Class --------
class Database {
Student* head;
public:
Database(){ head=NULL; }
void insert(String f,String l,String c,char g){
Student* t=new Student(f,l,c,g);
t->next=head; head=t;
}
void remove(String l){
Student* p=head,*prev=NULL;
while(p && !(p->lname==l)){ prev=p; p=p->next; }
if(!p){ cout<<"Not found!\n"; return; }
if(!prev) head=p->next; else prev->next=p->next;
delete p; cout<<"Deleted!\n";
}
void search(String l){
Student* p=head;
while(p){ if(p->lname==l){ printOne(p); return;} p=p->next; }
cout<<"Not found!\n";
}
void printRange(String l1,String l2){
Student* p=head;
while(p){
if(p->lname.get()>=l1.get() && p->lname.get()<=l2.get())
printOne(p);
p=p->next;
}
}
void printOne(Student* s){
cout<<s->fname.get()<<" "<<s->lname.get()
<<" | "<<s->course.get()<<" | "<<s->grade<<"\n";
}
};
// -------- Main Menu --------
int main(){
Database db; int ch;
cout<<"Welcome to the database menu!\n";
do{
cout<<"1.Insert 2.Delete 3.Search 4.PrintRange 9.Quit\nChoice: ";
cin>>ch;
if(ch==1){ string f,l,c; char g;
cout<<"Enter fname lname course grade: ";
cin>>f>>l>>c>>g;
db.insert(f,l,c,g);
}
else if(ch==2){ string l;
cout<<"Enter last name: "; cin>>l;
db.remove(l);
}
else if(ch==3){ string l;
cout<<"Enter last name: "; cin>>l;
db.search(l);
}
else if(ch==4){ string l1,l2;
cout<<"Enter range l1 l2: "; cin>>l1>>l2;
db.printRange(l1,l2);
}
}while(ch!=9);
}
//Q8 Write a program to traverse a singly linked list
a. Merge two sorted linked lists to form a third sorted linked list.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int v){ data=v; next=NULL; }
};
// Insert at end
void insert(Node*& head, int val) {
Node* t=new Node(val);
if(!head){ head=t; return; }
Node* p=head;
while(p->next) p=p->next;
p->next=t;
}
// Traverse
void traverse(Node* head) {
while(head){ cout<<head->data<<" "; head=head->next; }
cout<<endl;
}
// Merge two sorted lists
Node* merge(Node* a, Node* b) {
if(!a) return b;
if(!b) return a;
Node* head=NULL, *tail=NULL;
if(a->data < b->data){ head=tail=a; a=a->next; }
else { head=tail=b; b=b->next; }
while(a && b){
if(a->data < b->data){ tail->next=a; tail=a; a=a->next; }
else { tail->next=b; tail=b; b=b->next; }
}
tail->next = (a)?a:b;
return head;
}
int main(){
Node* l1=NULL; Node* l2=NULL;
insert(l1,1); insert(l1,3); insert(l1,5);
insert(l2,2); insert(l2,4); insert(l2,6);
cout<<"List1: "; traverse(l1);
cout<<"List2: "; traverse(l2);
Node* merged = merge(l1,l2);
cout<<"Merged: "; traverse(merged);
}
//Q9 Given a linked list of integers sorted from smallest (at the head end) to largest, make
appropriate function that inserts the node in the linked list so that it remains in sorted order.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int v){ data=v; next=NULL; }
};
// Insert in sorted order
void sortedInsert(Node*& head, int val) {
Node* t=new Node(val);
if(!head || val < head->data) { // insert at head
t->next=head;
head=t;
return;
}
Node* cur=head;
while(cur->next && cur->next->data < val)
cur=cur->next;
t->next=cur->next;
cur->next=t;
}
// Traverse the list
void traverse(Node* head){
while(head){ cout<<head->data<<" "; head=head->next; }
cout<<endl;
}
int main(){
Node* head=NULL;
sortedInsert(head,10);
sortedInsert(head,5);
sortedInsert(head,20);
sortedInsert(head,15);
sortedInsert(head,1);
cout<<"Sorted Linked List: ";
traverse(head);
}
//Q10Implement a data structure using array that supports the following operations: insert, findMin,
findMax, deleteMin, deleteMax, isEmpty, makeEmpty.
a. Note: You must use the following algorithm: maintain a sorted array. Insert new items
into the correct position in the array, sliding elements over one position to the right, as
needed. findMin and findMax, and deleteMax are trivial. For deleteMin remove the
item in position 0, and slide over all the other items one position to the left.
b. Consider a database of patient’s information for a hospital. The program should be able
to allocate and deallocate storage memory for the patient’s records. The database
should have the following information field: the first and last names, patient id, address
, related disease , date of admission Devise an appropriate C++ class Queue using
arrays to implement the following functions a) inserting an element( a record) in the
queue, b) deleting the record from the queue, and c) searching record from the queue
by patient id.
#include <iostream>
using namespace std;
// --------- Part A: Sorted Array Data Structure ---------
class SortedArray {
int arr[50], n;
public:
SortedArray() { n = 0; }
void insert(int x) {
int i = n - 1;
while (i >= 0 && arr[i] > x) {
arr[i + 1] = arr[i];
i--;
}
arr[i + 1] = x;
n++;
}
int findMin() { return (n ? arr[0] : -1); }
int findMax() { return (n ? arr[n - 1] : -1); }
void deleteMin() {
if (n) {
for (int i = 0; i < n - 1; i++) arr[i] = arr[i + 1];
n--;
}
}
void deleteMax() { if (n) n--; }
bool isEmpty() { return n == 0; }
void makeEmpty() { n = 0; }
void display() {
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << "\n";
}
};
// --------- Part B: Patient Database (Queue using array) ---------
struct Patient {
string fname, lname, disease, addr, date;
int id;
};
class PatientQueue {
Patient arr[50];
int f = 0, r = -1, s = 0;
public:
void insert(Patient p) {
if (s < 50) { arr[++r] = p; s++; }
}
void del() {
if (s > 0) { f++; s--; }
}
void search(int id) {
for (int i = f; i <= r; i++) {
if (arr[i].id == id) {
cout << "Found: " << arr[i].id << " " << arr[i].fname
<< " " << arr[i].lname << " " << arr[i].disease
<< " " << arr[i].date << "\n";
}
}
}
void disp() {
for (int i = f; i <= r; i++)
cout << arr[i].id << " " << arr[i].fname << " " << arr[i].lname << "\n";
}
};
// --------- Main Function ---------
int main() {
// Part A test
SortedArray sa;
sa.insert(30);
sa.insert(10);
sa.insert(20);
cout << "Sorted Array: ";
sa.display();
cout << "Min = " << sa.findMin()
<< " Max = " << sa.findMax() << "\n";
sa.deleteMin();
sa.display();
// Part B test
PatientQueue q;
Patient p1 = {"John", "Doe", "Fever", "NY", "22-8-25", 101};
Patient p2 = {"Riya", "Sharma", "Cough", "Delhi", "21-8-25", 102};
q.insert(p1);
q.insert(p2);
cout << "Patient list:\n";
q.disp();
q.search(102);
q.del();
q.disp();
}
//Q11Consider a database of patient’s information for a hospital. The database should have the
following information field: the first and last names, patient id, address, related disease, date
of admission Devise an appropriate C++ class Queue using array to implement the following
functions a) inserting an element (a record) in the queue, b) deleting the record from the queue,
and c) searching record from the queue by patient id.
#include <iostream>
using namespace std;
struct Patient {
string fname, lname, address, disease, doa;
int id;
};
class PatientQueue {
Patient arr[100];
int front, rear, size;
public:
PatientQueue(){ front=0; rear=-1; size=0; }
void insert(Patient p){
if(size==100){ cout<<"Queue full\n"; return; }
rear=(rear+1)%100; arr[rear]=p; size++;
}
void deleteRecord(){
if(size==0){ cout<<"Queue empty\n"; return; }
front=(front+1)%100; size--;
}
void search(int pid){
for(int i=0;i<size;i++){
int idx=(front+i)%100;
if(arr[idx].id==pid){
cout<<"Found: "<<arr[idx].fname<<" "<<arr[idx].lname
<<" | Disease:"<<arr[idx].disease
<<" | DoA:"<<arr[idx].doa<<"\n";
return;
}
}
cout<<"Patient not found\n";
}
void display(){
for(int i=0;i<size;i++){
int idx=(front+i)%100;
cout<<arr[idx].id<<" "<<arr[idx].fname<<" "<<arr[idx].lname<<"\n";
}
}
};
int main(){
PatientQueue q;
Patient p1={"John","Doe","Delhi","Fever","22-08-25",101};
Patient p2={"Riya","Sharma","Mumbai","Cough","21-08-25",102};
q.insert(p1); q.insert(p2);
cout<<"All Patients:\n"; q.display();
q.search(102);
q.deleteRecord();
cout<<"After Deletion:\n"; q.display();
}
//Q12 Consider a database of patient’s information for a hospital. The program should be able to
allocate and deallocate storage memory for the patient’s records. The database should have
the following information field: the first and last names, patient id, address, related disease,
date of admission Devise an appropriate C++ class Queue using linked list to implement the following functions a) inserting an element( a record) in the queue, b) deleting the record from the queue, and c) searching record from the queue by patient id.
#include <iostream>
using namespace std;
// Patient record structure
struct Patient {
string fname, lname, address, disease, date;
int id;
Patient* next;
Patient(string f, string l, int i, string a, string d, string dt) {
fname=f; lname=l; id=i; address=a; disease=d; date=dt; next=NULL;
}
};
// Queue class using linked list
class PatientQueue {
Patient *front, *rear;
public:
PatientQueue() { front = rear = NULL; }
// a) Insert record
void insert(string f, string l, int i, string a, string d, string dt) {
Patient* p = new Patient(f,l,i,a,d,dt);
if(!rear) front = rear = p;
else { rear->next = p; rear = p; }
}
// b) Delete record
void del() {
if(!front) { cout<<"Queue Empty\n"; return; }
Patient* temp = front;
front = front->next;
if(!front) rear=NULL;
cout<<"Deleted: "<<temp->id<<"\n";
delete temp;
}
// c) Search by patient id
void search(int id) {
Patient* cur = front;
while(cur) {
if(cur->id == id) {
cout<<"Found: "<<cur->fname<<" "<<cur->lname
<<" Disease: "<<cur->disease<<" Date: "<<cur->date<<"\n";
return;
}
cur = cur->next;
}
cout<<"Not Found\n";
}
// Display all records
void display() {
Patient* cur = front;
while(cur) {
cout<<cur->id<<" "<<cur->fname<<" "<<cur->lname<<" "
<<cur->disease<<" "<<cur->date<<"\n";
cur = cur->next;
}
}
};
// ---------- Main ----------
int main() {
PatientQueue q;
q.insert("John","Doe",101,"NY","Fever","22-8-25");
q.insert("Riya","Sharma",102,"Delhi","Cough","21-8-25");
q.display();
q.search(102);
q.del();
q.display();
}
//Q13 Implement stack as class in C++ having a constructor. Create the functions with the
functionalities for the operations: push(), pop(), isempty(), isfull().
Display a Main Menu as below:
"Stack Operations Main Menu”
1.Push
2.Pop
3.IsEmpty
4.IsFull
0.Exit
Implement the stack using array.
#include <iostream>
using namespace std;
class Stack{
int top,arr[5];
public: Stack(){top=-1;}
void push(int x){ if(top==4) cout<<"Full\n"; else arr[++top]=x; }
void pop(){ if(top==-1) cout<<"Empty\n"; else cout<<"Popped:"<<arr[top--]<<"\n"; }
bool isempty(){ return top==-1; }
bool isfull(){ return top==4; }
void disp(){ for(int i=0;i<=top;i++) cout<<arr[i]<<" "; cout<<"\n"; }
};
int main(){
Stack s; int ch,v;
do{
cout<<"\n1.Push 2.Pop 3.IsEmpty 4.IsFull 0.Exit\nChoice:"; cin>>ch;
if(ch==1){cin>>v; s.push(v);}
else if(ch==2) s.pop();
else if(ch==3) cout<<(s.isempty()?"Empty\n":"Not Empty\n");
else if(ch==4) cout<<(s.isfull()?"Full\n":"Not Full\n");
s.disp();
}while(ch!=0);
}
//Q14 Implement stack as class in C++ having a constructor. Create the functions with the
functionalities for the operations: push(), pop(), isempty(), isfull().
Display a Main Menu as below:
"Stack Operations Main Menu”
1.Push
2.Pop
3.IsEmpty
4.IsFull
0.Exit
Implement the stack using linked list.
#include <iostream>
using namespace std;
class Node {
public:
int d;
Node* n;
Node(int x) { d = x; n = NULL; }
};
class Stack {
Node* top;
public:
Stack() { top = NULL; }
void push(int x) {
Node* t = new Node(x);
t->n = top;
top = t;
}
void pop() {
if (!top) cout << "Empty\n";
else {
cout << "Popped: " << top->d << "\n";
Node* t = top;
top = top->n;
delete t;
}
}
bool isempty() { return top == NULL; }
bool isfull() { return false; } // linked list stack never full
void disp() {
for (Node* c = top; c; c = c->n) cout << c->d << " ";
cout << "\n";
}
};
int main() {
Stack s;
int ch, v;
do {
cout << "\nStack Operations Main Menu\n";
cout << "1.Push\n2.Pop\n3.IsEmpty\n4.IsFull\n0.Exit\nChoice: ";
cin >> ch;
if (ch == 1) { cin >> v; s.push(v); }
else if (ch == 2) s.pop();
else if (ch == 3) cout << (s.isempty() ? "Empty\n" : "Not Empty\n");
else if (ch == 4) cout << (s.isfull() ? "Full\n" : "Not Full\n");
s.disp();
} while (ch != 0);
}
//Q15 Infix, Postfix and Prefix notations are three different but equivalent ways of writing
expressions.
Infix notation: X + Y Operators are written in-between their operands. This is the usual way
we write expressions. An expression such as A * ( B + C ) / D is usually taken to mean
something like: "First add B and C together, then multiply the result by A, then divide by D to
give the final answer."
Postfix notation (also known as "Reverse Polish notation"): X Y + Operators are written after
their operands. The infix expression given above is equivalent to A B C + * D /
Prefix notation (also known as "Polish notation"): + X Y Operators are written before their
operands. The expressions given above are equivalent to / * A + B C D
Write a program in C++ to convert an infix expression into a) prefix and b) postfix expression?
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
int prec(char c) {
if (c == '^') return 3;
if (c == '*' || c == '/') return 2;
if (c == '+' || c == '-') return 1;
return -1;
}
string infixToPostfix(string s) {
stack<char> st;
string res;
for (char c : s) {
if (isalnum(c)) res += c;
else if (c == '(') st.push(c);
else if (c == ')') {
while (!st.empty() && st.top() != '(') {
res += st.top(); st.pop();
}
st.pop();
} else {
while (!st.empty() && prec(st.top()) >= prec(c)) {
res += st.top(); st.pop();
}
st.push(c);
}
}
while (!st.empty()) { res += st.top(); st.pop(); }
return res;
}
string infixToPrefix(string s) {
reverse(s.begin(), s.end());
for (char &c : s) {
if (c == '(') c = ')';
else if (c == ')') c = '(';
}
string postfix = infixToPostfix(s);
reverse(postfix.begin(), postfix.end());
return postfix;
}
int main() {
string infix;
cout << "Enter infix expression: ";
cin >> infix;
cout << "Postfix: " << infixToPostfix(infix) << endl;
cout << "Prefix: " << infixToPrefix(infix) << endl;
}
//Q16Write a C++ program for the evaluation of postfix expression (created in assignment no 17)
using Stack?
#include <iostream>
#include <stack>
using namespace std;
int evalPostfix(string exp) {
stack<int> st;
for (char c : exp) {
if (isdigit(c)) st.push(c - '0');
else {
int val2 = st.top(); st.pop();
int val1 = st.top(); st.pop();
switch (c) {
case '+': st.push(val1 + val2); break;
case '-': st.push(val1 - val2); break;
case '*': st.push(val1 * val2); break;
case '/': st.push(val1 / val2); break;
}
}
}
return st.top();
}
int main() {
string exp;
cout << "Enter Postfix Expression: ";
cin >> exp;
cout << "Result = " << evalPostfix(exp);
}
//Q17 Build a Binary Search tree by adding the following items into an empty Binary Search Tree,
in order: J, T, E, G, F, B, A, R, O, P, U, M, N, K, L, H, D, S, C, Q, I
Write the functions for the tree traversal in each of the following orders:
a) Pre-order traversal
b) In-order traversal
c) Post-order traversal
#include <iostream>
using namespace std;
struct Node {
char data;
Node *left, *right;
Node(char v) : data(v), left(NULL), right(NULL) {}
};
Node* insert(Node* root, char v) {
if (!root) return new Node(v);
if (v < root->data) root->left = insert(root->left, v);
else root->right = insert(root->right, v);
return root;
}
void preorder(Node* r) {
if (!r) return;
cout << r->data << " ";
preorder(r->left);
preorder(r->right);
}
void inorder(Node* r) {
if (!r) return;
inorder(r->left);
cout << r->data << " ";
inorder(r->right);
}
void postorder(Node* r) {
if (!r) return;
postorder(r->left);
postorder(r->right);
cout << r->data << " ";
}
int main() {
char vals[] = {'J','T','E','G','F','B','A','R','O','P','U','M','N','K','L','H','D','S','C','Q','I'};
int n = sizeof(vals)/sizeof(vals[0]);
Node* root = NULL;
for (int i=0;i<n;i++) root = insert(root, vals[i]);
cout << "Preorder: "; preorder(root); cout << "\n";
cout << "Inorder: "; inorder(root); cout << "\n";
cout << "Postorder: "; postorder(root); cout << "\n";
}
//Q18Consider a database of student’s information for a department. The data should be stored in
array of Structures. The database should have the following fields: the first and last names, a
course code, and a grade for a student. Create a C++ function to search a particular student’s
information from the database using linear search
#include <iostream>
#include <string>
using namespace std;
struct Student {
string firstName;
string lastName;
string courseCode;
char grade;
};
int linearSearch(Student arr[], int n, string lname) {
for (int i = 0; i < n; i++) {
if (arr[i].lastName == lname) return i; // found
}
return -1; // not found
}
int main() {
int n;
cout << "Enter number of students: ";
cin >> n;
Student db[50]; // max 50 students
for (int i = 0; i < n; i++) {
cout << "Enter FirstName LastName CourseCode Grade: ";
cin >> db[i].firstName >> db[i].lastName >> db[i].courseCode >> db[i].grade;
}
string key;
cout << "Enter last name to search: ";
cin >> key;
int idx = linearSearch(db, n, key);
if (idx != -1) {
cout << "Student found: " << db[idx].firstName << " " << db[idx].lastName
<< ", Course: " << db[idx].courseCode << ", Grade: " << db[idx].grade << "\n";
} else {
cout << "Student not found!\n";
}
}
//Q18 Given a two-dimensional array, containing names of all officers in an organization in the
alphabetical order. Write a C++ program to input the name of an officer and then search the
name in the given array. In case the name is found, print the position of the same in the array,
else print the message “Search Unsuccessful””. Use binary search technique.
#include <iostream>
#include <string>
using namespace std;
int main() {
int rows, cols;
cout << "Enter rows and cols: ";
cin >> rows >> cols;
string officers[50][50]; // max 50x50
cout << "Enter officer names in alphabetical order:\n";
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
cin >> officers[i][j];
string key;
cout << "Enter officer name to search: ";
cin >> key;
// Treat 2D array as 1D sorted list
int low = 0, high = rows * cols - 1, found = -1;
while (low <= high) {
int mid = (low + high) / 2;
int r = mid / cols, c = mid % cols; // convert back to 2D index
if (officers[r][c] == key) {
found = mid; break;
} else if (officers[r][c] < key)
low = mid + 1;
else
high = mid - 1;
}
if (found != -1) {
cout << "Officer found at position: Row "
<< (found / cols) << ", Column " << (found % cols) << endl;
} else {
cout << "Search Unsuccessful" << endl;
}
}
//Q19 Two arrays of size 20 each containing numbers in sorted order. Merge the two lists (arrays) in
a fashion that the resulting list (array) also contains the numbers in sorted order.
#include <iostream>
using namespace std;
int main() {
const int SIZE = 20;
int A[SIZE], B[SIZE], C[2 * SIZE];
cout << "Enter 20 sorted numbers for array A:\n";
for (int i = 0; i < SIZE; i++) cin >> A[i];
cout << "Enter 20 sorted numbers for array B:\n";
for (int i = 0; i < SIZE; i++) cin >> B[i];
int i = 0, j = 0, k = 0;
// Merge process
while (i < SIZE && j < SIZE) {
if (A[i] < B[j]) C[k++] = A[i++];
else C[k++] = B[j++];
}
while (i < SIZE) C[k++] = A[i++];
while (j < SIZE) C[k++] = B[j++];
cout << "Merged Sorted Array:\n";
for (int x = 0; x < 2 * SIZE; x++) cout << C[x] << " ";
cout << endl;
}
//Q20 There are different sorting techniques used for arranging the values present in the list. Suppose
we have a list of names of persons as a) “Rajan”, “Rohit”, “Aman”, “Jinny”, “Sanjay”,
“Bhatachariya” Write C++ programs arrange these names alphabetically using: a) Bubble Sort,
b) Selection Sort, c) Insertion Sort, d) Quicksort
#include <iostream>
#include <string>
using namespace std;
// Utility: Print array
void printArray(string arr[], int n) {
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << endl;
}
// a) Bubble Sort
void bubbleSort(string arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}
// b) Selection Sort
void selectionSort(string arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) minIdx = j;
}
swap(arr[i], arr[minIdx]);
}
}
// c) Insertion Sort
void insertionSort(string arr[], int n) {
for (int i = 1; i < n; i++) {
string key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// d) Quicksort
int partition(string arr[], int low, int high) {
string pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(string arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
string names[] = {"Rajan", "Rohit", "Aman", "Jinny", "Sanjay", "Bhatachariya"};
int n = 6;
// Bubble Sort
string arr1[6]; copy(begin(names), end(names), arr1);
bubbleSort(arr1, n);
cout << "Bubble Sort: "; printArray(arr1, n);
// Selection Sort
string arr2[6]; copy(begin(names), end(names), arr2);
selectionSort(arr2, n);
cout << "Selection Sort: "; printArray(arr2, n);
// Insertion Sort
string arr3[6]; copy(begin(names), end(names), arr3);
insertionSort(arr3, n);
cout << "Insertion Sort: "; printArray(arr3, n);
// Quicksort
string arr4[6]; copy(begin(names), end(names), arr4);
quickSort(arr4, 0, n - 1);
cout << "Quicksort: "; printArray(arr4, n);
return 0;
}
//21 A bank needs to maintain records of its customers. It is decided to create a database using B-
Tree (2-3 tree). The order is based on the Aadhaar number of each Customer. Each record
contains the following information. Name, Aadhaar Number.
A DBMS needs to be designed
to provide menu driven facility to its users. The facilities are:
I. Insert the record for a new customer
F. Find and display the record for a customer specified by name or by Aadhaar number
D. Delete the record of a customer from the database.
#include <iostream>
#include <string>
using namespace std;
// Customer record
struct Customer {
string name;
long long aadhaar; // Aadhaar number as key
};
// Node for 2-3 B-Tree
struct Node {
int nKeys; // Number of keys
Customer keys[2]; // Max 2 keys in 2-3 tree
Node* child[3]; // Max 3 children
bool isLeaf;
Node() {
nKeys = 0;
for (int i = 0; i < 3; i++) child[i] = NULL;
isLeaf = true;
}
};
// Utility function to display a customer
void displayCustomer(Customer c) {
cout << "Name: " << c.name << ", Aadhaar: " << c.aadhaar << endl;
}
// Find record by Aadhaar (B-Tree search)
Customer* search(Node* root, long long aadhaar) {
if (!root) return NULL;
int i = 0;
while (i < root->nKeys && aadhaar > root->keys[i].aadhaar) i++;
if (i < root->nKeys && aadhaar == root->keys[i].aadhaar) return &root->keys[i];
if (root->isLeaf) return NULL;
return search(root->child[i], aadhaar);
}
// Find by name (linear search in tree)
Customer* searchByName(Node* root, string name) {
if (!root) return NULL;
for (int i = 0; i < root->nKeys; i++) {
if (root->keys[i].name == name) return &root->keys[i];
}
if (root->isLeaf) return NULL;
for (int i = 0; i <= root->nKeys; i++) {
Customer* res = searchByName(root->child[i], name);
if (res) return res;
}
return NULL;
}
// Insert utility: Split child node
void splitChild(Node* parent, int i, Node* y) {
Node* z = new Node();
z->isLeaf = y->isLeaf;
z->nKeys = 1;
z->keys[0] = y->keys[1];
if (!y->isLeaf) {
z->child[0] = y->child[1];
z->child[1] = y->child[2];
}
y->nKeys = 1;
for (int j = parent->nKeys; j >= i + 1; j--) parent->child[j + 1] = parent->child[j];
parent->child[i + 1] = z;
for (int j = parent->nKeys - 1; j >= i; j--) parent->keys[j + 1] = parent->keys[j];
parent->keys[i] = y->keys[0];
parent->nKeys++;
}
// Insert into non-full node
void insertNonFull(Node* x, Customer k) {
int i = x->nKeys - 1;
if (x->isLeaf) {
while (i >= 0 && k.aadhaar < x->keys[i].aadhaar) {
x->keys[i + 1] = x->keys[i];
i--;
}
x->keys[i + 1] = k;
x->nKeys++;
} else {
while (i >= 0 && k.aadhaar < x->keys[i].aadhaar) i--;
i++;
if (x->child[i]->nKeys == 2) {
splitChild(x, i, x->child[i]);
if (k.aadhaar > x->keys[i].aadhaar) i++;
}
insertNonFull(x->child[i], k);
}
}
// Insert wrapper
void insert(Node*& root, Customer k) {
if (!root) {
root = new Node();
root->keys[0] = k;
root->nKeys = 1;
return;
}
if (root->nKeys == 2) {
Node* s = new Node();
s->isLeaf = false;
s->child[0] = root;
splitChild(s, 0, root);
int i = 0;
if (k.aadhaar > s->keys[0].aadhaar) i++;
insertNonFull(s->child[i], k);
root = s;
} else {
insertNonFull(root, k);
}
}
// In-order traversal (for display)
void inorder(Node* root) {
if (!root) return;
for (int i = 0; i < root->nKeys; i++) {
inorder(root->child[i]);
displayCustomer(root->keys[i]);
}
inorder(root->child[root->nKeys]);
}
// For simplicity, delete just marks Aadhaar = -1
bool deleteByAadhaar(Node* root, long long aadhaar) {
Customer* c = search(root, aadhaar);
if (c) {
c->aadhaar = -1;
c->name = "[Deleted]";
return true;
}
return false;
}
// Menu
int main() {
Node* root = NULL;
int choice;
do {
cout << "\n--- Bank Customer DB Menu ---\n";
cout << "1. Insert new customer\n";
cout << "2. Find by Aadhaar\n";
cout << "3. Find by Name\n";
cout << "4. Delete by Aadhaar\n";
cout << "5. Display all (Inorder)\n";
cout << "0. Exit\n";
cout << "Enter choice: ";
cin >> choice;
if (choice == 1) {
Customer c;
cout << "Enter Name: "; cin >> c.name;
cout << "Enter Aadhaar: "; cin >> c.aadhaar;
insert(root, c);
}
else if (choice == 2) {
long long a;
cout << "Enter Aadhaar: "; cin >> a;
Customer* c = search(root, a);
if (c && c->aadhaar != -1) displayCustomer(*c);
else cout << "Record not found.\n";
}
else if (choice == 3) {
string name;
cout << "Enter Name: "; cin >> name;
Customer* c = searchByName(root, name);
if (c && c->aadhaar != -1) displayCustomer(*c);
else cout << "Record not found.\n";
}
else if (choice == 4) {
long long a;
cout << "Enter Aadhaar to delete: "; cin >> a;
if (deleteByAadhaar(root, a)) cout << "Record deleted.\n";
else cout << "Record not found.\n";
}
else if (choice == 5) {
inorder(root);
}
} while (choice != 0);
return 0;
}
Or.......
#include <iostream>
#include <map>
using namespace std;
struct Customer {
string name;
long long aadhaar;
};
int main() {
map<long long, string> db; // Aadhaar -> Name
int choice;
do {
cout << "\n--- Bank DB Menu ---\n";
cout << "1. Insert Record\n2. Find Record\n3. Delete Record\n0. Exit\nChoice: ";
cin >> choice;
if (choice == 1) {
Customer c;
cout << "Enter Name: "; cin >> c.name;
cout << "Enter Aadhaar: "; cin >> c.aadhaar;
db[c.aadhaar] = c.name;
}
else if (choice == 2) {
long long a; cout << "Enter Aadhaar: "; cin >> a;
if (db.count(a)) cout << "Record Found -> Name: " << db[a] << "\n";
else cout << "Not Found!\n";
}
else if (choice == 3) {
long long a; cout << "Enter Aadhaar: "; cin >> a;
if (db.erase(a)) cout << "Record Deleted\n";
else cout << "Not Found!\n";
}
} while (choice != 0);
}
//23Depth First Search is any search algorithm that considers outgoing edges (children) of a vertex
before any of the vertex's siblings that is, outgoing edges of the vertex's predecessor in the
search. Extremes are searched first. This is typically implemented with a stack. Write a
program in C++ to find the DFS of a given graph
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> adj;
vector<bool> visited;
void DFS(int v) {
visited[v] = true;
cout << v << " ";
for (int u : adj[v])
if (!visited[u]) DFS(u);
}
int main() {
int V, E; cin >> V >> E;
adj.resize(V); visited.assign(V, false);
for (int i = 0, u, v; i < E; i++) {
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u); // undirected
}
int start; cin >> start;
DFS(start);
}
