调车场算法建模

Question

背景：

我正在尝试实现分流场算法的一个变体，但我不希望以RPN表示法输出表达式，而是希望它在推送令牌时更新自己，以便实时显示结果(就像你在按下计算器上的按钮，需要在每个按钮后更新显示一样(。

这是调车场班。。。

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

而Operation类则类似于。。。

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

Evaluate()函数相应地更新堆栈，"当前值"将为_operands.Peek()

以下是我迄今为止的一些"操作"：

public class NullaryOperation : Operation { }
例如Pi、E等
只是将常量推到_operands 上

public class UnaryOperation : Operation { }
例如平方根、正弦、余弦等
从_operands弹出一个数字，进行评估，并将结果推送到_operands

public class BinaryOperation : Operation { }
例如+、-、*、/等
检查优先级，必要时进行评估，将结果推送到_operands

---

问题是：
作为算法的一部分，我需要能够将开括号(和闭括号)推送到_operations堆栈上。此外，当我添加一个闭括号时，我需要不断弹出操作数/运算，直到遇到一个开括号。

我想避免这样的检查(检查对象类型(：

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

我想避免在Operation:中添加这样的方法

public abstract bool IsOpenParen();

我可以做这样的事。。。

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

但是，要求所有子类型将其类型指定为枚举似乎是一个糟糕的设计。

---

我应该如何建模，以便在插入括号时跟踪和处理括号？

顺便说一句：对我来说，把括号看作"运算"似乎没有多大意义。然而，维基百科上的算法是这样对待它们的，我想不出任何其他方法来跟踪它们相对于其他"真实"运算的位置。

谢谢。

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给出了一个正确的建议，将另一个ShuntingYard放入堆栈，但正确的方法是将ShuntingYard作为操作数，而不是运算。现在，一旦嵌套的ShuntingYard出现，所有后续的操作数和运算都会传递给它。应该做好准备，让ShuntingYard接收右括号运算，顶级的应该抛出错误，内部的应该自己求值，并用求值结果替换包含的Operand。