12,244,103 members (56,714 online)
Tip/Trick
Add your own
alternative version

20K views
3 downloads
15 bookmarked
Posted

# Shunting Yard algorithm in C#

, 26 Mar 2012 CPOL
 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)

## About the Author

 Software Developer Denmark
Software developer

## Comments and Discussions

 First Prev Next
 Mixing up terms? Andreas Gieriet21-Mar-12 14:44 Andreas Gieriet 21-Mar-12 14:44
 Re: Mixing up terms? A.J.Wegierski22-Mar-12 22:41 A.J.Wegierski 22-Mar-12 22:41
 Re: Mixing up terms? Andreas Gieriet23-Mar-12 2:01 Andreas Gieriet 23-Mar-12 2:01
 Re: Mixing up terms? Søren Gullach23-Mar-12 1:03 Søren Gullach 23-Mar-12 1:03
 Re: Mixing up terms? Andreas Gieriet23-Mar-12 1:29 Andreas Gieriet 23-Mar-12 1:29
 Thoughts PIEBALDconsult21-Mar-12 7:34 PIEBALDconsult 21-Mar-12 7:34
 Re: Thoughts Søren Gullach23-Mar-12 1:07 Søren Gullach 23-Mar-12 1:07
 Last Visit: 31-Dec-99 19:00     Last Update: 1-May-16 5:50 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    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
Web01 | 2.8.160426.1 | Last Updated 26 Mar 2012
Article Copyright 2012 by Søren Gullach
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid