9

背景：

我正在尝试实现Shunting-Yard Algorithm的变体，但不是以 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);
}

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

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

附带说明：将括号视为“操作”对我来说似乎没有多大意义。但是，维基百科上的算法以这种方式对待它们，我想不出任何其他方式来跟踪它们相对于其他“真实”操作的位置。

谢谢你。

4

1 回答 1

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其评估结果替换包含。

于 2013-03-14T14:08:31.907 回答