Click here to Skip to main content
11,797,355 members (70,860 online)
Click here to Skip to main content

Shunting Yard algorithm in C#

, 26 Mar 2012 CPOL 17.7K 2 15
Rate this:
Please Sign up or sign in to vote.
A Shunting yard algorithm in C#


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


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"));

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.


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


About the Author

Søren Gullach
Software Developer
Denmark Denmark
Software developer

You may also be interested in...

Comments and Discussions

SuggestionMixing up terms? Pin
Andreas Gieriet21-Mar-12 13:44
memberAndreas Gieriet21-Mar-12 13:44 
GeneralRe: Mixing up terms? Pin
A.J.Wegierski22-Mar-12 21:41
memberA.J.Wegierski22-Mar-12 21:41 
GeneralRe: Mixing up terms? Pin
Andreas Gieriet23-Mar-12 1:01
memberAndreas Gieriet23-Mar-12 1:01 
GeneralRe: Mixing up terms? Pin
Søren Gullach23-Mar-12 0:03
memberSøren Gullach23-Mar-12 0:03 
GeneralRe: Mixing up terms? Pin
Andreas Gieriet23-Mar-12 0:29
memberAndreas Gieriet23-Mar-12 0:29 
QuestionThoughts Pin
PIEBALDconsult21-Mar-12 6:34
memberPIEBALDconsult21-Mar-12 6:34 
AnswerRe: Thoughts Pin
Søren Gullach23-Mar-12 0:07
memberSø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 | Terms of Use | Mobile
Web02 | 2.8.151002.1 | Last Updated 26 Mar 2012
Article Copyright 2012 by Søren Gullach
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid