#include <stdio.h>
int main() {
int n, j, i, swap;
printf("Enter number of elements\n");
scanf("%d", &n);
int array[n];
printf("Enter %d integers\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &array[i]);
}
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (array[j] > array[j + 1]) {
swap = array[j];
array[j] = array[j + 1];
array[j + 1] = swap;
}
}
}
printf("Sorted list (using Bubble Sort) :\n");
for (i = 0; i < n; i++) {
printf("%d\n", array[i]);
}
return 0;
}
Output:
Enter number of elements
4
Enter 4 integers
2
1
4
9
Sorted list in ascending order:
1
2
4
9
#include <stdio.h>
void selectionSort(int arr[], int size);
void swap(int *a, int *b);
void selectionSort(int arr[], int size)
{
int i, j;
for (i = 0; i < size; i++)
{
for (j = i; j < size; j++)
{
if (arr[i] > arr[j])
swap(&arr[i], &arr[j]);
}
}
}
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int main()
{
int array[10], i, size;
printf("Enter Number of Elements: ");
scanf("%d", &size);
printf("\nEnter %d numbers\t", size);
printf("\n");
for (i = 0; i < size; i++)
scanf("%d", &array[i]);
selectionSort(array, size);
printf("\nSorted array (Using Selection Sort) ");
for (i = 0; i < size; i++)
printf(" %d ", array[i]);
return 0;
}
Output:
Enter Number of Elements: 4
Enter 4 numbers
2
1
9
4
Sorted array (Using Selection Sort) 1 2 4 9
#include <stdio.h>
int main(void)
{
int n, i, j, temp;
int arr[64];
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
for (i = 1; i < n; i++)
{
j = i;
while (j > 0 && arr[j - 1] > arr[j])
{
temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
j--;
}
}
printf("Sorted list in ascending order:\n");
for (i = 0; i < n; i++)
{
printf("%d\n", arr[i]);
}
return 0;
}
Output:
Enter number of elements
4
Enter 4 integers
9
2
4
5
Sorted list in ascending order:
2
4
5
9
#include <stdio.h>
int main()
{
int a[20], i, x, n;
printf("How many elements?");
scanf("%d", &n);
printf("Enter array elements:\n");
for (i = 0; i < n; ++i)
scanf("%d", &a[i]);
printf("\nEnter element to search:");
scanf("%d", &x);
for (i = 0; i < n; ++i)
if (a[i] == x)
break;
if (i < n)
printf("Element found at index %d", i);
else
printf("Element not found");
return 0;
}
Output:
How many elements?8
Enter array elements:
3
2
78
67
12
21
87
90
Enter element to search:12
Element found at index 4
#include <stdio.h>
int main()
{
int i, low, high, mid, n, key, array[100];
printf("Enter number of elements:\n");
scanf("%d", &n);
printf("Enter %d integers:\n", n);
for (i = 0; i < n; i++)
scanf("%d", &array[i]);
printf("Enter value to find:\n");
scanf("%d", &key);
low = 0;
high = n - 1;
mid = (low + high) / 2;
while (low <= high)
{
if (array[mid] < key)
low = mid + 1;
else if (array[mid] == key)
{
printf("%d found at location %d.\n", key, mid + 1);
break;
}
else
high = mid - 1;
mid = (low + high) / 2;
}
if (low > high)
printf("Not found! %d isn't present in the list.\n", key);
return 0;
}
Output:
Enter number of elements: 5
Enter 5 integers: 2 1 3 4 5
Enter value to find: 5
5 found at location 5.
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
}*head;
void createList(int n);
void traverseList();
int main()
{
int n;
printf("Enter the total number of nodes: ");
scanf("%d", &n);
createList(n);
printf("\nData in the list\n");
traverseList();
return 0;
}
void createList(int n)
{
struct node *newNode, *temp;
int data, i;
head = (struct node *)malloc(sizeof(struct node));
if (head == NULL)
{
printf("Unable to allocate memory.");
exit(0);
}
printf("Enter the data of node 1: ");
scanf("%d", &data);
head->data = data;
head->next = NULL;
temp = head;
for (i = 2; i <= n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));
if (newNode == NULL)
{
printf("Unable to allocate memory.");
break;
}
printf("Enter the data of node %d: ", i);
scanf("%d", &data);
newNode->data = data;
newNode->next = NULL;
temp->next = newNode;
temp = temp->next;
}
}
Output:
Enter the total number of nodes: 5
Enter the data of node 1: 23
Enter the data of node 2: 32
Enter the data of node 3: 45
Enter the data of node 4: 67
Enter the data of node 5: 89
Data in the list
Data = 23
Data = 32
Data = 45
Data = 67
Data = 89
#include <stdio.h>
int main() {
int array[100];
int i, n, x, pos;
printf("Enter the number of elements in the array \n");
scanf("%d", &n);
printf("Enter the elements \n");
for (i = 0; i < n; i++) {
scanf("%d", &array[i]);
}
printf("Input array elements are: \n");
for (i = 0; i < n; i++) {
printf("%d ", array[i]);
}
printf("\nEnter the new element to be inserted: ");
scanf("%d", &x);
printf("Enter the position where element is to be inserted: ");
scanf("%d", &pos);
n = n + 1;
// Shift elements to make space for the new element
for (i = n - 1; i >= pos; i--) {
array[i] = array[i - 1];
}
array[pos - 1] = x;
printf("Array elements after insertion are: \n");
for (i = 0; i < n; i++) {
printf("%d ", array[i]);
}
return 0;
}
Output:
Enter the number of elements in the array
3
Enter the elements
1
4
5
Input array elements are:
1 4 5
Enter the new element to be inserted: 78
Enter the position where element is to be inserted: 3
Array elements after insertion are:
1 4 78 5
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int i, n, index, arr[10];
printf("Enter the size of the array: ");
scanf("%d", &n);
printf("Enter the elements of the array: \n");
for (i = 0; i < n; i++)
{
printf("arr[%d] = ", i);
scanf("%d", &arr[i]);
}
printf("Enter the index of the element to be deleted: ");
scanf("%d", &index);
if (index >= n + 1)
{
printf(" \n Deletion is not possible in the array.");
}
else
{
for (i = index; i < n - 1; i++)
arr[i] = arr[i + 1];
printf("The array after deleting the element is: ");
for (i = 0; i < n - 1; i++)
printf("%d ", arr[i]);
return 0;
}
}
Output:
Enter the size of the array: 4
Enter the elements of the array:
arr[0] = 3
arr[1] = 4
arr[2] = 2
arr[3] = 9
Enter the index of the element to be deleted: 2
The array after deleting the element is: 3 4 9
#include <stdio.h>
int stack[100], choice, n, top, x, i;
void push(void);
void pop(void);
void display(void);
int main()
{
top = -1;
printf("\n Enter the size of STACK[MAX=100]:");
scanf("%d", &n);
printf("\n\t STACK OPERATIONS USING ARRAY");
printf("\n\t--------------------------------");
printf("\n\t 1.PUSH\n\t 2.POP\n\t 3.DISPLAY\n\t 4.EXIT");
do
{
printf("\n Enter the Choice:");
scanf("%d", &choice);
switch (choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("\n\t EXIT POINT ");
break;
}
default:
{
printf("\n\t Please Enter a Valid Choice(1/2/3/4)");
}
}
} while (choice != 4);
return 0;
}
void push()
{
if (top >= n - 1)
{
printf("\n\tSTACK is over flow");
}
else
{
printf(" Enter a value to be pushed:");
scanf("%d", &x);
top++;
stack[top] = x;
}
}
void pop()
{
if (top <= -1)
{
printf("\n\t Stack is under flow");
}
else
{
printf("\n\t The popped elements is %d", stack[top]);
top--;
}
}
void display()
{
if (top >= 0)
{
printf("\n The elements in STACK \n");
for (i = top; i >= 0; i--)
printf("\n%d", stack[i]);
printf("\n Press Next Choice");
}
else
{
printf("\n The STACK is empty");
}
}
Output (Example):
Enter the size of STACK[MAX=100]: 5
STACK OPERATIONS USING ARRAY
--------------------------------
1.PUSH
2.POP
3.DISPLAY
4.EXIT
Enter the Choice: 1
Enter a value to be pushed: 12
Enter the Choice: 1
Enter a value to be pushed: 24
Enter the Choice: 1
Enter a value to be pushed: 98
Enter the Choice: 3
The elements in STACK
98
24
12
Press Next Choice
Enter the Choice: 2
The popped elements is 98
Enter the Choice: 3
The elements in STACK
24
12
Press Next Choice
Enter the Choice: 4
EXIT POINT
#include <stdio.h>
#include <stdlib.h>
struct node
{
int info;
struct node *ptr;
}*top,*top1,*temp;
int topelement();
void push(int data);
void pop();
void empty();
void display();
void destroy();
void stack_count();
void create();
int count = 0;
void main()
{
int no, ch, e;
printf("\n 1 - Push");
printf("\n 2 - Pop");
printf("\n 3 - Top");
printf("\n 4 - Empty");
printf("\n 5 - Exit");
printf("\n 6 - Display");
printf("\n 7 - Stack Count");
printf("\n 8 - Destroy stack");
create();
while (1)
{
printf("\n Enter choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("Enter data : ");
scanf("%d", &no);
push(no);
break;
case 2:
pop();
break;
case 3:
if (top == NULL)
printf("No elements in stack");
else
{
e = topelement();
printf("\n Top element : %d", e);
}
break;
case 4:
empty();
break;
case 5:
exit(0);
case 6:
display();
break;
case 7:
stack_count();
break;
case 8:
destroy();
break;
default :
printf(" Wrong choice, Please enter correct choice ");
break;
}
}
}
/* Create empty stack */
void create()
{
top = NULL;
}
/* Count stack elements */
void stack_count()
{
printf("\n No. of elements in stack : %d", count);
}
/* Push data into stack */
void push(int data)
{
if (top == NULL)
{
top =(struct node *)malloc(1*sizeof(struct node));
top->ptr = NULL;
top->info = data;
}
else
{
temp =(struct node *)malloc(1*sizeof(struct node));
temp->ptr = top;
temp->info = data;
top = temp;
}
count++;
}
/* Display stack elements */
void display()
{
top1 = top;
if (top1 == NULL)
{
printf("Stack is empty");
return;
}
while (top1 != NULL)
{
printf("%d ", top1->info);
top1 = top1->ptr;
}
}
/* Pop Operation on stack */
void pop()
{
top1 = top;
if (top1 == NULL)
{
printf("\n Error : Trying to pop from empty stack");
return;
}
else
top1 = top1->ptr;
printf("\n Popped value : %d", top->info);
free(top);
top = top1;
count--;
}
/* Return top element */
int topelement()
{
return(top->info);
}
/* Check if stack is empty or not */
void empty()
{
if (top == NULL)
printf("\n Stack is empty");
else
printf("\n Stack is not empty with %d elements", count);
}
/* Destroy entire stack */
void destroy()
{
top1 = top;
while (top1 != NULL)
{
top1 = top->ptr;
free(top);
top = top1;
top1 = top1->ptr;
}
free(top1);
top = NULL;
printf("\n All stack elements destroyed");
count = 0;
}
Output (Example):
1 - Push
2 - Pop
3 - Top
4 - Empty
5 - Exit
6 - Display
7 - Stack Count
8 - Destroy stack
Enter choice : 1
Enter data : 56
Enter choice : 1
Enter data : 80
Enter choice : 2
Popped value : 80
Enter choice : 3
Top element : 56
Enter choice : 1
Enter data : 78
Enter choice : 1
Enter data : 90
Enter choice : 6
90 78 56
Enter choice : 7
No. of elements in stack : 3
Enter choice : 8
All stack elements destroyed
Enter choice : 4
Stack is empty
Enter choice : 5
#include <stdio.h>
// Function to swap two elements
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to print the array
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = { 12, 17, 6, 25, 1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Output:
Sorted array:
1 5 6 12 17 25
#include <stdio.h>
#define max 10
int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
int b[10];
void merging(int low, int mid, int high) {
int l1, l2, i;
for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
if(a[l1] <= a[l2])
b[i] = a[l1++];
else
b[i] = a[l2++];
}
while(l1 <= mid)
b[i++] = a[l1++];
while(l2 <= high)
b[i++] = a[l2++];
for(i = low; i <= high; i++)
a[i] = b[i];
}
void sort(int low, int high) {
int mid;
if(low < high) {
mid = (low + high) / 2;
sort(low, mid);
sort(mid+1, high);
merging(low, mid, high);
} else {
return;
}
}
int main() {
int i;
printf("List before sorting\n");
for(i = 0; i <= max; i++)
printf("%d ", a[i]);
sort(0, max);
printf("\nList after sorting\n");
for(i = 0; i <= max; i++)
printf("%d ", a[i]);
}
Output:
List before sorting
10 14 19 26 27 31 33 35 42 44 0
List after sorting
0 10 14 19 26 27 31 33 35 42 44
#include<stdio.h>
#include<stdlib.h>
#define n 5
int main()
{
int queue[n],ch=1,front=0,rear=0,i,j=1,x=n;
printf("Queue using Array");
printf("\n1.Insertion \n2.Deletion \n3.Display \n4.Exit");
while(ch)
{
printf("\nEnter the Choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
if(rear==x)
printf("\n Queue is Full");
else
{
printf("\n Enter no %d:",j++);
scanf("%d",&queue[rear++]);
}
break;
case 2:
if(front==rear)
{
printf("\n Queue is empty");
}
else
{
printf("\n Deleted Element is %d",queue[front++]);
x++;
}
break;
case 3:
printf("\nQueue Elements are:\n ");
if(front==rear)
printf("\n Queue is Empty");
else
{
for(i=front; i< rear; i++)
{
printf("%d",queue[i]);
printf("\n");
}
break;
case 4:
exit(0);
default:
printf("Wrong Choice: please see the options");
}
}
}
return 0;
}
Output:
Queue using Array
1.Insertion
2.Deletion
3.Display
4.Exit
Enter the Choice:1
Enter no 1:10
Enter the Choice:1
Enter no 2:20
Enter the Choice:1
Enter no 3:30
Enter the Choice:1
Enter no 4:40
Enter the Choice:2
Deleted Element is 10
Enter the Choice:3
Queue Elements are:
20
30
40
Enter the Choice:4
#include <stdio.h>
#include <stdlib.h>
// Define the structure for a tree node
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
// Function to create a new tree node
struct TreeNode* createNode(int value) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function to insert a new node into the binary tree
struct TreeNode* insert(struct TreeNode* root, int value) {
if (root == NULL) {
return createNode(value);
}
if (value < root->data) {
root->left = insert(root->left, value);
} else if (value > root->data) {
root->right = insert(root->right, value);
}
return root;
}
// Function to perform an in-order traversal of the binary tree
void inorderTraversal(struct TreeNode* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
// Main function to demonstrate the binary tree implementation
int main() {
struct TreeNode* root = NULL;
// Insert elements into the binary tree
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
// Display the elements of the binary tree using in-order traversal
printf("In-order traversal of the binary tree: ");
inorderTraversal(root);
return 0;
}
OUTPUT:
In-order traversal of the binary tree: 20 30 40 50 60 70 80
#include <stdio.h>
void heapify(int a[], int n, int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && a[left] > a[largest])
largest = left;
if (right < n && a[right] > a[largest])
largest = right;
if (largest != i) {
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;
heapify(a, n, largest);
}
}
void heapSort(int a[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
heapify(a, n, i);
for (int i = n - 1; i >= 0; i--) {
int temp = a[0];
a[0] = a[i];
a[i] = temp;
heapify(a, i, 0);
}
}
void printArr(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
printf("%d", arr[i]);
printf(" ");
}
}
int main()
{
int a[] = {48, 10, 23, 43, 28, 26, 1};
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
heapSort(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}
OUTPUT:
Before sorting array elements are -
48 10 23 43 28 26 1
After sorting array elements are -
1 10 23 26 28 43 48
int main() {
struct Node* root = NULL;
root = insertNode(root, 50);
insertNode(root, 30);
insertNode(root, 20);
insertNode(root, 40);
insertNode(root, 70);
insertNode(root, 60);
insertNode(root, 80);
printf("Inorder traversal of the BST: ");
inorderTraversal(root);
printf("\n");
printf("Preorder traversal of the BST: ");
preorderTraversal(root);
printf("\n");
printf("Postorder traversal of the BST: ");
postorderTraversal(root);
printf("\n");
return 0;
}
OUTPUT:
Inorder traversal of the BST: 20 30 40 50 60 70 80
Preorder traversal of the BST: 50 30 20 40 70 60 80
Postorder traversal of the BST: 20 40 30 60 80 70 50
#include <stdio.h>
#include <stdlib.h>
// Structure to represent an edge in the graph
struct Edge {
int src, dest, weight;
};
// Structure to represent a subset for union-find
struct Subset {
int parent;
int rank;
};
// Function to create a graph with V vertices and E edges
struct Graph {
int V, E;
struct Edge* edge;
};
// Function to create a graph with V vertices and E edges
struct Graph* createGraph(int V, int E) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->E = E;
graph->edge = (struct Edge*)malloc(E * sizeof(struct Edge));
return graph;
}
// Function to find the set of an element i
int find(struct Subset subsets[], int i) {
if (subsets[i].parent != i) {
subsets[i].parent = find(subsets, subsets[i].parent);
}
return subsets[i].parent;
}
// Function that does union of two sets of x and y
void Union(struct Subset subsets[], int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank) {
subsets[xroot].parent = yroot;
} else if (subsets[xroot].rank > subsets[yroot].rank) {
subsets[yroot].parent = xroot;
} else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
// Comparison function used by qsort to sort edges based on their weights
int compare(const void* a, const void* b) {
struct Edge* edge1 = (struct Edge*)a;
struct Edge* edge2 = (struct Edge*)b;
return edge1->weight - edge2->weight;
}
// Function to find MST using Kruskal's algorithm
void KruskalMST(struct Graph* graph) {
int V = graph->V;
struct Edge result[V]; // Array to store the resultant MST
int e = 0; // Index variable, used for result[]
// Step 1: Sort all edges in non-decreasing order of their weight
qsort(graph->edge, graph->E, sizeof(graph->edge[0]), compare);
// Allocate memory for creating V subsets
struct Subset* subsets = (struct Subset*)malloc(V * sizeof(struct Subset));
// Create V subsets with single elements
for (int v = 0; v < V; ++v) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
// Number of edges to be taken is V-1
while (e < V - 1 && graph->E > 0) {
// Step 2: Pick the smallest edge and increment the index for the next iteration
struct Edge next_edge = graph->edge[graph->E - 1];
graph->E--;
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
// If including this edge doesn't cause a cycle, include it in the result and increment the index
if (x != y) {
result[e++] = next_edge;
Union(subsets, x, y);
}
}
// Print the MST edges
printf("Edges in MST:\n");
for (int i = 0; i < e; ++i) {
printf("%d - %d Weight: %d\n", result[i].src, result[i].dest, result[i].weight);
}
free(subsets);
}
int main() {
int V = 4; // Number of vertices
int E = 5; // Number of edges
struct Graph* graph = createGraph(V, E);
// Example graph represented by source, destination, and weight of edges
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = 10;
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 6;
graph->edge[2].src = 0;
graph->edge[2].dest = 3;
graph->edge[2].weight = 5;
#include <stdio.h>
#include <limits.h>
#define V 9 // Number of vertices in the graph
// Function to find the vertex with the minimum distance value
int minDistance(int dist[], int visited[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++) {
if (visited[v] == 0 && dist[v] <= min) {
min = dist[v];
min_index = v;
}
}
return min_index;
}
// Function to print the constructed distance array
void printSolution(int dist[]) {
printf("Vertex \t Distance from Source\n");
for (int i = 0; i < V; i++) {
printf("%d \t %d\n", i, dist[i]);
}
}
// Function that implements Dijkstra's single source shortest path algorithm
void dijkstra(int graph[V][V], int src) {
int dist[V]; // The output array. dist[i] will hold the shortest distance from src to i
int visited[V]; // visited[i] will be true if vertex i is included in the shortest path tree or the shortest
// distance from src to i is finalized
for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
visited[i] = 0;
}
dist[src] = 0; // Distance of source vertex from itself is always 0
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, visited);
visited[u] = 1;
for (int v = 0; v < V; v++) {
if (!visited[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
printSolution(dist);
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 100
// Structure for the stack
struct Stack {
int top;
unsigned capacity;
char* array;
};
// Function to create a stack
struct Stack* createStack(unsigned capacity) {
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array = (char*)malloc(stack->capacity * sizeof(char));
return stack;
}
// Function to check if the stack is empty
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}
// Function to push an element onto the stack
void push(struct Stack* stack, char op) {
stack->array[++stack->top] = op;
}
// Function to pop an element from the stack
char pop(struct Stack* stack) {
if (!isEmpty(stack)) {
return stack->array[stack->top--];
}
return '$';
}
// Function to get the top element of the stack without popping it
char peek(struct Stack* stack) {
if (!isEmpty(stack)) {
return stack->array[stack->top];
}
return '$';
}
// Function to check if a character is an operator
int isOperator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^');
}
// Function to determine the precedence of an operator
int precedence(char op) {
if (op == '^')
return 3;
else if (op == '*' || op == '/')
return 2;
else if (op == '+' || op == '-')
return 1;
else
return -1;
}
// Function to convert infix expression to postfix expression
void infixToPostfix(char* infix, char* postfix) {
struct Stack* stack = createStack(strlen(infix));
if (!stack) return;
int k = 0;
for (int i = 0; infix[i] != '\0'; ++i) {
if (isalnum(infix[i])) {
postfix[k++] = infix[i];
} else if (infix[i] == '(') {
push(stack, infix[i]);
} else if (infix[i] == ')') {
while (!isEmpty(stack) && peek(stack) != '(') {
postfix[k++] = pop(stack);
}
if (!isEmpty(stack) && peek(stack) != '(') {
printf("Invalid expression\n");
return;
} else {
pop(stack);
}
} else { // Operator encountered
while (!isEmpty(stack) && precedence(infix[i]) <= precedence(peek(stack))) {
postfix[k++] = pop(stack);
}
push(stack, infix[i]);
}
}
// Pop remaining operators from the stack
while (!isEmpty(stack)) {
postfix[k++] = pop(stack);
}
postfix[k] = '\0';
}
// Function to convert infix expression to prefix expression
void infixToPrefix(char* infix, char* prefix) {
struct Stack* stack = createStack(strlen(infix));
if (!stack) return;
int k = 0;
for (int i = strlen(infix) - 1; i >= 0; i--) {
if (isalnum(infix[i])) {
prefix[k++] = infix[i];
} else if (infix[i] == ')') {
push(stack, infix[i]);
} else if (infix[i] == '(') {
while (!isEmpty(stack) && peek(stack) != ')') {
prefix[k++] = pop(stack);
}
if (!isEmpty(stack) && peek(stack) != ')') {
printf("Invalid expression\n");
return;
} else {
pop(stack);
}
} else { // Operator encountered
while (!isEmpty(stack) && precedence(infix[i]) < = precedence(peek(stack))) {
prefix[k++] = pop(stack);
}
push(stack, infix[i]);
}
}
// Pop remaining operators from the stack
while (!isEmpty(stack)) {
prefix[k++] = pop(stack);
}
prefix[k] = '\0';
// Reverse the final prefix expression
int start = 0;
int end = k - 1;
char temp;
while (start < end) {
temp = prefix[start];
prefix[start] = prefix[end];
prefix[end] = temp;
start++;
end--;
}
}
int main() {
char infix[MAX_SIZE];
char prefix[MAX_SIZE];
char postfix[MAX_SIZE];
strcpy(infix, "a+b*(c^d-e)^(f+g*h)-i");
infixToPrefix(infix, prefix);
printf("Prefix expression: %s\n", prefix);
infixToPostfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);
return 0;
}