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)

Please take some time to refresh [how to ask good questions](http://stackoverflow.com/help/how-to-ask), as well as [this question checklist](https://codeblog.jonskeet.uk/2012/11/24/stack-overflow-question-checklist/). And don't forget how to create a [mcve], with emphasis on the *minimal* part. Lastly, if you haven't done it yet, then now is probably a very good time to learn how to use a debugger to step through your code. — Some programmer dude, Oct 28 '19 at 07:27
A few other hints in making your code better: Don't use global variables. If a variable is needed in multiple functions, pass it as an argument. Also in C you [don't need to (and really shouldn't) cast the result of `malloc`](https://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). And try to use consistent indentation, it will make the code much easier to read, understand and debug. — Some programmer dude, Oct 28 '19 at 07:30

score 0 · Answer 1 · answered Oct 29 '19 at 13:42

Here are my observations and amendments:

Received a warning about gets. Have used fgets instead.gets is dangerous as it may cause a buffer overflow.
Freed the storages allocated in the insert function.The presence of these locations were causing the duplication of results,when intoprefix was called.
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.
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.

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;
}

Infix to Prefix and Postfix conversion

1 Answers1