The program will be given a mathematical expression written in traditional infix notation, and has to convert it to reverse polish notation (RPN).
The program is a filter: it must read from STDIN, and send output to STDOUT.
Input will consist of a single line, which will match
/\A[\d() \t*\/+-]{1,9999}\n\z/. The input will always be a
valid infix expression, as described below.
An infix expression is one of the following:
0:s.
Negative numbers will have a leading -.
Positive numbers won't have a leading +.
* / + -).
The expression may contain whitespace in any position except
between two digits. (I.e the expression won't match
/\d\s\d/).
Clarification: there may be
whitespace between the leading - and the first
digit of a negative number.
The operators follow the standard precedence conventions of
infix notation. That is, * and /
have higher precedence
than + and -. All operators are left-associative.
The output must consist of the same integers and operators
as the input. Every integer/operator must be separated from
the following one by exactly one space. The output must also
be properly newline-terminated. No other whitespace is allowed
in the output.
Clarification: "the same integer" means "having
the same integer value". That is, for the input token
007 you may output any of 7, 07, 007, 0007,
etc. All numbers (both input and output) are considered
to be in base-10. Yes, this means that 0 is
valid output for -0 and vice versa.
The RPN expression must be equivalent to the original input expression. For the purposes of this hole, equivalency means that evaluating the two expressions using integer arithmetic must produce the same results.
A RPN expression is evaluated by handling the tokens of the expression from left to right.
Once all of the operators have been evaluated, there should be exactly one item on the stack. The value of that item is the result of the evaluation.
The tiebreaker will favour programs with short lines and lots of
characters matching /[ \t\d*\/+()-]/.
You must not write to STDERR.
The program return code does not matter.
The program's runtime should be reasonably short. For any valid input the program should run in five minutes of CPU time on a 600 MHz Celeron.
The programs can be written as one or more lines. The score is the total number of characters you need (smaller is better). If your program is more than one line, you must count the newlines in between as one character each. The #! line is not counted. If you use options on the #! line, the options themselves are counted, including the leading space and ``-''.
If two (or more) golfers have the same score for the hole, the golfer with the lowest tie break score wins.
All programs must work on perl 5.6.1.
Assume total memory is < 2**32 bytes.
The programs may only use the perl executable, no other executables on the system are allowed (the program may use itself though). You may use any of the perl 5.6.1 standard core modules (perldoc perlmodlib for a list of those core modules). Your solutions must be portable in the sense that it should work on all versions of 5.6.1 everywhere (however, it's perfectly fine to abuse perl 5.6.1 bugs).
When tested, your script will be named rpn.pl, and you must assume your script to have file permissions of 0444 (that is read-only and non-executable for windows folks).
Input Example output 1 + 1 1 1 + 2*2 + 3*3 2 2 * 3 3 * + 2*(2 + -3)*3 2 2 -3 + * 3 *Note that there are multiple valid solutions to most inputs.
The game starts September 1st (05:00 UTC) and ends September 8th (05:00 UTC).
A test program [version 8] is provided to help screen entries.
Any program that passes the test program should be submitted. If you are surprised that your solution passed the test program, please submit it anyway! That will help us identify bugs in the test program.
Name your script rpn.pl, and place it in the same directory as your test program. Then verify and score your attempt using:
$ perl tpr05a.pl
The test program is based on Ton Hospel's generic golf tester, and thus has plenty of useful features. For more information on them type:
$ perl tpr05a.pl --help
Passing the test program does not assure your solution is valid. The referees have the final say.
You can submit your solutions here (you'll notice it's the same page as the Leaderboard). As a courtesy to other players, you should not wait until the last moment to submit your solutions. Everyone has more fun when the leaderboard depicts the situation correctly.
Do not publish your solutions anywhere. That will spoil the game, as your solutions are meant to be secret. All solutions will be published at the end of the game.
Prizes (provided by O'Reilly and ActiveState) will be awarded to veteran and beginner winners. A prize may also be awarded to any especially interesting artistic and/or unorthodox solutions.
You can track your ranking through the leaderboard here. Beginners are encouraged to enter and there is a separate leaderboard for them.
There is also a special leaderboard for teams. There will be no prizes awarded to the best team, other than the admiration of your fellow golfers. If you are in a team, you can't also play individually.
We encourage you to send feedback as well as your ideas for future holes and tiebreakers to golf@theperlreview.com.
Yanick Champoux <yanick1@sympatico.ca>
Terje Kristensen <terjek@operamail.com>
F. Xavier Noria <fxn@retemail.es>
Juho Snellman <jsnell@iki.fi>
If you want to be a referee next month, drop us a note: golf@theperlreview.com