建模：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 { }
例如平方根、正弦、余弦等
从 _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);
}

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

---

我应该如何建立模型以便在括号被推入时跟踪和处理它们？

另外，将括号视为“操作”似乎对我来说没有多大意义。然而，维基百科上的算法是这样处理它们的，我想不出其他方法来跟踪它们相对于其他“真实”操作的位置。

谢谢。

- user807566

---

为什么您不想在设计中特殊处理括号，而在应用程序中明显需要特殊处理它们呢？我的意思是，我相信您可以想出某种抽象概念，使其不再是一个特例，但除非您知道还有更多类似方式需要处理的结构，否则这听起来像是过度设计。 - millimoose

@PieterGeerkens Shunting-Yard算法解析中缀表达式，逆波兰表示法只是其可能的输出之一。 - millimoose

听起来你想让每个左括号都开启自己的ShuntingYard对象。当你遇到右括号时，你可以完成解析该序列并返回到之前的序列。 - StarPilot

@millimoose 我并不反对特殊情况的处理，事实上，我相信可能没有其他方法。但是，如果可能的话，我想避免在运行时检查类型（出于可移植性的原因），而且我不希望要求每个后续的“Operation”声明它是否为圆括号（如果这样的要求是可能的）。--编辑：我明白你的意思了。你是对的，我可能有点过度工程化了。不过，我还是想先探索一下我的选择。 - user807566

“Peek”是一个非常重要的操作，如果我理解你的意思正确的话。假设用户输入了“34+5”，结果为“17”。当他们输入“”时，您会显示什么？然后当他们输入“6”时，您必须撤消加法以获取“5”回来，以便将其乘以“6”；然后重新执行加法以获得“42”。一般来说，您可能需要准备好展开与优先级级别相同的堆栈。使用不可变数据结构可以相对简单地解决这个问题，但使用C#可变的“stack”则更难。 - rici

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。

- Vesper