Answer to Question #233843 in C for SOM

Question

· WAP to convert an infix expression into its equivalent prefix notation.

Answer 1

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




struct Node { 
    int cap; 
    int size;
   
    int* arr; 
}; 


struct Node* create(int data) 
{ 
    struct Node* head= (struct Node*)malloc(sizeof(struct Node)); 
    head->size = data; 
    head->cap = -1; 
    head->arr = (int*)malloc(head->size * sizeof(int));
    return head; 
} 


int isFull(struct Node* head) 
{ 
    if(head->cap == head->size - 1){
        printf("Not available\n");
    }
   
    return head->cap == head->size - 1; 
} 




int isEmpty(struct Node* head) 
{ 
    return head->cap == -1; 
}




void push(struct Node* head, int data) 
{ 
    if (isFull(head)) 
        return; 
    head->arr[++head->cap] = data; 
}




int pop(struct Node* head) 
{ 
    if (isEmpty(head)) 
        return INT_MIN; 
    return head->arr[head->cap--]; 
} 


int peek(struct Node* head) 
{ 
    if (isEmpty(head)) 
        return INT_MIN; 
    return head->arr[head->cap]; 
} 


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




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


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


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


int Postfix(char* expr) 
{ 
    int x, y; 


    struct Node* head= create(strlen(expr)); 
    if(!head) 
        return -1 ; 


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


        else if (expr[x] == '(') 
            push(head, expr[x]); 


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


    } 


  
    while (!isEmpty(head)) 
        expr[++y] = pop(head); 


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


void reverseExpression(char *expression){


    int s = strlen(expression);
    int y= s, x=0;
    char tempNode[s];


    tempNode[y--]='\0';
    while(expression[x]!='\0')
    {
        tempNode[y] = expression[x];
        y--;
        x++;
    }
    strcpy(expression,tempNode);
}
void bracketExpression(char* sentence){
    int x = 0;
    while(sentence[x]!='\0')
    {
        if(sentence[x]=='(')
            sentence[x]=')';
        else if(sentence[x]==')')
            sentence[x]='(';
        x++;
    }
}
void Prefix(char *sentence){


    int size = strlen(sentence);


    reverseExpression(sentence);
    
    bracketExpression(sentence);
    Postfix(sentence);


    reverseExpression(sentence);
}
//Testing code
int main()
{    
    printf("The infix string to be converted to prefix is: ");


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


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


    return 0; 
}