Click here to Skip to main content
Click here to Skip to main content
Go to top

Shunting Yard algorithm in C#

, 26 Mar 2012
Rate this:
Please Sign up or sign in to vote.
A 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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Søren Gullach
Software Developer
Denmark Denmark
Software developer
Follow on   Twitter

Comments and Discussions

 
SuggestionMixing up terms? PinmemberAndreas Gieriet21-Mar-12 13:44 
GeneralRe: Mixing up terms? PinmemberA.J.Wegierski22-Mar-12 21:41 
GeneralRe: Mixing up terms? PinmemberAndreas Gieriet23-Mar-12 1:01 
GeneralRe: Mixing up terms? PinmemberSøren Gullach23-Mar-12 0:03 
GeneralRe: Mixing up terms? PinmemberAndreas Gieriet23-Mar-12 0:29 
QuestionThoughts PinmemberPIEBALDconsult21-Mar-12 6:34 
AnswerRe: Thoughts PinmemberSøren Gullach23-Mar-12 0:07 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web01 | 2.8.140926.1 | Last Updated 26 Mar 2012
Article Copyright 2012 by Søren Gullach
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid