explaination
unknown
plain_text
6 months ago
13 kB
8
Indexable
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #define MAX 100 // Function to convert prefix to infix char* prefixToInfix(const char* prefix) { char stack[MAX][MAX]; // Stack to hold intermediate infix expressions int top = -1; // Stack pointer int length = strlen(prefix); // Traverse the prefix expression from right to left for (int i = length - 1; i >= 0; i--) { char current = prefix[i]; // If the character is an operand, push it to the stack if (isalnum(current)) { char temp[2] = {current, '\0'}; strcpy(stack[++top], temp); } else { // The character is an operator, pop two operands from the stack char operand1[MAX], operand2[MAX]; strcpy(operand1, stack[top--]); strcpy(operand2, stack[top--]); // Form the infix expression char temp[MAX]; sprintf(temp, "%s%c%s", operand1, current, operand2); strcpy(stack[++top], temp); } } // The final element in the stack is the complete infix expression return strdup(stack[top]); } int main() { char prefix[MAX]; // Read prefix expression from user printf(""); scanf("%s", prefix); // Convert prefix to infix char* infixResult = prefixToInfix(prefix); printf("%s\n", infixResult); // Clean up free(infixResult); return 0; } ------------------------------------------------------- #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #define MAX 100 // Maximum size for the stack and expression // Stack structure definition typedef struct { char items[MAX]; // Array to hold stack items int top; // Index of the top item in the stack } Stack; // Function to initialize the stack void initStack(Stack *s) { s->top = -1; // Set top to -1 to indicate an empty stack } // Function to check if the stack is empty int isEmpty(Stack *s) { return s->top == -1; // Returns 1 if empty, otherwise 0 } // Function to push an item onto the stack void push(Stack *s, char item) { if (s->top < MAX - 1) { // Check for stack overflow s->items[++s->top] = item; // Increment top and add item } else { printf("Stack Overflow\n"); // Error message for overflow } } // Function to pop an item from the stack char pop(Stack *s) { if (!isEmpty(s)) { // Check for stack underflow return s->items[s->top--]; // Return top item and decrement top } else { printf("Stack Underflow\n"); // Error message for underflow return '\0'; // Return null character on underflow } } // Function to peek at the top item of the stack without removing it char peek(Stack *s) { if (!isEmpty(s)) { return s->items[s->top]; // Return the top item } return '\0'; // Return null character if the stack is empty } // Function to determine the precedence of operators int precedence(char op) { switch (op) { case '+': case '-': return 1; // Low precedence for + and - case '*': case '/': return 2; // High precedence for * and / default: return 0; // Non-operator has lowest precedence } } // Function to check if a character is an operator int isOperator(char c) { return c == '+' || c == '-' || c == '*' || c == '/'; // Return 1 if operator, else 0 } // Function to convert infix expression to postfix void infixToPostfix(const char *infix, char *postfix) { Stack s; // Declare a stack for operators initStack(&s); // Initialize the stack int j = 0; // Index for postfix expression // Traverse each character in the infix expression for (int i = 0; infix[i] != '\0'; i++) { char token = infix[i]; // Current character // If the character is an operand, add it to the postfix expression if (isalnum(token)) { postfix[j++] = token; // Add operand to postfix } // If the character is an operator else if (isOperator(token)) { // Pop from the stack to the postfix expression until the top of the stack has an operator of lower precedence while (!isEmpty(&s) && precedence(peek(&s)) >= precedence(token)) { postfix[j++] = pop(&s); // Pop operator from stack to postfix } push(&s, token); // Push the current operator onto the stack } } // Pop all remaining operators from the stack to the postfix expression while (!isEmpty(&s)) { postfix[j++] = pop(&s); // Pop remaining operators } postfix[j] = '\0'; // Null-terminate the postfix string } int main() { char infix[MAX], postfix[MAX]; // Arrays to hold infix and postfix expressions printf("Enter infix expression: "); // Prompt user for input scanf("%s", infix); // Read infix expression from user infixToPostfix(infix, postfix); // Convert infix to postfix printf("Postfix expression: %s\n", postfix); // Output the postfix expression return 0; // End of the program } _________________________________________ #include <stdio.h> #include <stdlib.h> // Structure to represent a MinHeap typedef struct { int *arr; // Pointer to an array to hold heap elements int size; // Current number of elements in the heap int capacity; // Maximum number of elements the heap can hold } MinHeap; // Function to create a MinHeap with a given capacity MinHeap* createMinHeap(int capacity) { MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap)); // Allocate memory for the heap heap->capacity = capacity; // Set the maximum capacity heap->size = 0; // Initialize size to 0 (empty heap) heap->arr = (int*)malloc(capacity * sizeof(int)); // Allocate memory for the array return heap; // Return the created heap } // Function to swap two integers void swap(int *a, int *b) { int temp = *a; // Temporarily store the value of a *a = *b; // Assign the value of b to a *b = temp; // Assign the stored value to b } // Function to insert a new key into the MinHeap void insert(MinHeap *heap, int key) { if (heap->size == heap->capacity) { // Check if the heap is full printf("Heap is full\n"); // Print error message if full return; // Exit the function } heap->arr[heap->size] = key; // Add the new key at the end of the heap heap->size++; // Increment the size of the heap int i = heap->size - 1; // Index of the newly added element // Bubble up the new element to maintain the heap property while (i != 0 && heap->arr[(i - 1) / 2] > heap->arr[i]) { swap(&heap->arr[i], &heap->arr[(i - 1) / 2]); // Swap with parent i = (i - 1) / 2; // Move up the tree } } // Function to maintain the heap property by bubbling down void minHeapify(MinHeap *heap, int idx) { int smallest = idx; // Start with the current index as the smallest int left = 2 * idx + 1; // Calculate the left child index int right = 2 * idx + 2; // Calculate the right child index // Check if the left child exists and is smaller than the current smallest if (left < heap->size && heap->arr[left] < heap->arr[smallest]) smallest = left; // Update smallest if left child is smaller // Check if the right child exists and is smaller than the current smallest if (right < heap->size && heap->arr[right] < heap->arr[smallest]) smallest = right; // Update smallest if right child is smaller // If the smallest is not the current index, swap and heapify down if (smallest != idx) { swap(&heap->arr[idx], &heap->arr[smallest]); // Swap with the smallest minHeapify(heap, smallest); // Recursively heapify the affected subtree } } // Function to delete a specific key from the MinHeap void deleteKey(MinHeap *heap, int key) { int idx; // Variable to hold the index of the key // Search for the key in the heap for (idx = 0; idx < heap->size; idx++) { if (heap->arr[idx] == key) { break; // Key found } } // If the key was not found, print an error message if (idx == heap->size) { printf("Key not found\n"); return; // Exit the function } // Swap the key with the last element and reduce the size swap(&heap->arr[idx], &heap->arr[heap->size - 1]); // Swap with last element heap->size--; // Reduce the size of the heap minHeapify(heap, idx); // Restore the heap property } // Function to print the elements of the heap in level order void levelOrder(MinHeap *heap) { for (int i = 0; i < heap->size; i++) { printf("%d ", heap->arr[i]); // Print each element } printf("\n"); // New line after printing all elements } // Main function to execute the program int main() { MinHeap* heap = createMinHeap(100); // Create a MinHeap with capacity 100 char command[20]; // Buffer to hold user commands int value; // Variable to hold input values // Loop to continuously read user commands while (1) { // Read a line of input if (fgets(command, sizeof(command), stdin) == NULL) { break; // Exit if input fails } // Exit if the input is just a newline if (command[0] == '\n') { break; } // Parse the command for insertion if (sscanf(command, "insert %d", &value) == 1) { insert(heap, value); // Insert the value into the heap } // Parse the command for deletion else if (sscanf(command, "delete %d", &value) == 1) { deleteKey(heap, value); // Delete the value from the heap } } levelOrder(heap); // Print the heap in level order free(heap->arr); // Free the memory allocated for the array free(heap); // Free the memory allocated for the heap structure return 0; // End of the program } ____--------------------------------------------- #include <stdio.h> #include <stdlib.h> #define MAX_VERTICES 100 // Define the maximum number of vertices 7 typedef struct { int data[MAX_VERTICES]; // Array to hold queue elements int front, rear; // Indices for the front and rear of the queue } Queue; // Function to initialize the queue void initQueue(Queue *q) { q->front = 0; // Set front index to 0 q->rear = 0; // Set rear index to 0 } // Function to check if the queue is empty int isEmpty(Queue *q) { return q->front == q->rear; // Return true if front equals rear } // Function to add an element to the queue void enqueue(Queue *q, int value) { q->data[q->rear++] = value; // Add value at rear and increment rear } // Function to remove and return an element from the queue int dequeue(Queue *q) { return q->data[q->front++]; // Return the front value and increment front } // Function to perform BFS on a graph represented by an adjacency matrix void bfs(int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES], int m) { int visited[MAX_VERTICES] = {0}; // Array to track visited vertices Queue q; // Declare a queue for BFS initQueue(&q); // Initialize the queue visited[0] = 1; // Mark the first vertex as visited enqueue(&q, 0); // Enqueue the first vertex // Loop until the queue is empty while (!isEmpty(&q)) { int currentVertex = dequeue(&q); // Dequeue the front vertex printf("%d ", currentVertex + 1); // Print the vertex (1-indexed) // Explore all adjacent vertices for (int j = 0; j < m; j++) { // If there is an edge and the vertex hasn't been visited if (adjacencyMatrix[currentVertex][j] == 1 && !visited[j]) { visited[j] = 1; // Mark the vertex as visited enqueue(&q, j); // Enqueue the vertex } } } } // Main function int main() { int m; // Number of vertices int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES]; // Adjacency matrix for the graph // Prompt user to enter the number of vertices printf("Enter number of vertices: "); scanf("%d", &m); // Read the number of vertices // Prompt user to enter the adjacency matrix printf("Enter the adjacency matrix:\n"); for (int i = 0; i < m; i++) { // Loop through each row for (int j = 0; j < m; j++) { // Loop through each column scanf("%d", &adjacencyMatrix[i][j]); // Read each element of the matrix } } // Call the BFS function and print the traversal order printf("BFS traversal: "); bfs(adjacencyMatrix, m); // Perform BFS printf("\n"); // Print a new line after the traversal return 0; // End of the program }
Editor is loading...
Leave a Comment