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

Dynamic CSS for ASP.NET

I’ve recently being doing a bit of web development in ASP.NET and came across (as all web developers must commonly do) the problem of catering for IE’s poor standards compliance regarding rendering/CSS stylesheets. The common solution to the problem is to use CSS hacks, which perform some magic to get pages in IE looking as they ought to appear whilst still displaying correctly in good browsers (Firefox, Safari, etc.). When this fails as it often does, the best (yet slightly horrible) solution is to create separate stylesheets for IE (and possibly for different versions) and then put conditional tags around the references the CSS file(s) in the HTML head section.

<link rel="Stylesheet" type="text/css" href="StyleSheet.css" />
<!--[if lte IE 7]>
<link rel="Stylesheet" type="text/css" href="StyleSheet-IE.css" />
<![endif]-->

This particular example only includes the stylesheet StyleSheet-IE.css if the browser version is less than or equal to IE 7.0 (whereas StyleSheet.css is always linked). Note that the conditional tags can be put around any HTML element so that they are only read when the browser matches the specified conditions. It can sometimes be useful to wrap JavaScript blocks with them.

The latter solution has until now worked well for all my purposes, though a more concise and elegant way of presenting variations of the CSS code to different browsers has always been asking. The problem arose when I was trying to reference stylesheets for ASP.NET themes (CSS files under the App_Themes folder) – because the ASP.NET runtime dynamically adds links to the stylesheets according to the current theme, there’s no way (that I could find) to implement the previous solution using conditional tags.

My own solution was to create a Dynamic CSS processor which runs on the server to process any CSS file according to the browser type/version before returning the content. I have implemented the processor as an HTTP handler that can enabled by a simple reference in the web.config file. The basic idea is similar to conditional tags in HTML, but instead the tags are in the actual CSS code and have the syntax.

[[?[!]{browser} {true result} | {false result}]]

The browser expression is simply the name of the browser for which to check (e.g. “IE”, “Firefox”) and can optionally be preceded by a ‘!’ symbol to invert the condition. The statement is simply evaluated to {true result} if the condition is found to be true, and {false result} otherwise. It can be applied to whole or parts of CSS declarations, but it is important to enclose one or more tags in comment tags (“/*” and “*/”) to avoid syntax errors generated by the IDE. The processor will not recognise the statement unless it is inclosed in comment tags.

Example:

div.main
{
    /* margin-top: [[?IE -4px | 0 ]] */
}

Unfortunately I haven’t yet gotten round to implementing checking of browser version, but it is certainly something on my task list and I will post an update once it gets done.

The code for the HTTP handler is reasonably short and mainly involves RegEx expressions for parsing the CSS files with some lambda expressions for reducing the number of functions/loops. A caching feature is implemented to save the server from reprocessing a CSS file each time it is requested even when the file has remained unchanged.

You can view the full code for the HTTP handler here. Simply copy it to the App_Code folder and add the following references to web.config (the first is for II 6/Visual Studio test server and the second is for IIS 7).

<system.web>
    <httpHandlers>
        <add verb="*" path="*.css" type="StyleSheetHandler"/>
    </httpHandlers>
</system.web>
<system.webServer>
    <handlers>
        <add name="StyleSheetHandler" verb="*" path="*.css" type="StyleSheetHandler"/>
    </handlers>
</system.webServer>

Feedback is welcome and I would be glad to hear if anyone is using this in their web projects.