explaination

 avatar
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