title: Modeling The Shunting-Yard Algorithm
body: <p>Background:</p>
  
  <p>I am trying to implement a variant of the <a href="http://en.wikipedia.org/wiki/Shunting-yard_algorithm">Shunting-Yard Algorithm</a>, but instead of outputting the expression in RPN notation, I'd like it to update itself as tokens are pushed in so that results can be displayed in real time (as if you were pressing buttons on a calculator and needed to update the display after each button).</p>
  
  <p>Here is the Shunting-Yard class...</p>
  
  <pre><code>public class ShuntingYard
  {
     private Stack&lt;double&gt; _operands;
     private Stack&lt;Operation&gt; _operations;
  
     public ShuntingYard()
     {
        this._operands = new Stack&lt;double&gt;();
        this._operations = new Stack&lt;double&gt;();
     }
  }
  </code></pre>
  
  <p>And the <code>Operation</code> class would be something like...</p>
  
  <pre><code>public abstract class Operation
  {
     public abstract void Evaluate(Stack&lt;double&gt; operands, Stack&lt;Operation&gt; operations);
  }
  </code></pre>
  
  <p>The <code>Evaluate()</code> function updates the stacks accordingly, and the "current value" would be <code>_operands.Peek()</code></p>
  
  <p>Here are some of the "Operations" I have so far:</p>
  
  <p><code>public class NullaryOperation : Operation { }</code> <br />
  E.g. Pi, e, etc. <br />
  Just pushes constant onto <code>_operands</code></p>
  
  <p><code>public class UnaryOperation : Operation { }</code> <br />
  E.g. SquareRoot, Sine, Cosine, etc. <br />
  Pops one number off of <code>_operands</code>, evaluates, and pushes result to <code>_operands</code></p>
  
  <p><code>public class BinaryOperation : Operation { }</code> <br />
  E.g. +, -, *, /, etc. <br />
  Checks precedence, evaluates if needed, pushes result to <code>_operands</code></p>
  
  <hr>
  
  <p>Here is the problem: <br />
  I need the ability to push open-parentheses <code>(</code> and closed-parentheses <code>)</code> onto the <code>_operations</code> stack as part of the algorithm.  Moreover, when I add a closed-parenthesis, I need to keep popping operands/operations until I encounter an open-parenthesis.</p>
  
  <p>I want to avoid checks like this (checking object types):</p>
  
  <p><code>while (operations.Peek().GetType() != typeof(OpenParen)) { ... }</code></p>
  
  <p>I want to avoid adding a method like this in <code>Operation</code>:</p>
  
  <p><code>public abstract bool IsOpenParen();</code></p>
  
  <p>I could do something like this...</p>
  
  <pre><code>public abstract class Operation 
  {
     public enum OperationType { Nullary, Unary, Binary, OpenParen, CloseParen };
     public abstract OperationType GetOperationType() { };
  
     public abstract void Evaluate(Stack&lt;double&gt; operands, Stack&lt;Operation&gt; operations);
  }
  </code></pre>
  
  <p>But requiring all subtypes to specify their type as an enum seems like a bad design.</p>
  
  <hr>
  
  <p>How should I model this in such a way that I can track and handle parentheses as they are pushed in?</p>
  
  <p>On a side note: Thinking about parentheses as "Operations" doesn't seem to make much sense to me. However, the algorithm on Wikipedia treats them this way, and I can't think of any other way to keep track of their position relative to other "real" operations.</p>
  
  <p>Thank you.</p>