infix to postfix using stacks as linked lists in C language

Question

I have written a program to convert infix to postfix using C language in UBUNTU...but my program is not working properly can any one help? MY PROGRAM IS AS FOLLOWS

#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]);
    }
}

Always one of the operators is missing in the answer..also it gives CORE DUMPED as output sometimes and if infix contains '(' ot ')' then it gives output as stack is empty...... Please help me I am a student so their might be mistakes in my program.

Answer 1

There are a number of issues in this code, some minor, some major.

MAJOR: pop() will return an indeterminate character (i.e. it is undefined behavior) if the list is empty.

MINOR: Useless block scope in display()

MINOR: Unused variable i in display()

MAJOR: In prior() the opening if clause is wrong. It looks like this:

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

It should look like this:

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

MAJOR: In prior() a control path exists that doesn't establish a return value, therefore the function has undefined behavior for that case. See below

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
}

MINOR: In cnvrt() the first if clause is near-cryptographic to understand. It looks like this:

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

Consider updating it to look like this:

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

and thanks to @cHao for the nudge on operator precedence.

MINOR: In cnvrt() variable x is unused.

NON-STANDARD: void is not a valid return type for main(). According to the standard, main() must return an int. While this may work on your platform, it isn't standard-compliant.

These are just the things I spotted while reading the code, and I'm speculating fixing them will greatly assist in fixing your program, especially the items tagged MAJOR. As-written I cannot run this so I can only hope this is the case.

Answer 2

Here is working modification:

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

You can diff the code and find the modifications, or see @WhozCraig answer. There are some small errors there and there but the one that cause the memory failer is this part:

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

in the debugger:

> 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 is NULL, so l1->next will fail. You need to make it:

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

pop() is responsible of changing the pointer of l1, then when it's done from the last item, it will points to NULL, then accessing l1->next will fail.

Few tests now:

> 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*
>