Code Golf: Evaluating Mathematical Expressions
- by Noldorin
Challenge
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...
Rules
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!
My Solution
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.
Update
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.
Format
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.