0

A のように与えられた一連のトランプをフォーム B に変換して、結果 C を生成できるようにしたいと考えています。

A: "(AK,AQ,(A2:*h*h)):*s*s!AsQs,(JJ:*s*h)"
B: (((AsKs union AsQs union (A2 intersect hand with two hearts)) intersect hand with two spades) less AsQs) union (JJ intersect hand with one spade one heart)
C: AsKs,JsJh

操作の優先順位は

  • 1) 括弧、「()」
  • 2) 交差して少なくする (左結合), ':!'
  • 3) 結合、「、」

Intersect("AA", "*s*s") == "AsAs" など、B で操作を実行する機能がありますが、フォーム A からフォーム B の入力とCに到達するために順番に実行できる関連操作。

私はIronyやその他のレクサー/パーサーのソリューションを見てきましたが、この問題には少しやり過ぎのようです。もっと簡単な解決策はありますか？

  • おそらく、操作を表すノードを持つツリーに文字列を再帰的に分割しますか?
  • 文字列を優先順位の逆順に分解し、スタックにプッシュしますか? もしそうなら、これはどのように（大まかに）実装できますか？

私がエミュレートしようとしているものの実際の例をここに示します。A の構文の詳細については、こちらを参照してください。

4

2 に答える 2

2

解析Aして命令のツリーを構築し、リーフから開始して実行することができます (最も内側の括弧の内容を最初に実行したいと思うと思います)。この解析タスクでは、正規表現またはその他の必要なものを使用できます。頭のてっぺんから、最初に括弧と演算子記号を探してツリー構造を把握し、次に各リーフに実際の初等命令を入力し、各ジャンクションに演算子を入力することができると思います。

データ構造の格納は、インターフェイスを実装するAオブジェクト (それらを と呼びます) で構成できます。それぞれに 3 つのフィールドが必要です。ExpressionIOperandExpression

  1. Operatorのインスタンスであるフィールドenum Operations {Union, Intersection, SetDiff}、または好みに応じて単なる文字列です。
  2. 2 つのフィールドOperand1とOperand2は、「Ah」(カードのセットを定義する) のようなものか、別の のいずれかExpressionです。したがって、これらは のインスタンスとして宣言する必要がありますIOperand。

"Ah" のように 1 組のカードを保持するクラスも、これを実装する必要がありますIOperand。インターフェイスIOperand自体は、実際には何もする必要はありません。

与えられた各命令を操作に一致させるには、単純なスイッチを使用するか、代わりにDictionaryof string(またはenum) to を使用してから、 with (匿名) 関数 ( の命令を含む) をdelegate IOperand SetOp(IOperand, IOperand);入力します。DictionaryB

このDictionary場合、単純に実行できinstructionList[thisExpression.Operation](thisExpression);(これはおそらく、2 回の参照を避けるためにもう少しエレガントに行うことができますthisExpression)、文字列入力の適切な C# 変換が実行されます。

コンセプトの証明

ここで使用方法を示すために、基本的な実装とコンソール アプリを作成しました: https://bitbucket.org/Superbest/lexer

正気を保ったまま演習全体を進めることに成功した場合 (コンピューターはあなたを代理解析および操作ライブラリとして使用するので、頑張ってください)、最後のステップで、等しい式を評価し、C何を出力するかを尋ねられるはずです。あなたはちょうどあなたに戻ってきました。(初めて実行するときは、プログラムの指示に従う必要があるかもしれません。コードを壊して多くの例外を取得するのは非常に簡単だと思います。無効なプログラムに何が起こったのかを考えようとすると、非常に混乱します。入力。）

コードをそのまま実行している場合は、次の一連の回答を試してください (, = Enter)。

n, y, 2, n, n, n, y, 2, n, n, y, n, y, 2, n, n, n, n, alpha, beta, gamma

出力は次のようになります。

gamma

廃止されたとマークされたメソッドの本体を簡単に更新して、動作するプログラムを作成できるはずです。

さらに二項演算を追加したい場合は、 の本文の TODO を参照してくださいSimplification.Simplification()。適切な構文は、既に行った 3 つの操作を見れば明らかです。現状では、コードはバイナリ操作のみをサポートしています。メソッドが文字列を使用する場合は、SimplifiedOperand.Symbolフィールドを使用できます。

于 2012-08-29T19:09:44.547 に答える
1

私はこれを解決策として思いついた（Superbestの答えからのツリーのアイデアを使用して）。変更することについてのコメントをいただければ幸いです。

  • 入力： "AsQs、（JJ！ss：xy）、（AA：xy！ss）"
  • プリティプリント出力：AsQs union（（（JJ less ss）intersection xy）union（（AAintersection xy）less ss））

public class Node

{
    private string mStr;
    private string mOperation;
    private List mChildren = new List();
    //private Collection mCollection = new Collection();

    public Node(string input)
    {
        mStr = Regex.Replace(input, @"^\(([^\(\)]*)\)$", "$1");

        Init();
    }

    private void Init()
    {
        Split(mStr);

        return;
    }

    public Collection GenerateHands()
    {
        Collection collection = new Collection();

        if (Children == 0) { collection.Add(mStr); }

        if (Children > 0)
        {
            if (mOperation == "union") { collection = mChildren.ElementAt(0).GenerateHands().Union(mChildren.ElementAt(1).GenerateHands()); }
            if (mOperation == "intersect") { collection = mChildren.ElementAt(0).GenerateHands().Intersect(mChildren.ElementAt(1).GenerateHands()); }
            if (mOperation == "less") { collection = mChildren.ElementAt(0).GenerateHands().Less(mChildren.ElementAt(1).GenerateHands()); }
        }

        return collection;
    }

    public string PrettyPrint()
    {
        string print = "";

        if (Children == 0) { print += mStr; }

        if (Children > 0)
        {
            if (mChildren.ElementAt(0).Children > 0) { print += "("; }
            print += mChildren.ElementAt(0).PrettyPrint();
            if (mChildren.ElementAt(0).Children > 0) { print += ")"; }
            if (Children > 0) { print += " " + mOperation + " "; }
            if (mChildren.ElementAt(1).Children > 0) { print += "("; }
            print += mChildren.ElementAt(1).PrettyPrint();
            if (mChildren.ElementAt(1).Children > 0) { print += ")"; }
        }

        return print;
    }

    private void Split(string s)
    {
        // WARNING: Either could pass a,aa or a:aa

        // WARNING: This can hand down a 0 length string if ',' is at beginning or end of s.
        if (CommaOutsideBrackets(s) >= 0)
        {
            mChildren.Add(new Node(s.Substring(0, CommaOutsideBrackets(s))));
            mChildren.Add(new Node(s.Substring(CommaOutsideBrackets(s) + 1, s.Count() - CommaOutsideBrackets(s) - 1)));

            mOperation = "union";
        }

        // WARNING: This could throw negative if for example (aaaa)bb
        else if (OperatorOutsideBrackets(s) >= 0)
        {
            mChildren.Add(new Node(s.Substring(0, OperatorOutsideBrackets(s))));
            mChildren.Add(new Node(s.Substring(OperatorOutsideBrackets(s) + 1, s.Count() - OperatorOutsideBrackets(s) - 1)));

            if (s[OperatorOutsideBrackets(s)] == '!') { mOperation = "less"; }
            if (s[OperatorOutsideBrackets(s)] == ':') { mOperation = "intersection"; }
        }

        // We must be done?
        else
        {
        }
    }

    private int CommaOutsideBrackets(string s)
    {
        int countRound = 0, countSquare = 0;

        for (int i = 0; i = 0; i--)
        {
            if (s[i] == '!' || s[i] == ':') { return i; }
        }

        return -1;
    }

    public string Str
    {
        get { return mStr; }
    }

    public int Children
    {
        get { return mChildren.Count; }
    }
}

于 2012-08-30T01:03:24.797 に答える