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 など。
から 1 つの数値を取り出し_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が表示されると、後続のすべてのオペランドと操作がそれに渡されます。が閉じ括弧操作を受け取るように準備を行う必要がありますShuntingYard。トップレベルのものはエラーをスローし、内部のものは自分自身を評価し、包含Operandをその評価の結果に置き換えます。

于 2013-03-14T14:08:31.907 に答える