CODEWITHSUNDEEP
c
kuszi
kuszi

Reputation: 2079

The shortest way to convert infix expressions to postfix (RPN) in C

Original formulation is given here (you can try also your program for correctness) .

Additional rules:
1. The program should read from standard input and write to standard output.
2. The program should return zero to the calling system/program.
3. The program should compile and run with gcc -O2 -lm -s -fomit-frame-pointer.

The challenge has some history: the call for short implementations has been announced at the Polish programming contest blog in September 2009. After the contest, the shortest code was 81 chars long. Later on the second call has been made for even shorter code and after the year matix2267 published his solution in 78 bytes:

main(c){read(0,&c,1)?c-41&&main(c-40&&(c%96<27||main(c),putchar(c))):exit(0);}

Anyone to make it even shorter or prove this is impossible?

Upvotes: 13

Views: 5897

Answers (3)

makes
makes

Reputation: 6548

Here's a way to reduce the code down to 76 chars:

main(c){read(0,&c,1)?c-41&&main(c-40&&putchar(c,c%96>26&&main(c))):exit(0);}

A longer, commented version for clarity:

int main(int c)
{
   if (read(0,&c,1)) {          /* read char */
       if (c-41) {              /* if not ')' */
           if (c-40) {          /* then if not '(' */
               if (c%96>26) {   /* then if operator (not alphabet or <LF>) */
                   main(c);     /* recurse */
               }
               putchar(c);      /* print */
           }
           main(c);             /* recurse */
       }        
   } else exit(0);              /* end program */
}

Upvotes: 11

makes
makes

Reputation: 6548

I'm not out to break any records but I'll post this anyway:

#define x(z) while(p>##z s)putchar(*p--);
main(c){
int s[9],*p=s-1;
for(;read(0,&c,1);){
isalpha(c)?putchar(c):c=='('?(c=0):c==')'?(c=1):isdigit(c)?:(*++p=c);
if(c==0){x()main(0);}
if(c==1) break;}
x(=)return 0;}

Edit: Fixed correctness issues pointed out by kuszi's comment.

Upvotes: 4

Benoit Thiery
Benoit Thiery

Reputation: 6387

Well, the real winner is the one who wrote this small code you provided, but you can slightly modify it to remove the exit:

main(c){read(0,&c,1)?c-41&&main(c-40&&(c%96<27||main(c),putchar(c))):0;}

I tried and it works.

Upvotes: 4

Related Questions