Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

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?

like image 872
kuszi Avatar asked Jan 06 '11 23:01

kuszi


1 Answers

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 */
}
like image 74
makes Avatar answered Oct 13 '22 13:10

makes