1

我已经编写了一个程序，在 UBUNTU 中使用 C 语言将中缀转换为后缀......但是我的程序无法正常工作，有人可以帮忙吗？我的程序如下

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

char op[50];

struct node
{
    char data;
    struct node *next;
} *l1=NULL;

void push(char x)         // pushes char into the linkedlist
{
    if(l1==NULL)
    {
        l1=(struct node *)malloc(sizeof(struct node));
        l1->data=x;
        l1->next=NULL;
    }
    else
    {
        struct node *p;
        p=(struct node *)malloc(sizeof(struct node));
        p->data=x;
        p->next=l1;
        l1=p;
    }
}

char pop()           // pops char outof linkedlist
{
    char c;
    struct node *p;
    if (l1==NULL)
    {
        printf("the stack is empty\n");
        // exit(1);
    }
    else
    {
        c=l1->data;
        p=l1->next;
        free (l1);
        l1=p;
    }
    return c;
}

void display(struct node *start)
{
    {
        int i=0;
        struct node *p;
        p=start;
        if(p==NULL)
            printf("Empty list");
        else
        {
            while(p!=NULL)
            {
                printf("%c->",p->data);
                p=p->next;
            }
            printf("NULL\n");
        }
    }
}


int prior(char s, char c)
{
    if ( c=='^' && s=='+' || s=='-' ||s=='/' || s=='*')
        return 1;
    else if( c=='*' || c=='/')
    {
        if(s=='+' || s=='-' )
            return 1;
        else
            return 0;
    }
    else if( c=='+' || c=='-' )
        return 0;
}

void cnvrt(char s[], int n)       // convert infix to postfix
{
    char g;
    int i,j,x;
    for(i=0,j=0;i<n;i++)
    {

        if (s[i]>='0'&&s[i]<='9' || s[i]>='a' && s[i]<='z'|| s[i]>='A' && s[i]<='Z')
        {
            op[j]=s[i];
            j++;
        }
        else if(s[i]=='(')
        {
            push(s[i]);
        }
        else if (s[i]=='+' || s[i]=='/' || s[i]=='-' || s[i]=='*' || s[i]=='^')
        {

            if( l1==NULL)
                push(s[i]);
            else if(l1->data=='(')
                push(s[i]);
            else if(prior(l1->data, s[i] )!=1)
                push(s[i]);
            else
            { op[j]=pop();
                j++;
                push(s[i]);
            }
        }
        else if(s[i]==')')
        {
            while(l1!=NULL && l1->data!='(')
            {
                op[j]=pop();
                j++;
            }
            g=pop();
        }
    }
    while(l1!=NULL)
    {
        op[j]=pop();
        j++;
        l1=l1->next;
    }
}


void main()
{
    int i,n;
    char c[50];
    printf(" enter the no of characters in infix string\n ");
    scanf("%d",&n);
    printf(" enter the infix string\n");
    //for(i=0;i<n;i++)
    scanf("%s",c);

    cnvrt(c,n);
    printf("the postfix string is \n");
    for(i=0;i<n;i++)
    {
        printf("%c",op[i]);
    }
}

答案中总是缺少一个运算符..它有时也会将 CORE DUMPED 作为输出，如果中缀包含 '(' ot ')' 那么它会在堆栈为空时给出输出......请帮助我一个学生，所以他们可能会在我的程序中出错。

4

2 回答 2

4

这段代码有很多问题，有的小，有的大。

MAJOR： 如果列表为空，pop()将返回一个不确定的字符（即它是未定义的行为）。

次要：无用的块范围display()

次要：未使用i的变量display()

MAJOR：在prior()开头的if从句是错误的。它看起来像这样：

if  ( c=='^' && s=='+' || s=='-' ||s=='/' || s=='*')

它应该如下所示：

if  ( c=='^' && (s=='+' || s=='-' ||s=='/' || s=='*'))

MAJOR：prior()存在不建立返回值的控制路径，因此该函数在这种情况下具有未定义的行为。见下文

int prior(char s, char c)
{
    if ( c=='^' && (s=='+' || s=='-' ||s=='/' || s=='*'))
        return 1;
    else if( c=='*' || c=='/')
    {
        if(s=='+' || s=='-' )
            return 1;
        else
            return 0;
    }
    else if( c=='+' || c=='-' )
        return 0;

    // ELSE NO RETURN VALUE SET; UNDEFINED BEHAVIOR
}

次要：在cnvrt()第一个子if句中几乎可以理解为密码学。它看起来像这样：

(s[i]>='0'&&s[i]<='9' || s[i]>='a' && s[i]<='z'|| s[i]>='A' && s[i]<='Z')

考虑将其更新为如下所示：

((s[i]>='0'&&s[i]<='9') || (s[i]>='a' && s[i]<='z') || (s[i]>='A' && s[i]<='Z'))

并感谢@cHao 对运算符优先级的推动。

MINOR：未使用Incnvrt()变量。x

非标准： void不是有效的返回类型main()。根据标准，main() 必须返回一个int. 虽然这可能适用于您的平台，但它不符合标准。

这些只是我在阅读代码时发现的东西，我推测修复它们将极大地帮助修复您的程序，尤其是标记为MAJOR的项目。如前所述，我无法运行它，所以我只能希望是这样。

于 2013-08-31T07:43:20.330 回答
3

这是工作修改：

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

char op[50];

struct node
{
    char data;
    struct node *next;
} *l1=NULL;

void push(char x)         // pushes char into the linkedlist
{
    if(l1==NULL)
    {
        l1=(struct node *)malloc(sizeof(struct node));
        l1->data=x;
        l1->next=NULL;
    }
    else
    {
        struct node *p;
        p=(struct node *)malloc(sizeof(struct node));
        p->data=x;
        p->next=l1;
        l1=p;
    }
}

char pop()           // pops char outof linkedlist
{
    char c;
    struct node *p;
    if (l1==NULL)
    {
        printf("the stack is empty\n");
        // exit(1);
    }
    else
    {
        c=l1->data;
        p=l1->next;
        free (l1);
        l1=p;
    }
    return c;
}

void display(struct node *start)
{
    {
        //int i=0;
        struct node *p;
        p=start;
        if(p==NULL)
            printf("Empty list");
        else
        {
            while(p!=NULL)
            {
                printf("%c->",p->data);
                p=p->next;
            }
            printf("NULL\n");
        }
    }
}


int prior(char s, char c)
{
    if ( (c=='^' && s=='+') || s=='-' ||s=='/' || s=='*')
        return 1;
    else if( c=='*' || c=='/')
    {
        if(s=='+' || s=='-' )
            return 1;
        else
            return 0;
    }
    else if( c=='+' || c=='-' )
        return 0;
  return -1;
}

void cnvrt(char s[], int n)       // convert infix to postfix
{
    //char g;
    int i,j;//,x;
    for(i=0,j=0;i<n;i++)
    {

        if ((s[i]>='0'&&s[i]<='9') || (s[i]>='a' && s[i]<='z')|| (s[i]>='A' && s[i]<='Z'))
        {
            op[j]=s[i];
            j++;
        }
        else if(s[i]=='(')
        {
            push(s[i]);
        }
        else if (s[i]=='+' || s[i]=='/' || s[i]=='-' || s[i]=='*' || s[i]=='^')
        {

            if( l1==NULL)
                push(s[i]);
            else if(l1->data=='(')
                push(s[i]);
            else if(prior(l1->data, s[i] )!=1)
                push(s[i]);
            else
            { op[j]=pop();
                j++;
                push(s[i]);
            }
        }
        else if(s[i]==')')
        {
            while(l1!=NULL && l1->data!='(')
            {
                op[j]=pop();
                j++;
            }
            pop();
        }
    }
    while(l1!=NULL)
    {
        op[j]=pop();
        j++;
    }
}


int main()
{
    int i,n;
    char c[50];
    printf(" enter the no of characters in infix string\n ");
    scanf("%d",&n);
    printf(" enter the infix string\n");
    //for(i=0;i<n;i++)
    scanf("%s",c);

    cnvrt(c,n);
    printf("the postfix string is \n");
    for(i=0;i<n;i++)
    {
        printf("%c",op[i]);
    }

    return 0;
}

您可以区分代码并找到修改，或查看@WhozCraig 的答案。那里和那里有一些小错误，但导致内存失败的错误是这部分：

    //127-132
    while(l1!=NULL)
    {
        op[j]=pop();
        j++;
        l1=l1->next;
    }

在调试器中：

> gcc code.c -Wall -g

> gdb -q a.exe
Reading symbols from a.exe...done.
(gdb) run
Starting program: a.exe
[New Thread 4000.0x524]
 enter the no of characters in infix string
 3
 enter the infix string
1+2

Program received signal SIGSEGV, Segmentation fault.
0x004016f9 in cnvrt (s=0x22fee6 "1+2", n=3) at code.c:131
131             l1=l1->next;
(gdb)
(gdb) p l1
$1 = (struct node *) 0x0
(gdb)

l1是NULL，所以l1->next会失败。你需要做到：

    while(l1!=NULL)
    {
        op[j]=pop();
        j++;
    }

pop()负责改变 的指针l1，然后当从最后一项完成时，它会指向NULL，然后访问l1->next将失败。

现在很少测试：

> a.exe
 enter the no of characters in infix string
 3
 enter the infix string
1+2
the postfix string is
12+
> a.exe
 enter the no of characters in infix string
 7
 enter the infix string
(1+3)*4
the postfix string is
13+4*
>
于 2013-08-31T07:53:00.903 回答