Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Infix to Postfix program not giving correct output

Reply
Thread Tools

Infix to Postfix program not giving correct output

 
 
Maxx
Guest
Posts: n/a
 
      01-29-2011
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.
 
Reply With Quote
 
 
 
 
Ben Bacarisse
Guest
Posts: n/a
 
      01-29-2011
Maxx <(E-Mail Removed)> writes:

> 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[i] 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>
--
Ben.
 
Reply With Quote
 
 
 
 
BartC
Guest
Posts: n/a
 
      01-29-2011
"Maxx" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> 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.

--
Bartc

 
Reply With Quote
 
Maxx
Guest
Posts: n/a
 
      02-07-2011
On Jan 29, 5:36*am, Ben Bacarisse <(E-Mail Removed)> wrote:
> Maxx <(E-Mail Removed)> writes:
> > 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[i] 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>
> --
> Ben.


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

 
Reply With Quote
 
Maxx
Guest
Posts: n/a
 
      02-07-2011
On Jan 29, 6:50*am, "BartC" <(E-Mail Removed)> wrote:
> "Maxx" <(E-Mail Removed)> wrote in message
>
> news:(E-Mail Removed)...
>
> > 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?


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.
>
> --
> Bartc



Thanks
 
Reply With Quote
 
BartC
Guest
Posts: n/a
 
      02-07-2011

"Maxx" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> On Jan 29, 6:50 am, "BartC" <(E-Mail Removed)> wrote:


>> Using isdigit (which only works on '0'..'9', not on 0..9) won't work.


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

--
Bartc

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
The Concepts and Confusions of Prefix, Infix, Postfix and Fully Functional Notations Xah Lee Java 30 06-16-2007 05:57 PM
The Concepts and Confusions of Prefix, Infix, Postfix and Fully Functional Notations Xah Lee Python 30 06-16-2007 05:57 PM
Infix to postfix when have no brackets in the input? tomerdr@gmail.com C++ 1 12-28-2006 10:03 PM
convert infix to postfix caramel C Programming 19 11-19-2005 08:51 PM
infix to postfix expression string for evalution. KidLogik C++ 5 02-03-2004 05:20 PM



Advertisments