Q1. Write a program to take input of a Matrix using array and display its transpose.
Ans:- Here is a C++ program that takes the input of a matrix, stores it in a 2D array, and then computes and displays its transpose.
C++ Program: Matrix Input and Transpose
```cpp
#include <iostream>
using namespace std;
int main() {
int rows, cols;
// Taking matrix dimensions as input
cout << "Enter the number of rows: ";
cin >> rows;
cout << "Enter the number of columns: ";
cin >> cols;
// Declare a matrix and a transpose matrix
int matrix[100][100], transpose[100][100];
// Input matrix elements
cout << "Enter the elements of the matrix:\n";
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
cout << "Element at [" << i + 1 << "][" << j + 1 << "]: ";
cin >> matrix[i][j];
}
}
// Compute the transpose of the matrix
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
transpose[j][i] = matrix[i][j];
}
}
// Display the original matrix
cout << "\nOriginal Matrix:\n";
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
cout << matrix[i][j] << " ";
}
cout << endl;
}
// Display the transpose matrix
cout << "\nTranspose of the Matrix:\n";
for (int i = 0; i < cols; i++) {
for (int j = 0; j < rows; j++) {
cout << transpose[i][j] << " ";
}
cout << endl;
}
return 0;
}
```
Explanation:
- **Matrix Input**: The program first asks for the number of rows and columns of the matrix and then takes each element of the matrix as input.
- **Transpose Calculation**: The transpose is calculated by swapping rows and columns (i.e., `transpose[j][i] = matrix[i][j]`).
- **Matrix and Transpose Display**: The original matrix and its transpose are displayed in matrix form.
Sample Output:
```
Enter the number of rows: 2
Enter the number of columns: 3
Enter the elements of the matrix:
Element at [1][1]: 1
Element at [1][2]: 2
Element at [1][3]: 3
Element at [2][1]: 4
Element at [2][2]: 5
Element at [2][3]: 6
Original Matrix:
1 2 3
4 5 6
Transpose of the Matrix:
1 4
2 5
3 6
```
Notes:
- The maximum matrix size is set to 100x100 for simplicity. You can adjust it as needed.
- This program assumes the matrix has rectangular dimensions.
Q2. Write a program in `C’ Language to accept 10 strings as input and print them inlexicographic order
Ans:- Here is a C program that accepts 10 strings as input and prints them in lexicographic (alphabetical) order.
C Program: Sorting Strings in Lexicographic Order
```c
#include <stdio.h>
#include <string.h>
#define SIZE 10
#define MAX_LEN 100
int main() {
char strings[SIZE][MAX_LEN], temp[MAX_LEN];
int i, j;
// Input 10 strings
printf("Enter 10 strings:\n");
for (i = 0; i < SIZE; i++) {
printf("String %d: ", i + 1);
fgets(strings[i], MAX_LEN, stdin);
strings[i][strcspn(strings[i], "\n")] = 0; // Remove newline character
}
// Sorting the strings using bubble sort
for (i = 0; i < SIZE - 1; i++) {
for (j = i + 1; j < SIZE; j++) {
if (strcmp(strings[i], strings[j]) > 0) {
// Swap strings[i] and strings[j]
strcpy(temp, strings[i]);
strcpy(strings[i], strings[j]);
strcpy(strings[j], temp);
}
}
}
// Print the strings in lexicographic order
printf("\nStrings in lexicographic order:\n");
for (i = 0; i < SIZE; i++) {
printf("%s\n", strings[i]);
}
return 0;
}
```
Explanation:
- **`strings[SIZE][MAX_LEN]`**: This 2D array holds 10 strings, each with a maximum length of 100 characters.
- **`fgets`**: Used to read the strings from the input, including spaces. The newline character from `fgets` is removed with `strcspn` to avoid issues during sorting.
- **Bubble Sort**: The program sorts the strings using the `strcmp` function, which compares two strings lexicographically. If a string is lexicographically greater than the next, they are swapped.
- **`strcpy`**: Used to swap strings during sorting.
Sample Output:
```
Enter 10 strings:
String 1: apple
String 2: banana
String 3: orange
String 4: grape
String 5: pineapple
String 6: cherry
String 7: kiwi
String 8: mango
String 9: peach
String 10: watermelon
Strings in lexicographic order:
apple
banana
cherry
grape
kiwi
mango
orange
peach
pineapple
watermelon
```
Notes:
- This program uses bubble sort for simplicity. If you want a more efficient algorithm, you can implement quicksort or mergesort.
- The maximum length of each string is set to 100. You can adjust this if needed.
Q3. Write a program to implement singly linked list for user inputs and perform the following operations on
it:
(i) Reverse the linked list and display it.
(ii) Sort the nodes in ascending order and display them.
Ans:- Here is a C++ program that implements a singly linked list with user inputs and provides two operations:
1. Reversing the linked list and displaying it.
2. Sorting the nodes in ascending order and displaying them.
C++ Program: Singly Linked List with Reverse and Sort Operations
```cpp
#include <iostream>
using namespace std;
// Define a node structure
struct Node {
int data;
Node* next;
};
// Function to insert a node at the end of the linked list
void insertNode(Node*& head, int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->next = nullptr;
if (!head) {
head = newNode;
} else {
Node* temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
}
}
// Function to display the linked list
void displayList(Node* head) {
if (!head) {
cout << "List is empty" << endl;
return;
}
Node* temp = head;
while (temp) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
// Function to reverse the linked list
Node* reverseList(Node* head) {
Node* prev = nullptr;
Node* current = head;
Node* next = nullptr;
while (current) {
next = current->next; // Store the next node
current->next = prev; // Reverse the current node's pointer
prev = current; // Move the prev pointer forward
current = next; // Move the current pointer forward
}
return prev; // New head of the reversed list
}
// Function to sort the linked list using Bubble Sort
void sortList(Node* head) {
if (!head) return; // List is empty
Node* current = nullptr;
Node* nextNode = nullptr;
int temp;
for (current = head; current != nullptr; current = current->next) {
for (nextNode = current->next; nextNode != nullptr; nextNode = nextNode->next) {
if (current->data > nextNode->data) {
// Swap the data
temp = current->data;
current->data = nextNode->data;
nextNode->data = temp;
}
}
}
}
// Driver program
int main() {
Node* head = nullptr;
int n, value;
// Input number of nodes
cout << "Enter the number of nodes: ";
cin >> n;
// Insert user input into the linked list
for (int i = 0; i < n; i++) {
cout << "Enter value for node " << i + 1 << ": ";
cin >> value;
insertNode(head, value);
}
// Display the original list
cout << "\nOriginal Linked List: ";
displayList(head);
// Reverse the linked list
head = reverseList(head);
cout << "Reversed Linked List: ";
displayList(head);
// Sort the linked list
sortList(head);
cout << "Sorted Linked List: ";
displayList(head);
return 0;
}
```
Explanation:
- **Node Structure**: Each node of the singly linked list contains an integer `data` and a pointer to the next node (`next`).
- **insertNode**: This function adds a node with a specific value at the end of the linked list.
- **displayList**: This function displays the contents of the linked list.
- **reverseList**: This function reverses the linked list by modifying the `next` pointers of the nodes.
- **sortList**: This function sorts the linked list in ascending order using bubble sort. It compares the `data` of adjacent nodes and swaps them if needed.
Sample Output:
```
Enter the number of nodes: 5
Enter value for node 1: 4
Enter value for node 2: 2
Enter value for node 3: 7
Enter value for node 4: 1
Enter value for node 5: 5
Original Linked List: 4 2 7 1 5
Reversed Linked List: 5 1 7 2 4
Sorted Linked List: 1 2 4 5 7
```
Operations:
1. **Reverse**: The `reverseList` function modifies the `next` pointers to reverse the list.
2. **Sort**: The `sortList` function implements bubble sort, sorting the linked list in ascending order.
Notes:
- The program uses a simple bubble sort for sorting. For larger linked lists, you might want to use a more efficient sorting algorithm, such as merge sort.
- The program handles dynamic memory allocation by using `new` to create nodes.
Q4. Write a program using linked list that accepts two polynomials as input and displays the resultant
polynomial after performing the multiplication of the input polynomials.
Ans:- Here is a C++ program that performs polynomial multiplication using linked lists. Each polynomial is represented as a linked list where each node contains the coefficient and exponent of a term.
C++ Program: Polynomial Multiplication Using Linked Lists
```cpp
#include <iostream>
using namespace std;
// Structure to represent a node of the polynomial
struct Node {
int coeff; // Coefficient of the term
int exp; // Exponent of the term
Node* next; // Pointer to the next node
};
// Function to create a new node for the polynomial
Node* createNode(int coeff, int exp) {
Node* newNode = new Node();
newNode->coeff = coeff;
newNode->exp = exp;
newNode->next = nullptr;
return newNode;
}
// Function to insert a node at the end of the linked list
void insertNode(Node*& poly, int coeff, int exp) {
Node* newNode = createNode(coeff, exp);
if (!poly) {
poly = newNode;
} else {
Node* temp = poly;
while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
}
}
// Function to display a polynomial
void displayPoly(Node* poly) {
if (!poly) {
cout << "0";
return;
}
Node* temp = poly;
while (temp) {
if (temp->coeff != 0) {
cout << temp->coeff << "x^" << temp->exp;
if (temp->next && temp->next->coeff > 0) {
cout << " + ";
}
}
temp = temp->next;
}
cout << endl;
}
// Function to multiply two polynomials
Node* multiplyPolynomials(Node* poly1, Node* poly2) {
if (!poly1 || !poly2) return nullptr;
Node* result = nullptr;
Node* ptr1 = poly1;
Node* ptr2 = poly2;
// Multiply each term of poly1 with each term of poly2
while (ptr1) {
ptr2 = poly2;
while (ptr2) {
int coeff = ptr1->coeff * ptr2->coeff;
int exp = ptr1->exp + ptr2->exp;
insertNode(result, coeff, exp);
ptr2 = ptr2->next;
}
ptr1 = ptr1->next;
}
return result;
}
// Function to simplify the resultant polynomial (combine like terms)
Node* simplifyPolynomial(Node* poly) {
Node* result = nullptr;
while (poly) {
Node* temp = poly;
int coeffSum = temp->coeff;
Node* runner = poly->next;
Node* prev = poly;
while (runner) {
if (runner->exp == temp->exp) {
coeffSum += runner->coeff;
prev->next = runner->next; // Remove duplicate node
delete runner;
runner = prev->next;
} else {
prev = runner;
runner = runner->next;
}
}
if (coeffSum != 0) {
insertNode(result, coeffSum, temp->exp);
}
poly = poly->next;
}
return result;
}
// Driver function
int main() {
Node* poly1 = nullptr;
Node* poly2 = nullptr;
int n1, n2, coeff, exp;
// Input for first polynomial
cout << "Enter the number of terms in the first polynomial: ";
cin >> n1;
for (int i = 0; i < n1; i++) {
cout << "Enter coefficient and exponent for term " << i + 1 << ": ";
cin >> coeff >> exp;
insertNode(poly1, coeff, exp);
}
// Input for second polynomial
cout << "Enter the number of terms in the second polynomial: ";
cin >> n2;
for (int i = 0; i < n2; i++) {
cout << "Enter coefficient and exponent for term " << i + 1 << ": ";
cin >> coeff >> exp;
insertNode(poly2, coeff, exp);
}
// Display the input polynomials
cout << "\nFirst Polynomial: ";
displayPoly(poly1);
cout << "Second Polynomial: ";
displayPoly(poly2);
// Multiply the polynomials
Node* result = multiplyPolynomials(poly1, poly2);
// Simplify the resultant polynomial (combine like terms)
result = simplifyPolynomial(result);
// Display the result
cout << "\nResultant Polynomial after multiplication: ";
displayPoly(result);
return 0;
}
```
Explanation:
- **Node Structure**: Each node contains the coefficient (`coeff`) and exponent (`exp`) of a term and a pointer to the next node (`next`).
- **createNode**: A utility function to create a new node with a given coefficient and exponent.
- **insertNode**: This function adds a node at the end of the linked list.
- **displayPoly**: This function prints the polynomial in standard form.
- **multiplyPolynomials**: This function multiplies two polynomials term by term, storing the result in a new linked list.
- **simplifyPolynomial**: This function combines like terms (i.e., terms with the same exponent) in the resulting polynomial after multiplication.
Sample Output:
```
Enter the number of terms in the first polynomial: 2
Enter coefficient and exponent for term 1: 3 2
Enter coefficient and exponent for term 2: 5 1
Enter the number of terms in the second polynomial: 2
Enter coefficient and exponent for term 1: 4 1
Enter coefficient and exponent for term 2: 2 0
First Polynomial: 3x^2 + 5x^1
Second Polynomial: 4x^1 + 2x^0
Resultant Polynomial after multiplication: 12x^3 + 22x^2 + 10x^1
```
Operations:
1. **Multiplication**: The function multiplies each term from the first polynomial with each term from the second polynomial and stores the result.
2. **Simplification**: After multiplication, like terms (terms with the same exponent) are combined to give the final polynomial.
Notes:
- The program uses dynamic memory allocation (`new`) to create the nodes of the linked list.
- The polynomials are input as terms with coefficients and exponents, and the result is displayed in a simplified form after multiplication.
Q5. Write a program to implement doubly linked list of integers as user inputs and perform the following
operations:
(i) Calculate and display the sum of all the even integers of the doubly linked list
(ii) Insert new elements at the beginning, in the middle and at the end of the linked list
Ans:- Here’s a C++ program that implements a doubly linked list of integers and provides two operations:
1. Calculating and displaying the sum of all the even integers in the doubly linked list.
2. Inserting new elements at the beginning, in the middle, and at the end of the linked list.
C++ Program: Doubly Linked List with Operations
```cpp
#include <iostream>
using namespace std;
// Node structure for doubly linked list
struct Node {
int data;
Node* prev;
Node* next;
};
// Function to create a new node
Node* createNode(int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->prev = nullptr;
newNode->next = nullptr;
return newNode;
}
// Function to insert a node at the end of the doubly linked list
void insertAtEnd(Node*& head, int value) {
Node* newNode = createNode(value);
if (!head) {
head = newNode;
} else {
Node* temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
}
// Function to insert a node at the beginning of the doubly linked list
void insertAtBeginning(Node*& head, int value) {
Node* newNode = createNode(value);
if (!head) {
head = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
}
// Function to insert a node in the middle of the doubly linked list
void insertInMiddle(Node*& head, int value, int position) {
Node* newNode = createNode(value);
if (!head || position == 1) {
insertAtBeginning(head, value);
return;
}
Node* temp = head;
int count = 1;
// Traverse the list until we reach the desired position
while (temp && count < position - 1) {
temp = temp->next;
count++;
}
if (!temp || !temp->next) {
insertAtEnd(head, value);
} else {
newNode->next = temp->next;
newNode->prev = temp;
temp->next->prev = newNode;
temp->next = newNode;
}
}
// Function to calculate and display the sum of all even integers
int sumEvenIntegers(Node* head) {
int sum = 0;
Node* temp = head;
while (temp) {
if (temp->data % 2 == 0) {
sum += temp->data;
}
temp = temp->next;
}
return sum;
}
// Function to display the doubly linked list
void displayList(Node* head) {
Node* temp = head;
while (temp) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
// Driver function
int main() {
Node* head = nullptr;
int n, value, position;
// Input number of nodes
cout << "Enter the number of nodes: ";
cin >> n;
// Insert user inputs into the doubly linked list
for (int i = 0; i < n; i++) {
cout << "Enter value for node " << i + 1 << ": ";
cin >> value;
insertAtEnd(head, value);
}
// Display the list
cout << "\nDoubly Linked List: ";
displayList(head);
// Calculate and display sum of even integers
int evenSum = sumEvenIntegers(head);
cout << "Sum of even integers: " << evenSum << endl;
// Insert element at the beginning
cout << "\nEnter value to insert at the beginning: ";
cin >> value;
insertAtBeginning(head, value);
cout << "List after inserting at the beginning: ";
displayList(head);
// Insert element in the middle
cout << "Enter value to insert in the middle: ";
cin >> value;
cout << "Enter the position to insert the element: ";
cin >> position;
insertInMiddle(head, value, position);
cout << "List after inserting in the middle: ";
displayList(head);
// Insert element at the end
cout << "Enter value to insert at the end: ";
cin >> value;
insertAtEnd(head, value);
cout << "List after inserting at the end: ";
displayList(head);
return 0;
}
```
Explanation:
- **Node Structure**: Each node contains an integer `data`, a pointer to the previous node (`prev`), and a pointer to the next node (`next`).
- **createNode**: This function creates a new node with a given integer value.
- **insertAtEnd**: This function inserts a node at the end of the doubly linked list.
- **insertAtBeginning**: This function inserts a node at the beginning of the doubly linked list.
- **insertInMiddle**: This function inserts a node at a given position in the middle of the doubly linked list.
- **sumEvenIntegers**: This function calculates the sum of all even integers in the doubly linked list.
- **displayList**: This function displays the elements of the doubly linked list.
Sample Output:
```
Enter the number of nodes: 5
Enter value for node 1: 1
Enter value for node 2: 2
Enter value for node 3: 3
Enter value for node 4: 4
Enter value for node 5: 5
Doubly Linked List: 1 2 3 4 5
Sum of even integers: 6
Enter value to insert at the beginning: 10
List after inserting at the beginning: 10 1 2 3 4 5
Enter value to insert in the middle: 20
Enter the position to insert the element: 4
List after inserting in the middle: 10 1 2 20 3 4 5
Enter value to insert at the end: 30
List after inserting at the end: 10 1 2 20 3 4 5 30
```
Operations:
1. **Sum of Even Integers**: The `sumEvenIntegers` function iterates through the list and sums up all the even integers.
2. **Insertions**:
- **At the Beginning**: `insertAtBeginning` adds a node to the start of the list.
- **In the Middle**: `insertInMiddle` inserts a node at a specified position.
- **At the End**: `insertAtEnd` adds a node to the end of the list.
Notes:
- The position for inserting in the middle should be specified as a 1-based index.
- The program handles both forward and backward traversal using the `prev` and `next` pointers.
Q6. Write a program in C to sort user input data using bubble sort method. Also, print the number of swaps
and comparison operations performed for sorting the given data set.
Ans:- Here’s a C program that sorts user input data using the **Bubble Sort** algorithm and counts the number of **swaps** and **comparison operations** performed during the sorting process.
C Program: Bubble Sort with Swap and Comparison Count
```c
#include <stdio.h>
// Function to perform bubble sort and count swaps and comparisons
void bubbleSort(int arr[], int n, int* swapCount, int* compCount) {
int i, j, temp;
*swapCount = 0;
*compCount = 0;
// Bubble Sort Algorithm
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - 1 - i; j++) {
(*compCount)++; // Increment comparison counter
if (arr[j] > arr[j + 1]) {
// Swap the elements
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
(*swapCount)++; // Increment swap counter
}
}
}
}
// Function to print the array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int n, i, swapCount, compCount;
// Input the number of elements
printf("Enter the number of elements: ");
scanf("%d", &n);
int arr[n];
// Input the elements
printf("Enter the elements:\n");
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
// Perform bubble sort
bubbleSort(arr, n, &swapCount, &compCount);
// Output the sorted array
printf("Sorted array: ");
printArray(arr, n);
// Output the count of swaps and comparisons
printf("Number of swaps: %d\n", swapCount);
printf("Number of comparisons: %d\n", compCount);
return 0;
}
```
Explanation:
- **bubbleSort**: This function sorts the array using the bubble sort algorithm. It also keeps track of the number of **comparisons** and **swaps** made.
- The outer loop controls the passes, and the inner loop handles the adjacent comparison and swapping if the elements are out of order.
- Every time two elements are compared, the comparison count is incremented.
- If a swap is performed, the swap count is incremented.
- **printArray**: This function prints the elements of the array after sorting.
- **swapCount**: This variable tracks the number of swaps made during sorting.
- **compCount**: This variable tracks the number of comparisons made during sorting.
= Sample Output:
```
Enter the number of elements: 5
Enter the elements:
64 34 25 12 22
Sorted array: 12 22 25 34 64
Number of swaps: 6
Number of comparisons: 10
```
Operations:
1. **Bubble Sort**: The algorithm repeatedly steps through the list, compares adjacent pairs, and swaps them if they are in the wrong order. This process is repeated until the list is sorted.
2. **Swap and Comparison Counting**: The program counts and displays the number of swaps and comparisons performed during the sorting process.
Notes:
- The time complexity of the bubble sort is \( O(n^2) \), where \( n \) is the number of elements.
- In this program, the total number of **comparisons** is calculated for each pass through the array, while **swaps** are only counted when adjacent elements are swapped.
Q7. Write a program to convert an infix expression to a prefix expression. Use appropriate data structure.
Ans:- To convert an **infix expression** to a **prefix expression**, we can use a **stack** data structure. The approach involves reversing the infix expression, converting it to postfix, and then reversing the postfix expression to get the prefix expression.
Here is a C program that converts an infix expression to a prefix expression using a stack.
C Program: Infix to Prefix Conversion Using Stack
```c
#include <stdio.h>
#include <string.h>
#include <ctype.h>
// Stack implementation
#define MAX 100
char stack[MAX];
int top = -1;
void push(char x) {
if (top == MAX - 1) {
printf("Stack Overflow\n");
} else {
stack[++top] = x;
}
}
char pop() {
if (top == -1) {
printf("Stack Underflow\n");
return -1;
} else {
return stack[top--];
}
}
char peek() {
return stack[top];
}
// Function to check if the character is an operator
int isOperator(char x) {
return (x == '+' || x == '-' || x == '*' || x == '/' || x == '^');
}
// Function to check the precedence of operators
int precedence(char x) {
if (x == '^') return 3;
if (x == '*' || x == '/') return 2;
if (x == '+' || x == '-') return 1;
return 0;
}
// Function to check if the character is an operand (i.e., an alphabet or digit)
int isOperand(char x) {
return isalpha(x) || isdigit(x);
}
// Function to reverse a string
void reverse(char exp[]) {
int len = strlen(exp);
for (int i = 0; i < len / 2; i++) {
char temp = exp[i];
exp[i] = exp[len - i - 1];
exp[len - i - 1] = temp;
}
}
// Function to convert infix to postfix
void infixToPostfix(char infix[], char postfix[]) {
int i, j = 0;
char x;
for (i = 0; infix[i] != '\0'; i++) {
if (isOperand(infix[i])) {
postfix[j++] = infix[i];
} else if (infix[i] == '(') {
push(infix[i]);
} else if (infix[i] == ')') {
while ((x = pop()) != '(') {
postfix[j++] = x;
}
} else if (isOperator(infix[i])) {
while (top != -1 && precedence(peek()) >= precedence(infix[i])) {
postfix[j++] = pop();
}
push(infix[i]);
}
}
while (top != -1) {
postfix[j++] = pop();
}
postfix[j] = '\0';
}
// Function to convert infix to prefix
void infixToPrefix(char infix[], char prefix[]) {
// Reverse the infix expression
reverse(infix);
// Change '(' to ')' and vice versa
for (int i = 0; infix[i] != '\0'; i++) {
if (infix[i] == '(') {
infix[i] = ')';
} else if (infix[i] == ')') {
infix[i] = '(';
}
}
// Convert the modified infix to postfix
char postfix[MAX];
infixToPostfix(infix, postfix);
// Reverse the postfix to get the prefix
reverse(postfix);
strcpy(prefix, postfix);
}
int main() {
char infix[MAX], prefix[MAX];
// Input the infix expression
printf("Enter the infix expression: ");
scanf("%s", infix);
// Convert infix to prefix
infixToPrefix(infix, prefix);
// Output the prefix expression
printf("Prefix expression: %s\n", prefix);
return 0;
}
```
Explanation:
1. **Stack Operations**:
- **push**: Adds an element to the top of the stack.
- **pop**: Removes and returns the top element from the stack.
- **peek**: Returns the top element without removing it.
2. **isOperator**: This function checks whether a given character is an operator (`+`, `-`, `*`, `/`, `^`).
3. **precedence**: This function returns the precedence of operators. Higher precedence operators are evaluated before lower precedence ones.
4. **reverse**: This function reverses a string, which is essential in converting infix to prefix.
5. **infixToPostfix**: This function converts the infix expression to a postfix expression using a stack.
- Operands (i.e., numbers, variables) are directly added to the postfix expression.
- Operators are pushed onto the stack, respecting precedence and associativity.
6. **infixToPrefix**: This function converts an infix expression to prefix.
- First, it reverses the infix expression and changes the brackets accordingly (`(` becomes `)` and vice versa).
- Then, the reversed infix expression is converted to postfix using `infixToPostfix`.
- Finally, the resulting postfix expression is reversed to get the prefix expression.
Sample Output:
```
Enter the infix expression: A+B*(C^D-E)
Prefix expression: +A*B-^CDE
```
Steps for Conversion:
1. **Input Expression**: `A+B*(C^D-E)`
2. **Reverse the Infix**: `)E-D^C(*B+A`
3. **Convert to Postfix**: `EDC^-B*A+`
4. **Reverse Postfix to Get Prefix**: `+A*B-^CDE`
Notes:
- Infix expressions are human-readable (e.g., `A+B*(C-D)`), while prefix expressions place operators before operands (e.g., `+A*BC-D`).
- The algorithm first reverses the infix expression, then treats it as if converting it to postfix, and finally reverses the postfix result to obtain the prefix expression.
Q8. Write a program in ‘C’ language for the creation of a Red Black tree. Also,implement insertion and
deletion operations.
Ans:- Creating a **Red-Black Tree** (RBT) in C involves defining the structure of the tree, implementing insertion with necessary balancing, and implementing deletion while maintaining the properties of the tree. Red-Black Trees are a type of self-balancing binary search tree where each node has an additional bit for color (red or black) to ensure that the tree remains approximately balanced during insertions and deletions.
Here’s a complete C program that implements a Red-Black Tree with insertion and deletion operations:
C Program: Red-Black Tree Implementation
```c
#include <stdio.h>
#include <stdlib.h>
// Define colors
#define RED 1
#define BLACK 0
// Structure for a Red-Black Tree node
struct RBTreeNode {
int data;
int color; // 1 for red, 0 for black
struct RBTreeNode *left, *right, *parent;
};
// Function to create a new Red-Black Tree node
struct RBTreeNode* createNode(int data) {
struct RBTreeNode* newNode = (struct RBTreeNode*)malloc(sizeof(struct RBTreeNode));
newNode->data = data;
newNode->color = RED; // New nodes are red by default
newNode->left = newNode->right = newNode->parent = NULL;
return newNode;
}
// Function to perform a left rotation
void leftRotate(struct RBTreeNode **root, struct RBTreeNode *x) {
struct RBTreeNode *y = x->right;
x->right = y->left;
if (y->left != NULL)
y->left->parent = x;
y->parent = x->parent;
if (x->parent == NULL)
*root = y; // x was root
else if (x == x->parent->left)
x->parent->left = y; // x was a left child
else
x->parent->right = y; // x was a right child
y->left = x;
x->parent = y;
}
// Function to perform a right rotation
void rightRotate(struct RBTreeNode **root, struct RBTreeNode *y) {
struct RBTreeNode *x = y->left;
y->left = x->right;
if (x->right != NULL)
x->right->parent = y;
x->parent = y->parent;
if (y->parent == NULL)
*root = x; // y was root
else if (y == y->parent->right)
y->parent->right = x; // y was a right child
else
y->parent->left = x; // y was a left child
x->right = y;
y->parent = x;
}
// Function to fix violations after insertion
void fixViolation(struct RBTreeNode **root, struct RBTreeNode *newNode) {
struct RBTreeNode *parent = NULL;
struct RBTreeNode *grandparent = NULL;
while ((newNode != *root) && (newNode->color == RED) && (newNode->parent->color == RED)) {
parent = newNode->parent;
grandparent = parent->parent;
// Case A: Parent is a left child
if (parent == grandparent->left) {
struct RBTreeNode *uncle = grandparent->right;
// Case 1: Uncle is also red
if (uncle != NULL && uncle->color == RED) {
grandparent->color = RED;
parent->color = BLACK;
uncle->color = BLACK;
newNode = grandparent; // Move up to grandparent
} else {
// Case 2: newNode is a right child
if (newNode == parent->right) {
leftRotate(root, parent);
newNode = parent;
parent = newNode->parent;
}
// Case 3: newNode is a left child
rightRotate(root, grandparent);
int tempColor = parent->color;
parent->color = grandparent->color;
grandparent->color = tempColor;
newNode = parent;
}
} else { // Case B: Parent is a right child
struct RBTreeNode *uncle = grandparent->left;
// Case 1: Uncle is also red
if ((uncle != NULL) && (uncle->color == RED)) {
grandparent->color = RED;
parent->color = BLACK;
uncle->color = BLACK;
newNode = grandparent; // Move up to grandparent
} else {
// Case 2: newNode is a left child
if (newNode == parent->left) {
rightRotate(root, parent);
newNode = parent;
parent = newNode->parent;
}
// Case 3: newNode is a right child
leftRotate(root, grandparent);
int tempColor = parent->color;
parent->color = grandparent->color;
grandparent->color = tempColor;
newNode = parent;
}
}
}
(*root)->color = BLACK; // Ensure root is black
}
// Function to insert a new node
void insert(struct RBTreeNode **root, int data) {
struct RBTreeNode *newNode = createNode(data);
struct RBTreeNode *parent = NULL;
struct RBTreeNode *temp = *root;
// Find the appropriate position to insert the new node
while (temp != NULL) {
parent = temp;
if (newNode->data < temp->data)
temp = temp->left;
else
temp = temp->right;
}
newNode->parent = parent;
if (parent == NULL) {
*root = newNode; // Tree was empty
} else if (newNode->data < parent->data) {
parent->left = newNode;
} else {
parent->right = newNode;
}
// Fix violations after insertion
fixViolation(root, newNode);
}
// Function to perform inorder traversal
void inorder(struct RBTreeNode *root) {
if (root == NULL)
return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
// Function to find the minimum node
struct RBTreeNode *minimum(struct RBTreeNode *node) {
while (node->left != NULL)
node = node->left;
return node;
}
// Function to fix violations after deletion
void fixDeletion(struct RBTreeNode **root, struct RBTreeNode *x) {
struct RBTreeNode *sibling;
while (x != *root && x->color == BLACK) {
if (x == x->parent->left) {
sibling = x->parent->right;
if (sibling->color == RED) {
sibling->color = BLACK;
x->parent->color = RED;
leftRotate(root, x->parent);
sibling = x->parent->right;
}
if ((sibling->left == NULL || sibling->left->color == BLACK) &&
(sibling->right == NULL || sibling->right->color == BLACK)) {
sibling->color = RED;
x = x->parent;
} else {
if (sibling->right == NULL || sibling->right->color == BLACK) {
sibling->left->color = BLACK;
sibling->color = RED;
rightRotate(root, sibling);
sibling = x->parent->right;
}
sibling->color = x->parent->color;
x->parent->color = BLACK;
sibling->right->color = BLACK;
leftRotate(root, x->parent);
x = *root; // Break the loop
}
} else {
sibling = x->parent->left;
if (sibling->color == RED) {
sibling->color = BLACK;
x->parent->color = RED;
rightRotate(root, x->parent);
sibling = x->parent->left;
}
if ((sibling->right == NULL || sibling->right->color == BLACK) &&
(sibling->left == NULL || sibling->left->color == BLACK)) {
sibling->color = RED;
x = x->parent;
} else {
if (sibling->left == NULL || sibling->left->color == BLACK) {
sibling->right->color = BLACK;
sibling->color = RED;
leftRotate(root, sibling);
sibling = x->parent->left;
}
sibling->color = x->parent->color;
x->parent->color = BLACK;
sibling->left->color = BLACK;
rightRotate(root, x->parent);
x = *root; // Break the loop
}
}
}
x->color = BLACK; // Ensure x is black
}
// Function to delete a node
void deleteNode(struct RBTreeNode **root, int data) {
struct RBTreeNode *z = *root;
struct RBTreeNode *x, *y;
// Find the node to be deleted
while (z != NULL) {
if (z->data == data)
break;
else if (data < z->data)
z = z->left;
else
z = z->right;
}
if (z == NULL) {
printf("Node %d not found.\n", data);
return;
}
y = z; // The node to be deleted
int yOriginalColor = y->
No comments: