Shunting-Yard算法建模

Question

背景:

我正在尝试实现Shunting-Yard算法的变体,但不是以RPN表示法输出表达式,我希望它能够在推入标记时自动更新,以便结果可以实时显示(就像你按下计算器上的按钮,需要在每个按钮后更新显示器).

这是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 class NullaryOperation : Operation { }
例如Pi,e等.
只需按常数_operands

public class UnaryOperation : Operation { }
例如SquareRoot,Sine,Cosine等.弹出
一个数字_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放入堆栈中，但正确的方法是将aShuntingYard作为操作数，而不是作为操作。现在，一旦出现嵌套ShuntingYard，所有后续操作数和操作都会传递给它。应该做好准备，以便 aShuntingYard接收右括号操作，顶级操作应该抛出错误，内部操作应该评估自身并Operand用其评估结果替换包含。