Infix to Postfix program not giving correct output

[Maxx]

I'm writing this program which converts a given infix expression to
postfix expression, store the postfix expression in array prints
it ,and then prints the sum. I have used link list to implement the
pushdown stack. The program gets compiled correctly but its not giving
correct output at all. Here is the program i wrote::

#include <stdio.h>
#include <ctype.h>
#define MAX 1000

int rev[MAX];
int *p=rev;
struct node
{
int key;
struct node *next;
};

struct node *head,*z,*t;

void stackinitze()
{
head=(struct node *)malloc(sizeof *head);
z=(struct node *)malloc(sizeof *z);
head->next=z;
head->key=0;
z->next=z;
}

void push(int v)
{
t=(struct node *)malloc(sizeof *t);
t->key=v;
t->next=head->next;
head->next=t;
}
int pop()
{
int x;
t=head->next;
head->next=t->next;
x=t->key;
free(t);
return x;
}

int main(int argc, char **argv)
{
int c=*argv[1],i=0,j=1;
for(stackinitze();--argc>0;c=*argv[j++])
{

if(c>='0' && c<='9')
*p++=(c-'0');
if(c=='+' || c=='*')
push((char)c);
if(c==')')
*p++=pop(c);
}*p='\0';
while((c=rev[i++])!='\0')
{
if(isdigit(c))
printf("%d",c);
else
printf("%c",c);
}
while((c=rev[i++])!='\0')
{
if(c>='0'&& c<='9')
push(c-'0');
if(c=='+')
push(pop()+pop());
if(c=='*')
push(pop()*pop());
}
printf("Result is %d",pop());
return 0;
}

The program gets compiled correctly but the output it just gibberish.

Here is the output::

rev_polish 5 * ( ( 9 + 7 ) + 7 )
5353424040574355414355 +Result is 43.

Please help, i can't find any headway around this.

 

[Ben Bacarisse]

I'm writing this program which converts a given infix expression to
postfix expression, store the postfix expression in array prints
it ,and then prints the sum. I have used link list to implement the
pushdown stack. The program gets compiled correctly but its not giving
correct output at all. Here is the program i wrote::

There are lots of aspects to programming: you need to code well, know
your algorithms and use the right data structures (these are only the
ones I'll comment on -- there are others).

First, your algorithm is wrong. If you are making this up, well done,
but you have not got it right yet. If you are implementing something
you've read about, you need to do more work on understanding it. What
you have looks like the start of Dijkstra's shunting yard algorithm (I
name it so you can look it up if you want to).

Below, I'll comment on coding and data structures.

#include <stdio.h>
#include <ctype.h>
#define MAX 1000

int rev[MAX];
int *p=rev;

These name are rather small for global variables. p in particular. As
it happens you don't need p to be global -- it should be local to the
function that needs it.

struct node
{
int key;
struct node *next;
};

struct node *head,*z,*t;

Ditto for z and t. 'head' is not a brilliant name either. What is it
the head of?

I'd probably want to use a list for both the value queue (what you call
'rev') and for the operator stack. Limiting one and not the other is
odd. Alternatively, using a fixed size array for both would make the
program very simple, though you should check if you are running out of
space.

void stackinitze()

int pop(void) is the modern way to write this. Ditto for pop() below.

{
head=(struct node *)malloc(sizeof *head);

There is no need for the cast. It just gets in the way of reading the
code. Also (more serious) malloc is not declared. You should to ask for
more warnings from your compiler and you should to follow up on what it
says.

Don't let yourself get into the habit of not checking function return
values.

z=(struct node *)malloc(sizeof *z);
head->next=z;
head->key=0;
z->next=z;
}

I'd expect nothing at all here. I certainly would not expect two
mallocs, one of which is used to make a circular list.

There is an oft-used technique where a list always has a dummy element,
but if you are using this, you have misunderstood it's purpose. With a
global 'head' pointer your list can be much simpler.

void push(int v)
{
t=(struct node *)malloc(sizeof *t);
t->key=v;
t->next=head->next;
head->next=t;
}

't' should be local. You could use 'head' instead of 'head->next'.

int pop()
{
int x;
t=head->next;
head->next=t->next;
x=t->key;
free(t);
return x;
}
Ditto.

int main(int argc, char **argv)
{

I'd expect a function to do the work of converting the expression and
for that function to be called from main. It is a good idea to get into
the habit of doing this early.

int c=*argv[1],i=0,j=1;

What if there is no argc[1]? Also, there is no need for this
initialisation because the code below does it anyway.

for(stackinitze();--argc>0;c=*argv[j++])

This is 'for' loop syntax abuse! Just because you can put any three
expressions into the different parts does not mean it is a good idea.
I'd write:

stackinitze();
for (j = 1; j < argc; j++) {
int c = argv[j];
/* ... */
}

{

if(c>='0' && c<='9')

isdigit is better here.

*p++=(c-'0');

Only single digit numbers?

if(c=='+' || c=='*')
push((char)c);

push takes an int. What this does is convert an int into a char and
then back to an int for the call.

if(c==')')
*p++=pop(c);
}*p='\0';

Odd layout. On that subject, I'd suggest you use a lot more space --
between operators and after keywords for example.

Why '\0'? 'rev' is an int array and '\0' is 0 (but written so it look
like other character literals). You have, though, a data structure
problem here. If zero makes the end of the value queue, how can you
have a zero in the middle?

'p' (if you use it all) should be local to this function. As a general
rule, names should have the smallest possible scope and the larger the
scope the longer the name should be. (I don't mean xxxxxxxxxxxx instead
of x, of course, I mean longer and more helpful: eg: operator_stack,
value_queue, and so on).

while((c=rev[i++])!='\0')
{
if(isdigit(c))

You've turned digits into numbers. I.e. '0' is now 0 in the rev array
and isdigit(0) is 0 (false).

printf("%d",c);

Printing 2 followed by 2 will look like 22. Not a good idea if the
program is ever to handle proper numbers.

else
printf("%c",c);
}
while((c=rev[i++])!='\0')

I think you intended to reset i to 0 before this loop. rev already
beyond the 0 you put in there to mark the end.

{
if(c>='0'&& c<='9')

As before, '2' (for example) will have become 2 and 2 is not between '0'
and '9' (and isdigit is preferable to test the character range).

push(c-'0');
if(c=='+')
push(pop()+pop());
if(c=='*')
push(pop()*pop());
}
printf("Result is %d",pop());

Programs should write whole lines of output. Add a \n at the end.

return 0;
}

<snip>

 

[BartC]

I'm writing this program which converts a given infix expression to
postfix expression, store the postfix expression in array prints
it ,and then prints the sum. I have used link list to implement the

int pop()
{

pop() takes no parameters?

*p++=pop(c);

What's that pop(c) doing there then?

Here is the output::

rev_polish 5 * ( ( 9 + 7 ) + 7 )
5353424040574355414355 +Result is 43.

This is confusing: is this really the output, or also the input? Is the
'rev_polish' part of the input?

Perhaps specify exactly what the input is, and exactly what would be the
expected output.

int main(int argc, char **argv)
{
int c=*argv[1],i=0,j=1;
for(stackinitze();--argc>0;c=*argv[j++])

For this sort of thing, I would just hard-code test data into a string.
Especially if your method of running the program involves re-entering the
same input over and over again. Parsing from the command-line can be done
after it works.

And display exactly the string being entered, just to make it clear exactly
what is being worked on.

{

if(c>='0' && c<='9')
*p++=(c-'0');
if(c=='+' || c=='*')
push((char)c);
if(c==')')
*p++=pop(c);
}*p='\0';

Confusing bit of syntax here... Try inserting a new line or semicolon.

while((c=rev[i++])!='\0')
{
if(isdigit(c))
printf("%d",c);
else
printf("%c",c);
}

OK, you're printing what has been entered so far, which is presumably, a
bunch of numbers: 0 to 9 represents a number, and the code for '+' etc
represent an operator.

Using isdigit (which only works on '0'..'9', not on 0..9) won't work.
Perhaps just print the contents of rev[] as a series of numbers, then you
can see exactly what you've got. Once that bit works, then display it
properly formatted.

BTW you seem to be using '\0' as a terminator here; that form is normally
used as a string terminator character. Just 0 will do here. Although, if
your data can contain zero, this will clash with a 0 number in your
expression. So think of another terminator value not likely to occur. Or
maintain a separate length index.

You're using a stack implementing a linked list, requiring malloc() to
allocate, which is good practice, but a pain to use and error-prone . You've
also got to remember to free all the nodes later.

Since you're using a hard-coded size for rev[], you might as well do the
same for the stack, using an array of node (and since each node only
contains a single number, it simplifies to another array of int). Then you
just need a stack index.

 

[Maxx]

I'm writing this program which converts a given infix expression to
postfix expression, store the postfix expression in array prints
it ,and then prints the sum. I have used link list to implement the
pushdown stack. The program gets compiled correctly but its not giving
correct output at all. Here is the program i wrote::

There are lots of aspects to programming: you need to code well, know
your algorithms and use the right data structures (these are only the
ones I'll comment on -- there are others).

First, your algorithm is wrong.  If you are making this up, well done,
but you have not got it right yet.  If you are implementing something
you've read about, you need to do more work on understanding it.  What
you have looks like the start of Dijkstra's shunting yard algorithm (I
name it so you can look it up if you want to).

Below, I'll comment on coding and data structures.

#include <stdio.h>
#include <ctype.h>
#define MAX        1000

int rev[MAX];
int *p=rev;

These name are rather small for global variables.  p in particular.  As
it happens you don't need p to be global -- it should be local to the
function that needs it.

struct node
{
   int key;
   struct node *next;
};

struct node *head,*z,*t;

Ditto for z and t.  'head' is not a brilliant name either.  What is it
the head of?

I'd probably want to use a list for both the value queue (what you call
'rev') and for the operator stack.  Limiting one and not the other is
odd.  Alternatively, using a fixed size array for both would make the
program very simple, though you should check if you are running out of
space.

void stackinitze()

int pop(void) is the modern way to write this.  Ditto for pop() below.

{
   head=(struct node *)malloc(sizeof *head);

There is no need for the cast.  It just gets in the way of reading the
code.  Also (more serious) malloc is not declared.  You should to ask for
more warnings from your compiler and you should to follow up on what it
says.

Don't let yourself get into the habit of not checking function return
values.

   z=(struct node *)malloc(sizeof *z);
   head->next=z;
   head->key=0;
   z->next=z;
}

I'd expect nothing at all here.  I certainly would not expect two
mallocs, one of which is used to make a circular list.

There is an oft-used technique where a list always has a dummy element,
but if you are using this, you have misunderstood it's purpose.  With a
global 'head' pointer your list can be much simpler.

void push(int v)
{
   t=(struct node *)malloc(sizeof *t);
   t->key=v;
   t->next=head->next;
   head->next=t;
}

't' should be local.  You could use 'head' instead of 'head->next'.

int pop()
{
   int x;
   t=head->next;
   head->next=t->next;
   x=t->key;
   free(t);
   return x;
}
Ditto.

int main(int argc, char **argv)
{

I'd expect a function to do the work of converting the expression and
for that function to be called from main.  It is a good idea to get into
the habit of doing this early.

   int c=*argv[1],i=0,j=1;

What if there is no argc[1]?  Also, there is no need for this
initialisation because the code below does it anyway.

   for(stackinitze();--argc>0;c=*argv[j++])

This is 'for' loop syntax abuse!  Just because you can put any three
expressions into the different parts does not mean it is a good idea.
I'd write:

        stackinitze();
        for (j = 1; j < argc; j++) {
            int c = argv[j];
            /* ... */
        }

   {

           if(c>='0' && c<='9')

isdigit is better here.

                   *p++=(c-'0');

Only single digit numbers?

           if(c=='+' || c=='*')
                   push((char)c);

push takes an int.  What this does is convert an int into a char and
then back to an int for the call.

           if(c==')')
                   *p++=pop(c);
   }*p='\0';

Odd layout.  On that subject, I'd suggest you use a lot more space --
between operators and after keywords for example.

Why '\0'?  'rev' is an int array and '\0' is 0 (but written so it look
like other character literals).  You have, though, a data structure
problem here.  If zero makes the end of the value queue, how can you
have a zero in the middle?

'p' (if you use it all) should be local to this function.  As a general
rule, names should have the smallest possible scope and the larger the
scope the longer the name should be.  (I don't mean xxxxxxxxxxxx instead
of x, of course, I mean longer and more helpful: eg: operator_stack,
value_queue, and so on).

   while((c=rev[i++])!='\0')
   {
           if(isdigit(c))

You've turned digits into numbers.  I.e. '0' is now 0 in the rev array
and isdigit(0) is 0 (false).

                   printf("%d",c);

Printing 2 followed by 2 will look like 22.  Not a good idea if the
program is ever to handle proper numbers.

           else
                   printf("%c",c);
   }
   while((c=rev[i++])!='\0')

I think you intended to reset i to 0 before this loop.  rev already
beyond the 0 you put in there to mark the end.

   {
           if(c>='0'&& c<='9')

As before, '2' (for example) will have become 2 and 2 is not between '0'
and '9' (and isdigit is preferable to test the character range).

                   push(c-'0');
           if(c=='+')
                   push(pop()+pop());
           if(c=='*')
                   push(pop()*pop());
   }
   printf("Result is %d",pop());

Programs should write whole lines of output.  Add a \n at the end.

   return 0;
}

<snip>

Yeah i was actually trying to implement this algorithm on my own. But
went horribly wrong.

Of what i understood dummy nodes are use so that we can manipulate the
list with ease, esp in the first and last node cases.

I was hoping to input multidigit numbers not only one digit. Thats why
i stored each of them in argv[] with spaces separating them.

Terminating and array have always bugged me. I can't figure out what
values should do justice and be unique in the array..

Anyways thanks for the help

 

[Maxx]

pop() takes no parameters?


What's that pop(c) doing there then?



This is confusing: is this really the output, or also the input? Is the
'rev_polish' part of the input?

rev_polish is the name of the program. and only the first line is the
input till the ')'.

Perhaps specify exactly what the input is, and exactly what would be the
expected output.

int main(int argc, char **argv)
{
int c=*argv[1],i=0,j=1;
for(stackinitze();--argc>0;c=*argv[j++])

For this sort of thing, I would just hard-code test data into a string.
Especially if your method of running the program involves re-entering the
same input over and over again. Parsing from the command-line can be done
after it works.

And display exactly the string being entered, just to make it clear exactly
what is being worked on.

{

if(c>='0' && c<='9')
*p++=(c-'0');
if(c=='+' || c=='*')
push((char)c);
if(c==')')
*p++=pop(c);
}*p='\0';

Confusing bit of syntax here... Try inserting a new line or semicolon.

while((c=rev[i++])!='\0')
{
if(isdigit(c))
printf("%d",c);
else
printf("%c",c);
}

OK, you're printing what has been entered so far, which is presumably, a
bunch of numbers: 0 to 9 represents a number, and the code for '+' etc
represent an operator.

Yeah i was actually aiming to print the operators as characters.

Using isdigit (which only works on '0'..'9', not on 0..9) won't work.
Perhaps just print the contents of rev[] as a series of numbers, then you
can see exactly what you've got. Once that bit works, then display it
properly formatted.

Didn't get your point here.. why would isdigit() won't work.. After
all it should detect the digits and print them

BTW you seem to be using '\0' as a terminator here; that form is normally
used as a string terminator character. Just 0 will do here. Although, if
your data can contain zero, this will clash with a 0 number in your
expression. So think of another terminator value not likely to occur. Or
maintain a separate length index.

I'm very uncertain as what values should be used as an array
terminator.

You're using a stack implementing a linked list, requiring malloc() to
allocate, which is good practice, but a pain to use and error-prone . You've
also got to remember to free all the nodes later.

Since you're using a hard-coded size for rev[], you might as well do the
same for the stack, using an array of node (and since each node only
contains a single number, it simplifies to another array of int). Then you
just need a stack index.

Thanks

 

[BartC]

Didn't get your point here.. why would isdigit() won't work.. After
all it should detect the digits and print them

Try this:

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

int main(void){
int i;

for (i=0; i<=127; ++i)
printf("<%d> <%c> %d\n", i,i, isdigit(i));
}

You will see isdigit() only returns True (ie. not 0) for (Ascii) codes 48 to
57, ie. characters '0' to '9'. Not for 0 to 9.

I think your earlier code converted characters '0' to '9' (codes 48 to 57)
to numbers 0 to 9.