Infix to Prefix and Postfix conversion

Question

I'm writing code to convert Infix expression into Postfix and Prefix at the same time.

My problem is I haven't been able to convert into the prefix expression. In my intoprefix() I tried everything, but still the output will same as to the postfix.

Where if i input this expression

A+B

The expected output would be

Postfix expression is: AB+
Prefix expression is: +AB 

but my output is

Postfix expression is: AB+
Prefix expression is: AB+AB+

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

struct Stack{
char data;
struct Stack *next;
}*top = NULL, *pstart = NULL;

char str[50];

int main(int argc, char **argv){
printf("Enter infix expression: ");
gets(str);

printf("\n\nEquivalent postfix expression is: ");
intopostfix(str);

printf("\n\nEquivalent prefix expression is: ");
intoprefix(str);
printf("\n");
return 0;
}

/* function for insert operation */
void insert(char ch){

    struct Stack *ptr,*newNode;
    newNode = (struct Stack *)malloc(sizeof(struct Stack));
    newNode->next = NULL;
    newNode->data = ch;
    ptr = pstart;

    if(pstart == NULL){
    pstart = newNode;
    }
    else{
    while(ptr->next != NULL)
    ptr = ptr->next;
    ptr->next = newNode;
    }

}

/* function for push operation */
void push(char symbol){

    struct Stack *ptr;

        ptr = (struct Stack *)malloc(sizeof(struct Stack));
        ptr->data = symbol;

        if(top == NULL){
            top = ptr;
            ptr->next = NULL;
        }
        else{
            ptr->next = top;
            top = ptr;
    }
}

char pop(){

    struct Stack *ptr1;
    char ch1;

        if(top == NULL){
        printf("Stack underflow\n");
        return 0;
        }
        else{
            ptr1 = top;
            top = top->next;
            ch1 = ptr1->data;
            free(ptr1);
            ptr1 = NULL;
            return ch1;
        }
}

/* function for display display operation */
void displaypost(){

    struct Stack *temp;

        if(pstart == NULL)
            printf("");
        else{           
            temp = pstart;
        while(temp != NULL){
        printf("%c",temp->data);
        temp = temp->next;
        }
    }
}

/*function for precedence */
int precedence(char ch){

        if(ch   ==  '^'){
        return (5);
        }
        else if(ch == '*' || ch == '/'){
        return (4);
        }
        else if(ch == '+' || ch == '-'){
        return (3);
        }
        else{
        return (2);
        }
}
 /*function for converting infix to postfix */
void intopostfix(char str[]){

    int length;
    int index = 0;
    char symbol, temp;
    length = strlen(str);

    while(length > index)
    {
        symbol = str[index];

        switch(symbol){

        case '(':
        push(symbol);
        break;

        case ')':
        temp = pop();

        while(temp != '('){
        insert(temp);
        temp = pop();
        }

        break;

        case '^':
        case '+':
        case '-':
        case '*':
        case '/':

        if(top == NULL){
            push(symbol);
        }
        else{
        while(top != NULL && (precedence(top->data) >= precedence(symbol))){
            temp = pop();
            insert(temp);
            }
            push(symbol);
        }   
            break;
            default:
            insert(symbol);
         }
         index = index + 1;
    }
        while(top != NULL){
        temp = pop();
        insert(temp);
    }

        displaypost();
        return;
}
/*function to convert infix to prefix */
void intoprefix(char str[]){

    int length;
    int index = 0;
    char symbol, temp;
    length = strlen(str);

    while(length > index)
    {
        symbol = str[index];

        switch(symbol){

        case ')':
        temp = pop();
        break;

        case '(':
        push(symbol);


        while(temp != ')'){
        insert(temp);
        temp = pop();
        }

        break;

        case '+':
        case '-':
        case '*':
        case '/':
        case '^':

        if(top == NULL){
            push(symbol);
        }
        else{
        while(top != NULL && (precedence(top->data) <= precedence(symbol))){
            temp = pop();
            insert(temp);
            }
            push(symbol);
        }   
            break;
            default:
            insert(symbol);
         }
         index = index + 1;
    }
        while(top != NULL){
        temp = pop();
        insert(temp);
    }

        displaypost();
        return;
}

The program converts infix to postfix and prefix using linked lists (stacks)

Answer 1

Here are my observations and amendments:

1. Received a warning about gets. Have used fgets instead.gets is dangerous as it may cause a buffer overflow.
2. Freed the storages allocated in the insert function.The presence of these locations were causing the duplication of results,when intoprefix was called.

3. Since you already have an intopostfix function, I utilized the same to convert infix to prefix using the following algorithm. Please refer.

   Step 1:Reverse the infix expression. Note while reversing each ‘(‘ will become ‘)’ and each ‘)’ becomes ‘(‘.

   Step 2:Obtain the postfix expression of the modified expression.

   Step 3:Reverse the postfix expression.

4. Made main the owner of the arrays that store the input and results, thus avoiding the use of "global variables" and requiring me to pass these variables explicitly.

5. Removed the displaypost function from within intopostfix and am calling it from main.

   void insert(char ch);//no changes made
   void push(char symbol); //no changes made
   char pop(); //no changes made
   void displaypost(char * s);
   int precedence(char ch); //no changes made
   void intopostfix(char str[]); //removed the call to displaypost
   
   int main(int argc, char **argv){
     char str[50];
     char prefix_str[50];//store postfix str
     char postfix_str[50];//store prefix str
   
     printf("Enter infix expression: ");
     fgets(str,50,stdin);
     str[strlen(str)-1] = '\0';//overwrite newline char with NULL
   
     //reverse the original string and store in prefix_str
     int i,j;
   
     for(i = strlen(str)-1,j = 0;i >= 0;i--,j++){
       if(str[i] == '(')
         prefix_str[j] = ')';
       else if(str[i] == ')')
         prefix_str[j] = '(';
       else
         prefix_str[j] = str[i];
     }
     prefix_str[j] = '\0';
   
     //Print Post Fix
     printf("\n\nEquivalent postfix expression is: ");
     intopostfix(str);
     displaypost(postfix_str);
     printf("%s",postfix_str);
   
     //Print Prefix
     intopostfix(prefix_str);
     displaypost(prefix_str);
     //reverse prefix_str
     int temp;
     for(i = 0,j = strlen(prefix_str)-1;i < j;i++,j--){
       temp = prefix_str[i];
       prefix_str[i] = prefix_str[j];
       prefix_str[j] = temp;
     }
     printf("\n\nEquivalent prefix expression is: ");
     printf("%s\n",prefix_str);
     printf("\n");
     return 0;
   }
   
   //changes in displaypost
   void displaypost(char * s){
     struct Stack *temp,*p;
     if(pstart == NULL)
       printf("");
     else{           
       temp = pstart;
       int i = 0;
       while(temp != NULL){
       p = temp;
       s[i] = temp->data;//store character in array
       temp = temp->next;
       free(p);//free storage
       i++;
       }
       s[i] = '\0';
     }
     pstart = NULL;
   }