Shunting Yard algorithm in C#

Introduction

I was looking for some Shunting Yard code in C#, to solve a lexical analyze problem in a project for a Web developer platform. As I was unable to find any code, I have made some myself, maybe it's of interest to others.

At Wikipedia is an excelent article about Shunting Yard http://en.wikipedia.org/wiki/Shunting-yard_algorithm

Background

The idea of Shunting Yard is to take an expression i.e 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 and evaluate it as a RPN to get the correct order of evaluation.

The code presented here is an abstract templated class that makes the RPN stack and evaluates it.

Using the code

To use the code make a new class inheriting from my base class:

public abstract class ShuntingYardBase<TResult, TInput>

The TResult being the return type of the expression, and TInput is the type of input, normaly a string but it can also be a list of you own objects,

and implement the abstract functions,
here is an example from my demo project:

Create a dictionary with the operators, precedence and Associativity.

    public class ShuntingYardSimpleMath : ShuntingYardBase<double, string>
    {
        Dictionary<char> Oprs = new Dictionary<char>() 
        {
            { '+', new PrecedensAssociativity(2,PrecedensAssociativity.Asso.Left)},
            { '-', new PrecedensAssociativity(2,PrecedensAssociativity.Asso.Left)},
            { '*', new PrecedensAssociativity(3,PrecedensAssociativity.Asso.Left)},
            { '/', new PrecedensAssociativity(3,PrecedensAssociativity.Asso.Left)},
            { '^', new PrecedensAssociativity(4,PrecedensAssociativity.Asso.Right)},
        };

.. and implement the abstract functions. Evaluate result1 and result2 with operator.

        public override double Evaluate(double result1, char opr, double result2)
        {
            switch (opr)
            {
                case '+':
                    return (double)result1 + result2;
                case '-':
                    return (double)result1 - result2;
                case '*':
                    return (double)result1 * result2;
                case '/':
                    return (double)result1 / result2;
                case '^':
                    return Math.Pow(result1, result2);
            }
            throw new Exception("Wrong operator!!");
        }

.. typecast input type to result type, optional using you TagObj.

        public override double TypecastIdentifier(string input, object TagObj)
        {
            double result;
            if (double.TryParse(input, out result))
                return result;
            throw new Exception("Wrong identifier!!");
        }

.. Is what I have an identifier?

        public override bool IsIdentifier(string input)
        {
            double result;
            return double.TryParse(input, out result);
        }

.. Is what I have an operator?

        public override bool IsOperator(char? opr)
        {
            if(opr == null) return false;
            return Oprs.ContainsKey((char)opr);
        }

.. type cast operator from input type to operator type "char"

        public override char? TypecastOperator(string input)
        {
            if (!Oprs.ContainsKey(input[0]))
                return null;
            return (char?)input[0];
        }

.. has operator left or right Associativity.

        public override PrecedensAssociativity.Acc Association(char opr)
        {
            if (!Oprs.ContainsKey(opr))
                throw new Exception("Wrong operator!!");
            return Oprs[opr].Asso;
        }

.. return -1,0 or 1 according to precedence.

        public override int Precedence(char opr1, char opr2)
        {
            if (!Oprs.ContainsKey(opr1))
                throw new Exception("Wrong operator!!");
            if (!Oprs.ContainsKey(opr2))
                throw new Exception("Wrong operator!!");
            if (Oprs[opr1].Prece > Oprs[opr2].Prec) return 1;
            if (Oprs[opr1].Prec < Oprs[opr2].Prec) return -1;
            return 0;
        }

.. Filter out noise in the input list (blanks, NL, CR etc.)

        public override bool IsNoise(string input)
        {
            return false;
        }

and the use the code

   ShuntingYardSimpleMath SY = new ShuntingYardSimpleMath();
   String s = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3";
   Console.WriteLine("input: {0}", s); Console.WriteLine();
   List<String> ss = s.Split(' ').ToList();
   SY.DebugRPNSteps += new ShuntingYardBase<double, string>.DebugRPNDelegate(SY_DebugRPNSteps);
   SY.DebugResSteps += new ShuntingYardBase<double, string>.DebugResDelegate(SY_DebugResSteps);
   Double res = SY.Execute(ss, null);
   bool ok = res == 3.0001220703125;
   Console.WriteLine("input: {0} = {1} {2}", s, res, (ok ? "Ok" : "Error"));
   Console.ReadKey();

This snippet writes the RPN stack and evaluation stack out on the console.

Points of Interest

It's interesting that this code also can be used as a part of a lexical analyser for source code, C# XHTML etc.

I make an article on this later.