5

私は、算術式を解析するための拡張された操車場アルゴリズムを実装してきました。アルゴリズムの1つの側面は、、、Queueおよびを維持することStackです。

私の実装では、QueuecontainsExpressionsとOperators。Stack含むOperatorsとParenthesis。_

Expressions、、、ParenthesisおよびOperatorsそれらのいずれか2つが共有インターフェイスを持つことを保証する共通点はありません。

アプローチ：

  • 私の現在の実装は、Expressionで構成さOperatorれていINotParanthesisます。OperatorをParanthesis実装しINotExpressionます。Queue <INotParanthesis>次に、、、およびを宣言しStack <INotExpression>ます。

    私はこの実装が好きではありません-これらのインターフェースは、よりクリーンなアルゴリズムコードを目的としたハックのようです。また、インターフェースは、オブジェクトではなく、オブジェクトが何であるかを記述する必要があると思います。

  • 一方、<Object>そのようなコードの正確さを確認するのは難しい場合があるため、のコレクションも使用したくありません。

  • これまでに思いついたのは、自分のコンテナNonParanthesisQueueとNonExpressionStackコンテナを実装することだけです。これには、オブジェクトがそれらのコンテナから引き出される際のより一貫性のある型チェックの利点と、より多くのコードの欠点があります。

私のアプローチに代わる合理的な方法はありますか？

4

2 に答える 2

5

本当に欲しいのは和型のようですね。C＃にはこれらが組み込まれていませんが、これを実現するためにチャーチエンコーディングと呼ばれる関数型プログラミングからのトリックがあります。キャストを含まない完全にタイプセーフですが、主に型推論の制限のために、C＃で使用するのは少し奇妙です。

Map主なトリックは、プロパティとチェックを使用して2つの選択肢のいずれかを取得する代わりに、2つの関数を引数として取り、存在する選択肢に応じて適切な関数を呼び出す高階関数を使用することです。使用方法は次のとおりです。

var stack = new Stack<IEither<Operator, Parenthesis>>();

stack.Push(new Left<Operator, Parenthesis>(new Operator()));
stack.Push(new Right<Operator, Parenthesis>(new Parenthesis()));

while (stack.Count > 0)
{
    stack.Pop().Map(op  => Console.WriteLine("Found an operator: " + op),
                    par => Console.WriteLine("Found a parenthesis: " + par));
}

IEither、、Leftの実装は次のとおりRightです。これらは完全に汎用的であり、合計タイプが必要な場所であればどこでも使用できます。

public interface IEither<TLeft, TRight>
{
    TResult Map<TResult>(Func<TLeft, TResult> onLeft, Func<TRight, TResult> onRight);
    void Map(Action<TLeft> onLeft, Action<TRight> onRight);
}

public sealed class Left<TLeft, TRight> : IEither<TLeft, TRight>
{
    private readonly TLeft value;

    public Left(TLeft value)
    {
        this.value = value;
    }

    public TResult Map<TResult>(Func<TLeft, TResult> onLeft, Func<TRight, TResult> onRight)
    {
        return onLeft(value);
    }

    public void Map(Action<TLeft> onLeft, Action<TRight> onRight)
    {
        onLeft(value);
    }
}

public sealed class Right<TLeft, TRight> : IEither<TLeft, TRight>
{
    private readonly TRight value;

    public Right(TRight value)
    {
        this.value = value;
    }

    public TResult Map<TResult>(Func<TLeft, TResult> onLeft, Func<TRight, TResult> onRight)
    {
        return onRight(value);
    }

    public void Map(Action<TLeft> onLeft, Action<TRight> onRight)
    {
        onRight(value);
    }
}

参照：

于 2011-07-28T00:13:05.337 に答える
1

たぶん、それぞれに小さなホルダータイプを定義できます。1つはExpressionプロパティとOperatorプロパティを持ち、もう1つはOperatorプロパティとParenthesisプロパティを持ちます。アクセサーとコンストラクターは、1つだけが設定されるようにアサートまたはその他の方法で保証できます。キューとスタックには、それぞれ適切なホルダータイプが含まれます。

少し厄介ですが、タイプセーフで実行可能です。

うまくいけば、誰かがもっと賢い考えを持っているでしょう。

于 2011-07-27T23:01:37.087 に答える