10/9/2025
Data Structure and Algorithm
Assignment : 01,02
Submitted to: Prof. Amna
Submitted by:Rida Irfan
[Link]: 24-CS-402
Difference between linear and binary search
Linear Search
• Data can be unsorted or sorted.
• It checks each element one by one until the target is found.
• It is slow for large lists.
Example:
If list = [5, 3, 9, 1] and you search 9 → it will check 5 → 3 → then 9 → found at 3rd position.
Binary Search
• Works only on sorted data.
• It divides the list into two halves, compares the middle element, and decides which half to search
next.
• It is much faster than linear search.
Example:
If list = [2, 4, 6, 8, 10] and you search 8 → check middle (6) → 8 is greater → move right → found
8.
Task 01:
Balanced Parentheses
Checker Input: a string of parentheses, e.g. "((a+b)*c)". Output: "Balanced" or "Not Balanced".
Hint: Push opening brackets onto stack, pop when a matching closing bracket is found.
Input:
#include <iostream>
#include <string>
using namespace std;
class Stack {
char st[50];
int top;
public:
void initstack() {
top = -1;}
bool isempty() {
return (top == -1):}
bool isfull() {
return (top == 49);}
void push (char c) {
if (isfull()) {
cout << "Stack Overflow\n";
} else {
st[++top] = c;}}
char pop () {
if (isempty ()) {
cout << "Stack Underflow\n";
return '\0';
} else {
return st[top--]:}}
char peek () {
if (isempty()) return '\0';
return st[top];
};
bool isBalanced(string expr) {
Stack s;
[Link]();
for (int i = 0; i < [Link](); i++) { // ? fixed loop
char ch = expr[i];
if (ch == '(' || ch == '{' || ch == '[') {
[Link](ch);
else if (ch == ')' || ch == '}' || ch == ']') {
if ([Link]())
return false;
char top = [Link]();
if ((ch == ')' && top != '(') ||
(ch == '}' && top != '{') ||
(ch == ']' && top != '['))
return false;
return [Link]();
int main() {
string expression;
cout << "Enter an expression: ";
getline(cin, expression);
if (isBalanced(expression))
cout << "Balanced" << endl;
else
cout << "Not Balanced" << endl;
return 0;
Output:
Task 02:
Reverse a String Input: "HELLO" Output: "OLLEH"
Input:
#include <iostream>
#include <string>
using namespace std;
class Stack {
int size;
char st[50];
int top;
public:
void initstack() {
size = 50
top = -1; }
bool isempty() {
return (top == -1); }
bool isfull() {
return (top == size - 1); }
void push(char c) {
if (isfull()) {
cout << "Stack is full!" << endl;
} else {
st[++top] = c;}}
char pop() {
if (isempty()) {
cout << "Stack is empty!" << endl;
return '\0';
} else {
return st[top--]; } }};
int main() {
Stack s;
[Link]();
string str;
cout << "Enter a string: ";
cin >> str;
for (int i = 0; i < [Link](); i++) {
[Link](str[i]);}
string reversed = "";
while (![Link]()) {
reversed += [Link](); }
cout << "Reversed String: " << reversed << endl;
return 0;}
Output:
Task 03:
Print Job Scheduling Simulate a printer queue where jobs arrive in order. Input: Job IDs
(integers). Process jobs in FIFO order.
Input:
#include <iostream>
using namespace std;
class queuee {
int que[6];
int front;
int rear;
public:
void initqueuee() {
front = -1;
rear = -1;
bool isempty() {
return (front == -1 || front > rear);
bool isfull() {
return (rear == 5); }
void inqueuee(int num) {
if (isfull()) {
cout << " queue is full!" << endl;
} else {
if (front == -1)
front = 0;
que[++rear] = num;
cout << "Job add to queue:" << num << endl;
void dequeue() {
if (isempty()) {
cout << "No jobs are in process!" << endl;
} else {
cout << " Jobs are in process: " << que[front] << endl;
front++;
}}
void peek() {
if (isempty()) {
cout << "No jobs waiting!" << endl;
} else {
cout << "Next job to print: " << que[front] << endl;
} }
void display() {
if (isempty()) {
cout << "No jobs in the queue!" << endl;
} else {
cout << "Current jobs in queue: ";
for (int i = front; i <= rear; i++) {
cout << que[i] << " ";
cout << endl; }}};
int main() {
queuee printer;
[Link]();
[Link](1);
[Link](10);
[Link](100);
[Link](109);
[Link]();
[Link]();
[Link]();
[Link]();
[Link]();
[Link]();
[Link]();
return 0;}
Output:
Task 04:
Bank Counter Simulation Customers arrive at a bank counter. Use a queue to represent waiting
line. Service customers in order of arrival.
Input:
#include <iostream>
using namespace std;
class queuee {
int que[6];
int front;
int rear;
public:
void initqueuee() {
front = -1;
rear = -1;
bool isempty() {
return (front == -1 || front > rear);
bool isfull() {
return (rear == 5);
void inqueuee(int num) {
if (isfull()) {
cout << "line of bank is full!" << endl;
} else {
if (front == -1)
front = 0;
que[++rear] = num;
cout << "customer " << num << "is enterd in the line." << endl;
void dequeue() {
if (isempty()) {
cout << "No customers to serve." << endl;
} else {
cout << "Serving customer: " << que[front] << endl;
front++;
void peek() {
if (isempty()) {
cout << "No customers waiting." << endl;
} else {
cout << "Next customer to serve: " << que[front] << endl;
void display() {
if (isempty()) {
cout << "line is empty." << endl;
} else {
cout << "Current customers in line: ";
for (int i = front; i <= rear; i++) {
cout << que[i] << " ";
cout << endl;
};
int main() {
queuee bank;
[Link]();
[Link](11);
[Link](12);
[Link](13);
[Link](14);
[Link]();
[Link]();
[Link]();
[Link]();
[Link]();
[Link]();
[Link]();
return 0;
Output:
Task 05:
Infix expression into prefix expression or postfix expression Conversion Write Function to
Convert a given infix expression into prefix expression or postfix expression (anyone of your
choice) using stack Write Function to Evaluate the Prefix or Postfix Expression. Write main
program to test your code. Test run your code using an input string and show here the state of
stack and output at each step of expression conversion from infix to prefix. Show the step by
step state of stack during evaluation of prefix/postfix expression
Input:
#include<iostream>
#include<string>
using namespace std;
class Stack {
char st[20];
int top;
int size;
public:
void initstack() {
top = -1;
size = 20;
bool isempty() {
return (top == -1);
bool isfull() {
return (top == size - 1);
void push(char c) {
if (isfull()) cout << "Stack full\n";
else st[++top] = c;
char pop() {
if (isempty()) {
cout << "Stack empty\n";
return '\0';
} else return st[top--];
char peek() {
if (isempty()) return '\0';
return st[top];
};
int prec(char op) {
if (op == '^') return 3;
if (op == '*' || op == '/') return 2;
if (op == '+' || op == '-') return 1;
return 0;
string intopost(string infix) {
Stack s;
[Link]();
string post = "";
for (int i = 0; i < [Link](); i++) {
char ch = infix[i];
if (isalnum(ch))
post += ch;
else if (ch == '(')
[Link](ch);
else if (ch == ')') {
while (![Link]() && [Link]() != '(')
post += [Link]();
[Link]();
else {
while (![Link]() && prec([Link]()) >= prec(ch))
post += [Link]();
[Link](ch);
while (![Link]())
post += [Link]();
return post;
int epostfix(string post) {
int st[20];
int top = -1;
for (int i = 0; i < [Link](); i++) {
char ch = post[i];
if (isdigit(ch))
st[++top] = ch - '0';
else {
int b = st[top--];
int a = st[top--];
int r;
if (ch == '+') r = a + b;
else if (ch == '-') r = a - b;
else if (ch == '*') r = a * b;
else if (ch == '/') r = a / b;
st[++top] = r;
return st[top];
int main() {
string infix;
cout << "Enter infix expression: ";
cin >> infix;
string postfix = intopost(infix);
cout << "Postfix expression: " << postfix << endl;
int result = epostfix(postfix);
cout << "Result: " << result << endl;
return 0;
Output: