Tuesday, November 23, 2010

Postfix expression parser.

A question on DreamInCode lead me to my old nemesis, the Postfix expression parser. I'd fallen in love with a Reverse Polish Notation calculator in high school (the HP-32SII, they sadly don't make them anymore). When I tried to program a RPNC to use on my PC years ago, I failed miserably. But I've learned a lot since then, and I figured I could at least try a simple postfix parser.

It wasn't that bad. You don't have to check for a lot of things a calculator does. Here's the body of the code. I made it static, since you really don't need to instantiate it. If I ever make it into a calculator, I'd probably make it non-static, and make the stack a class-level field.

class PostfixParser
{
    const string Placeholder = "[x]";

    private static Dictionary<string, Func<double, double, double>> op;

    private static List<string> operators = new List<string>() { "+", "-", "*", "/" };

    static PostfixParser()
    {
        op = new Dictionary<string, Func<double, double, double>>();
        op.Add("+", (x, y) => x + y);
        op.Add("-", (x, y) => x - y);
        op.Add("*", (x, y) => x * y);
        op.Add("/", (x, y) => x / y);
        op.Add("^", (x, y) => Math.Pow(x, y));
    }

    public static double ParseExp(string exp, double? val)
    {
        string[] tokens = exp.Split(new string[] { " " } , StringSplitOptions.RemoveEmptyEntries);
        if (tokens.Contains(Placeholder) && val == null)
            throw new InvalidOperationException("Placeholder token detected in expression, but parameter \"val\" was null.");
        Stack<double> stack = new Stack<double>();
        foreach (string token in tokens)
        {
            if (operators.Contains(token))
            {
                if (stack.Count < 2)
                    throw new InvalidOperationException("Operator imbalance.");
                double y = stack.Pop();
                double x = stack.Pop();
                stack.Push(op[token](x, y));
            }
            else
            {
                double n;
                if (token == Placeholder)
                    n = val.Value;
                else if (!double.TryParse(token, out n))
                    throw new InvalidOperationException("Invalid token detected: " + token);
                stack.Push(n);
            }
        }

        if (stack.Count > 1)
            throw new InvalidOperationException("More than one result on the stack.");
        if (stack.Count < 1)
            throw new InvalidOperationException("No results on the stack.");
        return stack.Pop();
    }

    public static double ParseExp(string exp)
    {
        return ParseExp(exp, null);
    }
}

This can be used like this:
string fToCExp = "5 9 / [x] 32 - *";
string cToFExp = "9 5 / [x] * 32 + ";
Console.WriteLine("100C converted to F:");
Console.WriteLine(PostfixParser.ParseExp(cToFExp, 100));
Console.WriteLine("32F converted to C:");
Console.WriteLine(PostfixParser.ParseExp(fToCExp, 32));
Console.ReadKey();

To give an output of:

100C converted to F:
212
32F converted to C:
0

You could add more operators if you wished, like a 1/x or a SQRT, but since most other operators are unary rather than binary, you'd have to change your popping logic.

Note: I did it with a placeholder value in mind. I used "[x]" for whatever reason, but it could be anything that won't parse into a double by itself or match one of the operators. You could remove this altogether, if you cared to.

No comments:

Post a Comment

Speak your mind.