Infix to Postfix program not giving correct output

Discussion in 'C Programming' started by Maxx, Jan 29, 2011.

  1. Maxx

    Maxx Guest

    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.
    Maxx, Jan 29, 2011
    #1
    1. Advertising

  2. Maxx <> 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 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.
    Ben Bacarisse, Jan 29, 2011
    #2
    1. Advertising

  3. Maxx

    BartC Guest

    "Maxx" <> wrote in message
    news:...
    > 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
    BartC, Jan 29, 2011
    #3
  4. Maxx

    Maxx Guest

    On Jan 29, 5:36 am, Ben Bacarisse <> wrote:
    > Maxx <> 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 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
    Maxx, Feb 7, 2011
    #4
  5. Maxx

    Maxx Guest

    On Jan 29, 6:50 am, "BartC" <> wrote:
    > "Maxx" <> wrote in message
    >
    > news:...
    >
    > > 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
    Maxx, Feb 7, 2011
    #5
  6. Maxx

    BartC Guest

    "Maxx" <> wrote in message
    news:...
    > On Jan 29, 6:50 am, "BartC" <> 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
    BartC, Feb 7, 2011
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. KidLogik
    Replies:
    5
    Views:
    7,030
    David Rubin
    Feb 3, 2004
  2. caramel

    convert infix to postfix

    caramel, Nov 18, 2005, in forum: C Programming
    Replies:
    19
    Views:
    1,394
    Barry
    Nov 19, 2005
  3. Replies:
    1
    Views:
    425
    mlimber
    Dec 28, 2006
  4. Xah Lee
    Replies:
    30
    Views:
    1,751
    Peter J. Holzer
    Jun 16, 2007
  5. Xah Lee
    Replies:
    30
    Views:
    1,222
    Peter J. Holzer
    Jun 16, 2007
Loading...

Share This Page