Here is the challenge (of my own invention, though I wouldn't be surprised if it has previously appeared elsewhere on the web).
Write a function that takes a single argument that is a string representation of a simple mathematical expression and evaluates it as a floating point value. A "simple expression" may include any of the following: positive or negative decimal numbers, +, -, *, /, (, ). Expressions use (normal) infix notation. Operators should be evaluated in the order they appear, i.e. not as in BODMAS, though brackets should be correctly observed, of course. The function should return the correct result for any possible expression of this form. However, the function does not have to handle malformed expressions (i.e. ones with bad syntax).
Examples of expressions:
1 + 3 / -8 = -0.5 (No BODMAS) 2*3*4*5+99 = 219 4 * (9 - 4) / (2 * 6 - 2) + 8 = 10 1 + ((123 * 3 - 69) / 100) = 4 2.45/8.5*9.27+(5*0.0023) = 2.68...
I anticipate some form of "cheating"/craftiness here, so please let me forewarn against it! By cheating, I refer to the use of the eval or equivalent function in dynamic languages such as JavaScript or PHP, or equally compiling and executing code on the fly. (I think my specification of "no BODMAS" has pretty much guaranteed this however.) Apart from that, there are no restrictions. I anticipate a few Regex solutions here, but it would be nice to see more than just that.
Now, I'm mainly interested in a C#/.NET solution here, but any other language would be perfectly acceptable too (in particular, F# and Python for the functional/mixed approaches). I haven't yet decided whether I'm going to accept the shortest or most ingenious solution (at least for the language) as the answer, but I would welcome any form of solution in any language, except what I've just prohibited above!
I've now posted my C# solution here (403 chars). Update: My new solution has beaten the old one significantly at 294 chars, with the help of a bit of lovely regex! I suspected that this will get easily beaten by some of the languages out there with lighter syntax (particularly the funcional/dynamic ones), and have been proved right, but I'd be curious if someone could beat this in C# still.
I've seen some very crafty solutions already. Thanks to everyone who has posted one. Although I haven't tested any of them yet, I'm going to trust people and assume they at least work with all of the given examples.
Just for the note, re-entrancy (i.e. thread-safety) is not a requirement for the function, though it is a bonus.
Please post all answers in the following format for the purpose of easy comparison:
Language
Number of characters: ???
Fully obfuscated function:
(code here)Clear/semi-obfuscated function:
(code here)Any notes on the algorithm/clever shortcuts it takes.
Number of characters: 167 106 (see below for the 106 character version)
Fully obfuscated function: (167 characters if you join these three lines into one)
sub e{my$_="($_[0])";s/\s//g;$n=q"(-?\d++(\.\d+)?+)";
@a=(sub{$1},1,sub{$3*$6},sub{$3+$6},4,sub{$3-$6},6,sub{$3/$6});
while(s:\($n\)|(?<=\()$n(.)$n:$a[7&ord$5]():e){}$_}
Clear/deobfuscated version:
sub e {
my $_ = "($_[0])";
s/\s//g;
$n=q"(-?\d++(\.\d+)?+)"; # a regex for "number", including capturing groups
# q"foo" in perl means the same as 'foo'
# Note the use of ++ and ?+ to tell perl
# "no backtracking"
@a=(sub{$1}, # 0 - no operator found
1, # placeholder
sub{$3*$6}, # 2 - ord('*') = 052
sub{$3+$6}, # 3 - ord('+') = 053
4, # placeholder
sub{$3-$6}, # 5 - ord('-') = 055
6, # placeholder
sub{$3/$6}); # 7 - ord('/') = 057
# The (?<=... bit means "find a NUM WHATEVER NUM sequence that happens
# immediately after a left paren", without including the left
# paren. The while loop repeatedly replaces "(" NUM WHATEVER NUM with
# "(" RESULT and "(" NUM ")" with NUM. The while loop keeps going
# so long as those replacements can be made.
while(s:\($n\)|(?<=\()$n(.)$n:$a[7&ord$5]():e){}
# A perl function returns the value of the last statement
$_
}
I had misread the rules initially, so I'd submitted a version with "eval". Here's a version without it.
The latest bit of insight came when I realized that the last octal digit in the character codes for +, -, /, and * is different, and that ord(undef) is 0. This lets me set up the dispatch table @a as an array, and just invoke the code at the location 7 & ord($3).
There's an obvious spot to shave off one more character - change q"" into '' - but that would make it harder to cut-and-paste into the shell.
Number of characters: 124 106
Taking edits by ephemient into account, it's now down to 124 characters: (join the two lines into one)
sub e{$_=$_[0];s/\s//g;$n=q"(-?\d++(\.\d+)?+)";
1while s:\($n\)|$n(.)$n:($1,1,$3*$6,$3+$6,4,$3-$6,6,$6&&$3/$6)[7&ord$5]:e;$_}
Number of characters: 110 106
The ruby solution down below is pushing me further, though I can't reach its 104 characters:
sub e{($_)=@_;$n='( *-?[.\d]++ *)';
s:\($n\)|$n(.)$n:(($1,$2-$4,$4&&$2/$4,$2*$4,$2+$4)x9)[.8*ord$3]:e?e($_):$_}
I had to give in and use ''. That ruby send trick is really useful for this problem.
Number of characters: 106
A small contortion to avoid the divide-by-zero check.
sub e{($_)=@_;$n='( *-?[.\d]++ *)';
s:\($n\)|$n(.)$n:($1,0,$2*$4,$2+$4,0,$2-$4)[7&ord$3]//$2/$4:e?e($_):$_}
Here's the test harness for this function:
perl -le 'sub e{($_)=@_;$n='\''( *-?[.\d]++ *)'\'';s:\($n\)|$n(.)$n:($1,0,$2*$4,$2+$4,0,$2-$4)[7&ord$3]//$2/$4:e?e($_):$_}' -e 'print e($_) for @ARGV' '1 + 3' '1 + ((123 * 3 - 69) / 100)' '4 * (9 - 4) / (2 * 6 - 2) + 8' '2*3*4*5+99' '2.45/8.5*9.27+(5*0.0023) ' '1 + 3 / -8'