c# - 调车场算法建模

Question

背景:

我正在尝试实现 Shunting-Yard Algorithm 的变体，但不是以 RPN 表示法输出表达式，我希望它在插入 token 时更新自身，以便可以实时显示结果(就像您按下计算器上的按钮并需要在之后更新显示一样每个按钮)。

这是 Shunting-Yard 类...

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)类 NullaryOperation:操作 {}
例如。 Pi、e等
只需将常量压入 _operands

公共(public)类 UnaryOperation:操作 {}
例如。平方根、正弦、余弦等
从 _operands 弹出一个数字，计算结果并将结果推送到 _operands

公共(public)类 BinaryOperation:操作 {}
例如。 +、-、*、/等
检查优先级，在需要时进行评估，将结果推送到 _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 接收右括号操作做准备，顶层应该抛出错误，内部应该 self 评估并替换包含 Operand及其评估结果。