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: