c - 中缀到前缀和后缀的转换

Question

我正在编写代码将 Infix 表达式同时转换为 Postfix 和 Prefix。

我的问题是我无法转换为前缀表达式。在我的 intoprefix() 中，我尝试了一切，但输出仍然与后缀相同。

如果我在哪里输入这个表达式

A+B

预期输出为

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

但我的输出是

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

程序使用链表(堆栈)将中缀转换为后缀和前缀

Answer 1

以下是我的观察和修正:

1. 收到有关 gets 的警告。已使用fgets反而。 gets是危险，因为它可能导致缓冲区溢出。
2. 释放 insert 中分配的存储空间功能.存在这些位置导致结果重复，当 intoprefix被叫到了。

3. 因为您已经有 intopostfix功能，我用了同样的转换infix至prefix使用以下算法。请 refer .

   第一步:反转中缀表达式。请注意，反转每个“(”时将变成‘)’，每个‘)’变成‘(‘。

   第二步:获取修改后的表达式的后缀表达式。

   第三步:反转后缀表达式。

4. 制造main存储输入和结果的数组的所有者，从而避免使用“全局变量”并要求我显式传递这些变量。

5. 删除了 displaypost从内部发挥作用intopostfix我是从 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;
   }