Code Golf: Evaluating Mathematical Expressions

Yesterday I happened to stumble across a code golf question and for no particular reason (except for perhaps boredom) decided to create my own problem and to post it on StackOverflow for the community to reply with their solutions. It actually turned out to be much more popular than I might have anticipated.

A quick definition of code golf for those who are unaware of this enormous (though really quite enjoyable) time sink:

The objective of code golf is simply to write a program/function that solves a given problem using the fewest possible number of characters. This usually involves clever tricks related to the problem and whatever language you use, followed by heavy obfuscation.

Here is the problem specification, copied from my StackOverflow post:

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...

Now, my own solution isn’t particularly astounding, but I did get it down to 403 characters, and have since cut off a few more (though haven’t bothered to re-obfuscate it). It is in fact my first proper attempt at code golf, so I don’t consider it too bad.

Here it is, in all its obfuscated ugliness:

float e(string x){float v=0;if(float.TryParse(x,out v))return v;x+=';';int t=0;char o,s='?',p='+';float n=0;int l=0;for(int i=0;i<x.Length;i++){o=s;if(
x[i]!=' '){s=x[i];if(char.IsDigit(x[i])|s=='.'|(s=='-'&o!='1'))s='1';if(s==')')
l--;if(s!=o&l==0){if(o=='1'|o==')'){n=e(x.Substring(t,i-t));if(p=='+')v+=n;
if(p=='-')v-=n;if(p=='*')v*=n;if(p=='/')v/=n;p=x[i];}t=i;if(s=='(')t++;}
if(s=='(')l++;}}return v;}

And in a rather more readable form (identical in behaviour):

float Eval(string expr)
{
    float val = 0;
    if (float.TryParse(expr, out val))
        return val;
    expr += ';';
    int tokenStart = 0;
    char oldState, state = '?', op = '+';
    float num = 0;
    int level = 0;
    for (int i = 0; i < expr.Length; i++)
    {
        oldState = state;
        if (expr[i] != ' ')
        {
            state = expr[i];
            if (char.IsDigit(expr[i]) || state == '.' ||
                (state == '-' && oldState != '1'))
                state = '1';
            if (state == ')')
                level--;
            if (state != oldState && level == 0)
            {
                if (oldState == '1' || oldState == ')')
                {
                    num = Eval(expr.Substring(tokenStart, i - tokenStart));
                    if (op == '+') val += num;
                    if (op == '-') val -= num;
                    if (op == '*') val *= num;
                    if (op == '/') val /= num;
                    op = expr[i];
                }
                tokenStart = i;
                if (state == '(')
                    tokenStart++;
            }
            if (state == '(')
                level++;
        }
    }
    return val;
}

The current leading solution in one written in Haskell (a mere 226 chars), with another in Python (237 chars) taking second place. This hardly surprises me – the functional and dynamic languages almost inevitably have more succinct syntax, besides generally being known to be more suitable for creating parsers. (If I hadn’t specified the absence of the BODMAS rules, I would have surely seen a solution containing little more than an “eval” statement!) Interestingly, the top two have both managed to avoid using regex altogether (though other solutions have with some success). In my opinion, it’s worth reading through the question to see how the various languages compare at performing the same task.

Please feel free to reply to the StackOverflow question or this post if you have a unique solution (in any language) that you’d like to share.

Update

I ended up spending just a bit longer on this task, since having seen some of the other solutions, it became pretty clear that I could get the char count down a good deal more. With the help of regex, my new solution stands at 294 characters. That in fact seems to be the winner amongst the set of solutions in C-style languages, so I’m quite pleased. (I have now promised myself not to entertain myself any long with this game, however.)

Here it is in a (relatively) clear form, in case anyone’s interested. (It assumes the System.Text.RegularExpressions namespace has been imported.)

float e(string x)
{
    while (x.Contains("("))
        x = Regex.Replace(x, @"\(([^\(]*?)\)", m => e(m.Groups[1].Value).ToString());

    float r = 0;
    foreach (Match m in Regex.Matches("+" + x, @"\D ?-?[\d.]+"))
    {
        var o = m.Value[0];
        var v = float.Parse(m.Value.Substring(1));
        r = o == '+' ? r + v : o == '-' ? r - v : o == '*' ? r * v : r / v;
    }
    return r;
}

http://stackoverflow.com/questions/928563/code-golf-evaluating-mathematical-expressions/944716#944716