Untitled

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

#define MAX_SIZE 100

// Stack implementation
typedef struct {
    char items[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack* stack) {
    stack->top = -1;
}

int isEmpty(Stack* stack) {
    return stack->top == -1;
}

int isFull(Stack* stack) {
    return stack->top == MAX_SIZE - 1;
}

void push(Stack* stack, char item) {
    if (isFull(stack)) {
        printf("Stack Overflow\n");
        exit(EXIT_FAILURE);
    }
    stack->items[++stack->top] = item;
}

char pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack Underflow\n");
        exit(EXIT_FAILURE);
    }
    return stack->items[stack->top--];
}

char peek(Stack* stack) {
    return stack->items[stack->top];
}


int isOperator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^');
}


int getPrecedence(char c) {
    if (c == '^')
        return 3;
    else if (c == '*' || c == '/')
        return 2;
    else if (c == '+' || c == '-')
        return 1;
    else
        return 0;
}


void infixToPrefix(char* infix, char* prefix) {
    Stack stack;
    initStack(&stack);

    // Step 1: Push
    push(&stack, '(');
    strcat(infix, ")");

    int i, j = 0;
    for (i = 0; infix[i] != '\0'; i++) {
        char symbol = infix[i];

        if (symbol == ' ') {
            continue;
        } else if (symbol == '(') {
            push(&stack, symbol);
        } else if (symbol == ')') {
            // Step6
            while (peek(&stack) != '(') {
                prefix[j++] = pop(&stack);
            }
            pop(&stack); // Step 6(b
        } else if (isOperator(symbol)) {
            // Step 5:
            // Step 5(a):

            while (!isEmpty(&stack) && isOperator(peek(&stack)) && getPrecedence(peek(&stack)) >= getPrecedence(symbol)) {
                prefix[j++] = pop(&stack);
            }
            push(&stack, symbol); // Step 5(b):
        } else {
            // Step 4
            // Step 3
            prefix[j++] = symbol;
        }
    }

    prefix[j] = '\0';
}

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

    printf("Enter an infix expression: ");
    fgets(infix, MAX_SIZE, stdin);

    infixToPrefix(infix, prefix);

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

    return 0;
}