Modeling The Shunting-Yard Algorithm

Question

Background:

I am trying to implement a variant of the Shunting-Yard Algorithm, 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).

Here is the Shunting-Yard class...

public class ShuntingYard
{
   private Stack<double> _operands;
   private Stack<Operation> _operations;

   public ShuntingYard()
   {
      this._operands = new Stack<double>();
      this._operations = new Stack<double>();
   }
}

And the Operation class would be something like...

public abstract class Operation
{
   public abstract void Evaluate(Stack<double> operands, Stack<Operation> operations);
}

The Evaluate() function updates the stacks accordingly, and the "current value" would be _operands.Peek()

Here are some of the "Operations" I have so far:

public class NullaryOperation : Operation { }
E.g. Pi, e, etc.
Just pushes constant onto _operands

public class UnaryOperation : Operation { }
E.g. SquareRoot, Sine, Cosine, etc.
Pops one number off of _operands, evaluates, and pushes result to _operands

public class BinaryOperation : Operation { }
E.g. +, -, *, /, etc.
Checks precedence, evaluates if needed, pushes result to _operands

---

Here is the problem:
I need the ability to push open-parentheses ( and closed-parentheses ) onto the _operations 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.

I want to avoid checks like this (checking object types):

while (operations.Peek().GetType() != typeof(OpenParen)) { ... }

I want to avoid adding a method like this in Operation:

public abstract bool IsOpenParen();

I could do something like this...

public abstract class Operation 
{
   public enum OperationType { Nullary, Unary, Binary, OpenParen, CloseParen };
   public abstract OperationType GetOperationType() { };

   public abstract void Evaluate(Stack<double> operands, Stack<Operation> operations);
}

But requiring all subtypes to specify their type as an enum seems like a bad design.

---

How should I model this in such a way that I can track and handle parentheses as they are pushed in?

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.

Thank you.

Answer 1

public class Operand {
    private ShuntingYard sy;
    private double d;
    public Operand(double v) {
        d=v;
        sy=null;
    }
    public Operand() {
        d=NaN(); // I'm inept at C#, this should mean "d" is unused
        sy=new ShuntingYard();
    }
}
public class ShuntingYard {
    private Stack<Operand> _operands;
    private Stack<Operation> _operations;

   public ShuntingYard()
   {
      this._operands = new Stack<Operand>();
      this._operations = new Stack<Operation>();
   }
}

StarPilot gives a correct advice, putting another ShuntingYard into the stack, but the correct way is to put a ShuntingYard as an operand, not as an operation. Now, once a nested ShuntingYard appears, all subsequent operands and operations are passed to it. A preparation should be made in order for a ShuntingYard to receive a closing parenthesis operation, a top-level one should throw an error, and the inner ones should evaluate themselves and replace containing Operand with the result of its evaluation.