Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #92559 > unrolled thread

Need Help Displaying of Infix to postfix conversion

Back to article view | Back to comp.lang.c

Contents

  Need Help Displaying of Infix to postfix conversion Own IT <beltondavid1@gmail.com> - 2016-08-21 02:47 -0700
    Re: Need Help Displaying of Infix to postfix conversion BartC <bc@freeuk.com> - 2016-08-21 11:17 +0100
      Re: Need Help Displaying of Infix to postfix conversion Keith Thompson <kst-u@mib.org> - 2016-08-21 15:43 -0700
        Re: Need Help Displaying of Infix to postfix conversion BartC <bc@freeuk.com> - 2016-08-21 22:17 +0100
          Re: Need Help Displaying of Infix to postfix conversion Keith Thompson <kst-u@mib.org> - 2016-08-21 18:17 -0700
    Re: Need Help Displaying of Infix to postfix conversion Barry Schwarz <schwarzb@dqel.com> - 2016-08-21 09:42 -0700
      Re: Need Help Displaying of Infix to postfix conversion Siri Cruise <chine.bleu@yahoo.com> - 2016-08-21 11:24 -0700
      Re: Need Help Displaying of Infix to postfix conversion BartC <bc@freeuk.com> - 2016-08-21 23:40 +0100
        Re: Need Help Displaying of Infix to postfix conversion Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-22 00:13 +0100
          Re: Need Help Displaying of Infix to postfix conversion BartC <bc@freeuk.com> - 2016-08-22 01:31 +0100
            Re: Need Help Displaying of Infix to postfix conversion David Kleinecke <dkleinecke@gmail.com> - 2016-08-21 20:13 -0700
      Re: Need Help Displaying of Infix to postfix conversion supercat@casperkitty.com - 2016-08-22 09:44 -0700
        Re: Need Help Displaying of Infix to postfix conversion Barry Schwarz <schwarzb@dqel.com> - 2016-08-22 10:18 -0700
          Re: Need Help Displaying of Infix to postfix conversion supercat@casperkitty.com - 2016-08-22 10:27 -0700
            Re: Need Help Displaying of Infix to postfix conversion "Osmium" <r124c4u102@comcast.net> - 2016-08-22 16:05 -0500
          Usenet in general and CLC in particular (Was: Need Help something or other...) gazelle@shell.xmission.com (Kenny McCormack) - 2016-08-25 11:48 +0000

#92559 — Need Help Displaying of Infix to postfix conversion

I have a program with me and it works fine, however I want a different output. The program is all about infix to postfix conversion. Say I have a expression of 3*7-5+6, my code displays 37*5-6+ which is correct however I want an output like this:
3
37
37*
37*5
37*5-
37*5-6
37*5-6+

This is my code

#include<stdio.h>
#include<conio.h>
#include<ctype.h>
char stack[20];
int top = -1;
void push(char x)
{
        stack[++top] = x;
}

char pop()
{
        if(top == -1)
            return -1;
        else
            return stack[top--];
}

int priority(char x)
{
    if(x == '(')
    return 0;
    if(x == '+' || x == '-')
    return 1;
    if(x == '*' || x == '/')
    return 2;
}

void main()
{
    char exp[20];
    char *e, x;
    printf("Enter the expression: ");
    scanf("%s",exp);
    e = exp;
    while(*e != '\0')
    {
            if(isalnum(*e))
                    printf("%c",*e);
            else if(*e == '(')
                    push(*e);
    else if(*e == ')')
            {
                    while((x = pop()) != '(')
                        printf("%c", x);
            }
    else
    {
        while(priority(stack[top]) >= priority(*e))
            printf("%c",pop());
        push(*e);
    }
            e++;
    }
while(top != -1)
{
    printf("%c",pop());
}

getch();
}

[toc] | [next] | [standalone]

#92560

On 21/08/2016 10:47, Own IT wrote:
> I have a program with me and it works fine, however I want a different output. The program is all about infix to postfix conversion. Say I have a expression of 3*7-5+6, my code displays 37*5-6+ which is correct however I want an output like this:
> 3
> 37
> 37*
> 37*5
> 37*5-
> 37*5-6
> 37*5-6+

This is just the final line, but output incrementally on each line? So 
with ABC as the result, it is shown as:

  A
  AB
  ABC

?

> char pop()

Use char pop(void) here. (Otherwise it won't work with some compilers.)

> int priority(char x)
> {
>     if(x == '(')
>     return 0;
>     if(x == '+' || x == '-')
>     return 1;
>     if(x == '*' || x == '/')
>     return 2;
> }

You need indents here on the return statements. Then you'll see there is 
no return statement for when all conditions are false.

> while(top != -1)
> {
>     printf("%c",pop());
> }

This is where you'll want to store each character into a array of 
characters, rather than just output them immediately.

Once in such a string, then one or two loops and some logic will give 
you the output you want. Note this will display all the lines at once; 
you can't have a character-at-a-time output as you type the input, for 
several reasons.

-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#92569

BartC <bc@freeuk.com> writes:
> On 21/08/2016 10:47, Own IT wrote:
[...]
>> char pop()
>
> Use char pop(void) here. (Otherwise it won't work with some compilers.)

Certainly char pop(void) is preferred to the old-style char pop(), but
any conforming C compiler will accept the older form.

(And of course `void main()` should be `int main(void)`.)

[...]

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#92570

On 21/08/2016 23:43, Keith Thompson wrote:
> BartC <bc@freeuk.com> writes:
>> On 21/08/2016 10:47, Own IT wrote:
> [...]
>>> char pop()
>>
>> Use char pop(void) here. (Otherwise it won't work with some compilers.)
>
> Certainly char pop(void) is preferred to the old-style char pop(), but
> any conforming C compiler will accept the older form.

I thought it went badly wrong when using gcc, with pop(), but I've done 
more tests and it happens with pop(void) too. I get this output for '3*4':

3ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿ ....

instead of '34*'. Only when optimised. So there might be a bug either in 
the code, or possibly with gcc.

(BTW you now seem to be posting from two hours in the future instead of 
one...)

-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#92574

BartC <bc@freeuk.com> writes:
> On 21/08/2016 23:43, Keith Thompson wrote:
>> BartC <bc@freeuk.com> writes:
>>> On 21/08/2016 10:47, Own IT wrote:
>> [...]
>>>> char pop()
>>>
>>> Use char pop(void) here. (Otherwise it won't work with some compilers.)
>>
>> Certainly char pop(void) is preferred to the old-style char pop(), but
>> any conforming C compiler will accept the older form.
>
> I thought it went badly wrong when using gcc, with pop(), but I've
> done more tests and it happens with pop(void) too. I get this output
> for '3*4':
>
> 3ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿ ....
>
> instead of '34*'. Only when optimised. So there might be a bug either
> in the code, or possibly with gcc.

It's not a gcc bug, it's a bug in the code.  The code accesses
stack[-1].  It's not too surprising that the behavior differs with the
optimization level.

> (BTW you now seem to be posting from two hours in the future instead
> of one...)

Thanks, but again, it's not my machine, and I've done what I can.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#92564

On Sun, 21 Aug 2016 02:47:19 -0700 (PDT), Own IT
<beltondavid1@gmail.com> wrote:

>I have a program with me and it works fine, however I want a different output. The program is all about infix to postfix conversion. Say I have a expression of 3*7-5+6, my code displays 37*5-6+ which is correct however I want an output like this:
>3
>37
>37*
>37*5
>37*5-
>37*5-6
>37*5-6+

Bart has already given you a hint on how to achieve this.  It applies
to everywhere you currently call printf.  Here are some other comments
that might help you.

>This is my code
>
>#include<stdio.h>
>#include<conio.h>

This is a non-standard header.  If you change from calling getch to
calling getchar (see below), you lose nothing and your code becomes
portable.  When asking for help here, it will increase the number of
potential responders.

>#include<ctype.h>
>char stack[20];
>int top = -1;
>void push(char x)
>{
>        stack[++top] = x;
>}
>
>char pop()

In C, this means that the number and type of arguments to pop are not
specified (and could be anything).  If you want a function with no
arguments, specify void.

>{
>        if(top == -1)
>            return -1;

This seems pointless since you never test the return value for
validity before using it in statements that call pop.

There are systems where char is unsigned.  On those, this will produce
a large value.  If pop returned int, that problem would disappear and
it would simplify the testing suggested above.

>        else
>            return stack[top--];
>}
>
>int priority(char x)
>{
>    if(x == '(')
>    return 0;

You started out with a nice indenting format.  Keep to it consistently
and it will help you eliminate the error Bart noted here.

>    if(x == '+' || x == '-')
>    return 1;
>    if(x == '*' || x == '/')
>    return 2;
>}
>
>void main()

main returns int.  Always.

>{
>    char exp[20];
>    char *e, x;
>    printf("Enter the expression: ");
>    scanf("%s",exp);

When you enter data into a program this way, it goes into a buffer
until you press Enter.  Then scanf extracts as much data as it wants
from the buffer, leaving the remainder for future use.  With %s, scanf
stops extracting at the first white space character.  \n is such a
character.

>    e = exp;
>    while(*e != '\0')
>    {
>            if(isalnum(*e))
>                    printf("%c",*e);
>            else if(*e == '(')
>                    push(*e);
>    else if(*e == ')')
>            {
>                    while((x = pop()) != '(')
>                        printf("%c", x);
>            }
>    else
>    {
>        while(priority(stack[top]) >= priority(*e))

This code will not handle an expression with a leading sign, such as 
    +5-4
or 
    -6*4
It will attempt to evaluate stack[-1] which will cause undefined
behavior.

It is probably beyond the scope of what you intend but this code will
get confused with erroneous expressions such as 
   4(5)
or
   6+/3
and it also fails to handle "reasonable" ones like
   4*-2
even if parenthesized to
   4*(-2)

>            printf("%c",pop());
>        push(*e);
>    }
>            e++;
>    }
>while(top != -1)
>{
>    printf("%c",pop());
>}
>
>getch();

As noted above, there is still a character in the buffer.  On many
systems, getch will accept this character and your program will not
pause.

Even on systems where getch will wait, how does the user know?  He can
see the printed output but the system is not presenting any stimulus.
If you replace this with
     puts("Press Enter to continue");
     getchar();
     getchar();
you improve the user interface and resolve the portability issue.

>}

-- 
Remove del for email

[toc] | [prev] | [next] | [standalone]

#92567

In article <rmjjrbp57ba3ecuiv430vtirnq5drjelmd@4ax.com>,
 Barry Schwarz <schwarzb@dqel.com> wrote:

> >    {
> >        while(priority(stack[top]) >= priority(*e))
> 
> This code will not handle an expression with a leading sign, such as 
>     +5-4
> or 
>     -6*4
> It will attempt to evaluate stack[-1] which will cause undefined
> behavior.
> 
> It is probably beyond the scope of what you intend but this code will
> get confused with erroneous expressions such as 
>    4(5)
> or
>    6+/3
> and it also fails to handle "reasonable" ones like
>    4*-2
> even if parenthesized to
>    4*(-2)

You can generalise a precedence parser with left and right precedences and a 
marked nofix precedence. Suppose I use precedences 0 to 100. Examples of left 
and right precedences could be 60+60 60-60 70*70 10,10 10=15 100(0 0)100 
100identifier100 100number100.

100x100 is a nofix operator, like an identifier or number.
100x0 is left bracket.
0x100 is a right bracket.
100x(m), 0<m<100, is prefix operator.
(m)x100, 0<m<100, is postfix operator.
(m)x(n), 0<n<=m<100, is a left associative infix operator.
(m)x(n), 0<m<n<100, is a right associative infix operator.

There's a value stack of partial computations (actual numbers, parse trees, 
whatever) and an operator stack of tokens. Start with an empty value stack and a 
operator stack 100begin0.

The loop is
    do
        read next token as (left)token(right).
                on the end of the input token is 0end100
        if (operators top right==100)==(input token left==100)
            then parse conflict
                switch input token
                    case 60-60: change input token to 100-99 (negation)
                    case 100++99: change to 99++100 (preincr to postincr)
                    ...
                    default: parse error
        bool zeropop = false
        while not zeropop and operators top right >= input token left
            (left)OP(right) = pop off operators stack
            Y = right==100 ? null : pop off values stack
            X = left==100 ? null : pop off values stack
            compute X OP Y and push on values stack
            zeropop = right==0
            if zeropop
                parse error if OP and input token are incompatiable
                for example not (...) or [...] or ?...:
        push input token on operator stack
    until end of input

Exitting the read tokens loop leaves either
    parse error
or
    value stack has one element, the complete computation
    operator stack has one element, 0end100

-- 
:-<> Siri Seal of Disavowal #000-001. Disavowed. Denied. Deleted.
'I desire mercy, not sacrifice.'
If you assume the final scene is a dying delusion as Tom Cruise drowns below
the Louvre, then Edge of Tomorrow has a happy ending. Kill Tom repeat..

[toc] | [prev] | [next] | [standalone]

#92572

On 21/08/2016 17:42, Barry Schwarz wrote:
> On Sun, 21 Aug 2016 02:47:19 -0700 (PDT), Own IT

>>        while(priority(stack[top]) >= priority(*e))

> It will attempt to evaluate stack[-1] which will cause undefined
> behavior.

I had to change that line to:

         while(priority(top>=0 && stack[top]) >= priority(*e))

to fix the gcc problem I was seeing.

-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#92573

BartC <bc@freeuk.com> writes:

> On 21/08/2016 17:42, Barry Schwarz wrote:
>> On Sun, 21 Aug 2016 02:47:19 -0700 (PDT), Own IT
>
>>>        while(priority(stack[top]) >= priority(*e))
>
>> It will attempt to evaluate stack[-1] which will cause undefined
>> behavior.
>
> I had to change that line to:
>
>         while(priority(top>=0 && stack[top]) >= priority(*e))

That looks like a typo.  There are several places where stack access
needs a check for correctness.  This is one of them and you do that with

  while(top >= 0 && priority(stack[top]) >= priority(*e))

I'd write a tiny "empty()" function and a "top()" function too just to
keep all the stack stuff in one place.

> to fix the gcc problem I was seeing.

I don't think it's a gcc problem -- it's a code problem.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#92575

On 22/08/2016 00:13, Ben Bacarisse wrote:
> BartC <bc@freeuk.com> writes:
>
>> On 21/08/2016 17:42, Barry Schwarz wrote:
>>> On Sun, 21 Aug 2016 02:47:19 -0700 (PDT), Own IT
>>
>>>>        while(priority(stack[top]) >= priority(*e))
>>
>>> It will attempt to evaluate stack[-1] which will cause undefined
>>> behavior.
>>
>> I had to change that line to:
>>
>>         while(priority(top>=0 && stack[top]) >= priority(*e))
>
> That looks like a typo.  There are several places where stack access
> needs a check for correctness.  This is one of them and you do that with
>
>   while(top >= 0 && priority(stack[top]) >= priority(*e))

Yes, that's what I didn't quite manage to transcribe.


> I'd write a tiny "empty()" function and a "top()" function too just to
> keep all the stack stuff in one place.

That's a good idea too (since the overflow and underflow checks I put in 
didn't quite catch the problem; I had to resort to looking at the code!)

--
Bartc

[toc] | [prev] | [next] | [standalone]

#92576

Here's some code I wrote for a similar purpose"

done = false;
while (! done) {
   Token t;
   if (suffix) {
      if (prefix_precedence [read (prefix-stack)] >
               suffix_precedence [suffix] {
         apply_prefix ();}
      else {
         apply_suffix ();}
   else if (datum) {
      t = read_token ();
      if (t <= last_operator) {
         suffix = t;}
      else {
         unread_token (t);
         suffix = CONCATENATE;}}
   else {
      t = read_token ();
      if (t <= last_operator) {
         suffix = t;}
      else {
         datum = t;}}}

Most of the real work is done by the apply_prefix function
(which pops the prefix_stack). The default apply_suffix function
pushes the suffix onto the prefix_stack and the datum onto a
so-far unmentioned datum_stack. The apply_prefix function is
generally a binary combining the top of the datum_stack with
the datum.

Of course, this doesnt do exactly what the OP wanted but it is
much more versatile. 

I feel sure I will told if I have made any errors.

[toc] | [prev] | [next] | [standalone]

#92590

On Sunday, August 21, 2016 at 11:42:43 AM UTC-5, Barry Schwarz wrote:
> This is a non-standard header.  If you change from calling getch to
> calling getchar (see below), you lose nothing and your code becomes
> portable.  When asking for help here, it will increase the number of
> potential responders.

On the platforms I've seen that support <conio.h> and getch(), calling
getch() will retrieve a single character from the console without line
buffering, while getchar() will capture everything until the next newline,
retrieve one character, and leave the remainder pending.  It also is not
subject to I/O redirection.  There are ways of achieving the same effect
in Unix, but IMHO the approach taken by popular compilers that target
MS-DOS, CP/M, etc. is superior on platforms that can support it.

[toc] | [prev] | [next] | [standalone]

#92592

On Mon, 22 Aug 2016 09:44:08 -0700 (PDT), supercat@casperkitty.com
wrote:

>On Sunday, August 21, 2016 at 11:42:43 AM UTC-5, Barry Schwarz wrote:
>> This is a non-standard header.  If you change from calling getch to
>> calling getchar (see below), you lose nothing and your code becomes
>> portable.  When asking for help here, it will increase the number of
>> potential responders.
>
>On the platforms I've seen that support <conio.h> and getch(), calling
>getch() will retrieve a single character from the console without line
>buffering, while getchar() will capture everything until the next newline,
>retrieve one character, and leave the remainder pending.  It also is not
>subject to I/O redirection.  There are ways of achieving the same effect
>in Unix, but IMHO the approach taken by popular compilers that target
>MS-DOS, CP/M, etc. is superior on platforms that can support it.

Probably all true but in the case under discussion there already was a
\n sitting in the buffer (residue from the call to scanf) waiting to
be retrieved.  I also doubt that an unseasoned new programmer would be
concerned with this level of detail.

The point that not everyone has conio.h and getch remains valid. Using
them unnecessarily reduces the number of potential responders which is
counter-productive when asking questions here.

-- 
Remove del for email

[toc] | [prev] | [next] | [standalone]

#92594

On Monday, August 22, 2016 at 12:19:02 PM UTC-5, Barry Schwarz wrote:
> Probably all true but in the case under discussion there already was a
> \n sitting in the buffer (residue from the call to scanf) waiting to
> be retrieved.  I also doubt that an unseasoned new programmer would be
> concerned with this level of detail.

The purpose of the code is to wait until the user actually hits a key.
An attempt to read input from stdin when it isn't redirected will grab
character input until the user hits return/enter, anything after that
will be left pending until either getch() is called, or until there is
an attempt to read more data from stdin after the newline (in the latter
case, input will be grabbed until the next newline).

> The point that not everyone has conio.h and getch remains valid. Using
> them unnecessarily reduces the number of potential responders which is
> counter-productive when asking questions here.

There is no reason that any C programmer shouldn't have a general idea of
what those things do on systems that support them.  Some systems open up a
console window when launching a program, and close that window when the
program terminates; getch() will give users a chance to see what output
the program produced.

[toc] | [prev] | [next] | [standalone]

#92607

<supercat@casperkitty.com> wrote:

> On Monday, August 22, 2016 at 12:19:02 PM UTC-5, Barry Schwarz wrote:
>> Probably all true but in the case under discussion there already was a
>> \n sitting in the buffer (residue from the call to scanf) waiting to
>> be retrieved.  I also doubt that an unseasoned new programmer would be
>> concerned with this level of detail.
>
> The purpose of the code is to wait until the user actually hits a key.
> An attempt to read input from stdin when it isn't redirected will grab
> character input until the user hits return/enter, anything after that
> will be left pending until either getch() is called, or until there is
> an attempt to read more data from stdin after the newline (in the latter
> case, input will be grabbed until the next newline).
>
>> The point that not everyone has conio.h and getch remains valid. Using
>> them unnecessarily reduces the number of potential responders which is
>> counter-productive when asking questions here.
>
> There is no reason that any C programmer shouldn't have a general idea of
> what those things do on systems that support them.  Some systems open up a
> console window when launching a program, and close that window when the
> program terminates; getch() will give users a chance to see what output
> the program produced.

Any hint that will help a poster get an on topic response is helpful, this 
group delights in pursuing tangents and diversions, and it is to the posters 
advantage if he can possibly avoid them  Using getch() is a tangent magnet 
and is not needed in the situation you cite.  Simply put a couple gethar() 
calls just before the final brace. 

[toc] | [prev] | [next] | [standalone]

#92695 — Usenet in general and CLC in particular (Was: Need Help something or other...)

In article <jjcmrbl6d3sh3741bibrpk7ms53d7snct0@4ax.com>,
Barry Schwarz  <schwarzb@dqel.com> wrote:
...
>The point that not everyone has conio.h and getch remains valid. Using
>them unnecessarily reduces the number of potential responders which is
>counter-productive when asking questions here.

This is flat out wrong.

The fact is that the more "off topic" stuff you include in your post, the
*more* likely it is that people will respond.

In fact, the real problem with forums in general, Usenet in more
specificity, and this newsgroup in particular, is that unless you include
soemthing for people to nitpick (i.e., something that is "wrong"), people
will usually just ignore your post.

-- 
Conservatives want smaller government for the same reason criminals want fewer cops.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web