Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
8.4 kB
0
Indexable
Never
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_SIZE 100

// Structure for stack
struct Stack {
    int top;
    int capacity;
    int* array;
};

// Function to create a stack
struct Stack* createStack(int capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->top = -1;
    stack->capacity = capacity;
    stack->array = (int*)malloc(stack->capacity * sizeof(int));
    return stack;
}

// Function to check if stack is empty
int isEmpty(struct Stack* stack) {
    return stack->top == -1;
}

// Function to check if stack is full
int isFull(struct Stack* stack) {
    return stack->top == stack->capacity - 1;
}

// Function to push an element to stack
void push(struct Stack* stack, int item) {
    if (isFull(stack)) {
        printf("Stack Overflow\n");
        return;
    }
    stack->array[++stack->top] = item;
}

// Function to pop an element from stack
int pop(struct Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack Underflow\n");
        return -1;
    }
    return stack->array[stack->top--];
}

// Function to evaluate prefix expression
int evaluatePrefix(char* expression) {
    struct Stack* stack = createStack(MAX_SIZE);
    int length = strlen(expression);
    
    for (int i = length - 1; i >= 0; i--) {
        if (isdigit(expression[i])) {
            push(stack, expression[i] - '0');
        } else {
            int operand1 = pop(stack);
            int operand2 = pop(stack);
            
            switch (expression[i]) {
                case '+':
                    push(stack, operand1 + operand2);
                    break;
                case '-':
                    push(stack, operand1 - operand2);
                    break;
                case '*':
                    push(stack, operand1 * operand2);
                    break;
                case '/':
                    push(stack, operand1 / operand2);
                    break;
                case '%':
                    push(stack, operand1 % operand2);
                    break;
            }
        }
    }
    
    return pop(stack);
}

// Function to evaluate postfix expression
int evaluatePostfix(char* expression) {
    struct Stack* stack = createStack(MAX_SIZE);
    int length = strlen(expression);
    
    for (int i = 0; i < length; i++) {
        if (isdigit(expression[i])) {
            push(stack, expression[i] - '0');
        } else {
            int operand2 = pop(stack);
            int operand1 = pop(stack);
            
            switch (expression[i]) {
                case '+':
                    push(stack, operand1 + operand2);
                    break;
                case '-':
                    push(stack, operand1 - operand2);
                    break;
                case '*':
                    push(stack, operand1 * operand2);
                    break;
                case '/':
                    push(stack, operand1 / operand2);
                    break;
                case '%':
                    push(stack, operand1 % operand2);
                    break;
            }
        }
    }
    
    return pop(stack);
}

int main() {
    struct Stack* undoStack = createStack(MAX_SIZE);
    struct Stack* redoStack = createStack(MAX_SIZE);
    int choice;
    
    do {
        printf("\n---- Expression Evaluation ----\n");
        printf("1. Evaluate Expressions\n");
        printf("2. Undo/Redo\n");
        printf("3. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);
        
        switch (choice) {
            case 1:
                char prefixExpression[MAX_SIZE];
                char postfixExpression[MAX_SIZE];
                
                printf("\nEnter Prefix Expression: ");
                getchar();
                fgets(prefixExpression, sizeof(prefixExpression), stdin);
                prefixExpression[strcspn(prefixExpression, "\n")] = '\0';
                
                printf("Enter Postfix Expression: ");
                fgets(postfixExpression, sizeof(postfixExpression), stdin);
                postfixExpression[strcspn(postfixExpression, "\n")] = '\0';
                
                int prefixResult = evaluatePrefix(prefixExpression);
                int postfixResult = evaluatePostfix(postfixExpression);
                
                printf("\nPrefix Expression Result: %d\n", prefixResult);
                printf("Postfix Expression Result: %d\n", postfixResult);
                
                // Push the expressions and results to undo stack
                push(undoStack, prefixResult);
                push(undoStack, postfixResult);
                push(undoStack, strlen(prefixExpression));
                push(undoStack, strlen(postfixExpression));
                for (int i = strlen(prefixExpression) - 1; i >= 0; i--) {
                    push(undoStack, prefixExpression[i]);
                }
                for (int i = strlen(postfixExpression) - 1; i >= 0; i--) {
                    push(undoStack, postfixExpression[i]);
                }
                break;
                
            case 2:
                int undoStackEmpty = isEmpty(undoStack);
                int redoStackEmpty = isEmpty(redoStack);
                
                if (!undoStackEmpty) {
                    // Move the top 4 elements from undo stack to redo stack
                    for (int i = 0; i < 4; i++) {
                        push(redoStack, pop(undoStack));
                    }
                    
                    // Retrieve the expressions and results from undo stack
                    int undoPostfixResult = pop(undoStack);
                    int undoPrefixResult = pop(undoStack);
                    int undoPostfixLength = pop(undoStack);
                    int undoPrefixLength = pop(undoStack);
                    
                    // Retrieve the expressions from undo stack and print them
                    char undoPrefixExpression[MAX_SIZE];
                    for (int i = undoPrefixLength - 1; i >= 0; i--) {
                        undoPrefixExpression[i] = pop(undoStack);
                    }
                    undoPrefixExpression[undoPrefixLength] = '\0';
                    printf("\nUndo Prefix Expression: %s\n", undoPrefixExpression);
                    
                    char undoPostfixExpression[MAX_SIZE];
                    for (int i = undoPostfixLength - 1; i >= 0; i--) {
                        undoPostfixExpression[i] = pop(undoStack);
                    }
                    undoPostfixExpression[undoPostfixLength] = '\0';
                    printf("Undo Postfix Expression: %s\n", undoPostfixExpression);
                    
                    // Evaluate the expressions and print the results
                    int undoPrefixResultNew = evaluatePrefix(undoPrefixExpression);
                    int undoPostfixResultNew = evaluatePostfix(undoPostfixExpression);
                    printf("Undo Prefix Expression Result: %d\n", undoPrefixResultNew);
                    printf("Undo Postfix Expression Result: %d\n", undoPostfixResultNew);
                    
                    // Push the expressions and results to redo stack
                    push(redoStack, undoPrefixResultNew);
                    push(redoStack, undoPostfixResultNew);
                    push(redoStack, undoPrefixLength);
                    push(redoStack, undoPostfixLength);
                    for (int i = 0; i < undoPrefixLength; i++) {
                        push(redoStack, undoPrefixExpression[i]);
                    }
                    for (int i = 0; i < undoPostfixLength; i++) {
                        push(redoStack, undoPostfixExpression[i]);
                    }
                } else {
                    printf("\nUndo stack is empty. Cannot undo.\n");
                }
                break;
                
            case 3:
                printf("\nExiting...\n");
                break;
                
            default:
                printf("\nInvalid choice. Please try again.\n");
        }
    } while (choice != 3);

    return 0;
}