Answer to Question #240343 in C for xyz

Question

Write a program to convert an infix expression into its equivalent prefix notation.

Answer 1

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>




struct Node { 
    int top; 
    int size;
    
    int* queue; 
}; 


struct Node* create(int max) 
{ 
    struct Node* list = (struct Node*)malloc(sizeof(struct Node)); 
    list->size = max; 
    list->top = -1; 
    list->queue = (int*)malloc(list->size * sizeof(int));
    return list; 
} 




int isFull(struct Node* node) 
{ 
    if(node->top == node->size - 1){
        printf("Fukk\n");
    }
    
    return node->top == node->size - 1; 
} 




int isEmpty(struct Node* list) 
{ 
    return list->top == -1; 
}


void push(struct Node* list, int data) 
{ 
    if (isFull(list)) 
        return; 
    list->queue[++list->top] = data; 
}




int pop(struct Node* list) 
{ 
    if (isEmpty(list)) 
        return INT_MIN; 
    return list->queue[list->top--]; 
} 


int peek(struct Node* list) 
{ 
    if (isEmpty(list)) 
        return INT_MIN; 
    return list->queue[list->top]; 
} 




int Operand(char c) 
{ 
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); 
} 




int prec(char c) 
{ 
    switch (c) 
    { 
    case '+': 
    case '-': 
        return 1; 


    case '*': 
    case '/': 
        return 2; 


    case '^': 
        return 3; 
    } 
    return -1; 
} 


 
int PostfixForm(char* text) 
{ 
    int x, y; 


      
    struct Node* list = create(strlen(text)); 
    if(!list)  
        return -1 ; 


    for (x = 0, y = -1; text[x]; ++x) 
    { 
         
        if (Operand(text[x])) 
            text[++y] = text[x]; 


        
        else if (text[x] == '(') 
            push(list, text[x]); 


         
        else if (text[x] == ')') 
        { 
            while (!isEmpty(list) && peek(list) != '(') 
                text[++y] = pop(list); 
            if (!isEmpty(list) && peek(list) != '(') 
                return -1;             
            else
                pop(list); 
        } 
        else 
        { 
            while (!isEmpty(list) && prec(text[x]) <= prec(peek(list))) 
                text[++y] = pop(list); 
            push(list, text[x]); 
        } 


    } 


 
    while (!isEmpty(list)) 
        text[++y] = pop(list); 


    text[++y] = '\0'; 
    
}


void reverseExpression(char *text){


    int len = strlen(text);
    int y = len, x=0;
    char temp[len];


    temp[y--]='\0';
    while(text[x]!='\0')
    {
        temp[y] = text[x];
        y--;
        x++;
    }
    strcpy(text,temp);
}
void bracketsExpression(char* text){
    int x = 0;
    while(text[x]!='\0')
    {
        if(text[x]=='(')
            text[x]=')';
        else if(text[x]==')')
            text[x]='(';
        x++;
    }
}
void InfixtoPrefix(char *text){


    int size = strlen(text);




    reverseExpression(text);
    
    bracketsExpression(text);
    
    PostfixForm(text);
    
    reverseExpression(text);
}


int main()
{    
    printf("Infix expression is: ");


    char string[] = "((a/b)+c)-(d+(e*f))"; 
    printf("%s\n",string);
    InfixtoPrefix(string); 


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


    return 0; 
}