Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.5 kB
1
Indexable
Never
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 100
struct Stack {
    char data[MAX_SIZE];
    int top;
};

void initialize(struct Stack *s) {
    s->top = -1;
}

int isEmpty(struct Stack *s) {
    return s->top == -1;
}
void push(struct Stack *s, char element) {
    if (s->top >= MAX_SIZE - 1) {
        printf("Stack Overflow\n");
        exit(1);
    }

    s->data[++s->top] = element;
}
char pop(struct Stack *s) {
    if (isEmpty(s)) {
        printf("Stack Underflow\n");
        exit(1);
    }

    return s->data[s->top--];
}
char peek(struct Stack *s) {
    if (isEmpty(s)) {
        printf("Stack Underflow\n");
        exit(1);
    }

    return s->data[s->top];
}
int isOperator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/');
}
int getPrecedence(char c) {
    if (c == '+' || c == '-')
        return 1;
    else if (c == '*' || c == '/')
        return 2;
    else
        return 0;
}

void infixToPrefix(char *infix, char *prefix) {
    struct Stack operatorStack;
    initialize(&operatorStack);
    int infixLen = strlen(infix);
    int prefixIdx = 0;

    for (int i = infixLen - 1; i >= 0; i--) {
        char current = infix[i];

        if (current == ' ')
            continue;

        if (isdigit(current) || isalpha(current)) {
            prefix[prefixIdx++] = current;
        } else if (current == ')') {
            push(&operatorStack, current);
        } else if (isOperator(current)) {
            while (!isEmpty(&operatorStack) && getPrecedence(peek(&operatorStack)) >= getPrecedence(current)) {
                prefix[prefixIdx++] = pop(&operatorStack);
            }
            push(&operatorStack, current);
        } else if (current == '(') {
            while (!isEmpty(&operatorStack) && peek(&operatorStack) != ')') {
                prefix[prefixIdx++] = pop(&operatorStack);
            }
            pop(&operatorStack); 
        }
    }

    while (!isEmpty(&operatorStack)) {
        prefix[prefixIdx++] = pop(&operatorStack);
    }

    prefix[prefixIdx] = '\0';

    int len = strlen(prefix);
    for (int i = 0; i < len / 2; i++) {
        char temp = prefix[i];
        prefix[i] = prefix[len - i - 1];
        prefix[len - i - 1] = temp;
    }
}

int main() {
    char infix[MAX_SIZE];
    char prefix[MAX_SIZE];

    printf("Enter the infix expression: ");
    fgets(infix, MAX_SIZE, stdin);
    infix[strlen(infix) - 1] = '\0'; 

    infixToPrefix(infix, prefix);

    printf("The prefix expression is: %s\n", prefix);

    return 0;
}