13,143,985 members (33,976 online)
Tip/Trick
alternative version

#### Stats

9.4K views
7 bookmarked
Posted 9 Dec 2012

# Shunting Yard in C#

, 12 Mar 2013
 Rate this:
An implementation of the Shunting yard algorithm.

## Introduction

The Shunting yard algorithm takes an expression, e.g., 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 and evaluates it in RPN.

## Background

I was looking for a Shunting yard algorithm in C# for a web development project to lexical analyse XHTML code. As I was unable to find anything I spent some time writing code to solve my problem. I think others can use it as well.

An good article on the Shunting yard algorithm can be found at Wikipedia http://en.wikipedia.org/wiki/Shunting-yard_algorithm .

## Using the code

To use the code we have to make a new class inheriting from my class `ShuntingYardBase<Result,Input>`, where `Result` is the type returned from the code, and `Input` is the type of source, normally `String`, but can be any type including your own list of classes.

Then we have to implement some virtual functions:

This is from my demo code - a simple math evaluator.

```public override double Evaluate(double result1, char opr, double result2)
{
if (!Oprs.ContainsKey(opr))
throw new Exception("Wrong operator!!");
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);
}
return base.Evaluate(result1, opr, result2);
}```

After implementing all the virtual functions (see the code example), use the object:

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

## Points of Interest

It is interesting that this code also can be used to lexical analyze source code, C# , HTML, etc.

## Share

 Software Developer Denmark
Software developer

## You may also be interested in...

 First Prev Next
 No Code? FatCatProgrammer10-Dec-12 3:45 FatCatProgrammer 10-Dec-12 3:45
 Re: No Code? Søren Gullach12-Dec-12 2:54 Søren Gullach 12-Dec-12 2:54
 Last Visit: 31-Dec-99 18:00     Last Update: 21-Sep-17 20:33 Refresh 1

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

Web04 | 2.8.170915.1 | Last Updated 12 Mar 2013
Article Copyright 2012 by Søren Gullach