次のステップを容易にするために省略し、オプションの括弧を追加することにより、
- スタート（中あなたのケース
not、and、or）、対応する演算子ノードを作成します。
- バイナリ演算子は、前と次のノードを子として取得します。単項演算子は、次のものだけを取得します。
だから、あなたの例￢((A ∧ B) ∨ C ∨ D)のために、アルゴリズムは次のように行くだろう：
￢((A ∧ B) ∨ C ∨ D)は￢(((A ∧ B) ∨ C) ∨ D)
- なり
NOTノードを作成し、それはのように、次の開く括弧の結果を得るでしょう子供。
ALEAFノード、ANDノード、BLEAFノードを作成します。 ANDの子は、AとBです。ORノードを作成すると、以前に作成されたノードはANDで、新しいノードはLEAFで、Cです。ORノードを作成すると、以前に作成されたノードはOR、新しいノードはDになります。その時点で
は、あなたのツリーは次のようになります。
NOT
|
OR
/\
OR D
/\
AND C
/\
A B
あなたは再帰的（多型がここで使用することができる）、そのタイプに基づいて評価しNode.Evaluate（）メソッドを追加することができます。たとえば、次のようになります。
class LeafEx {
bool Evaluate() {
return Boolean.Parse(this.Lit);
}
}
class NotEx {
bool Evaluate() {
return !Left.Evaluate();
}
}
class OrEx {
bool Evaluate() {
return Left.Evaluate() || Right.Evaluate();
}
}
などとなります。あなたの式の結果を取得するには、のみ
bool result = Root.Evaluate();
よしを呼び出す必要があり、それは割り当てないと、それは実際に実装するのも楽しいものだから、私は先に行ってきました。私がここに投稿するコードの一部は、私が以前に説明したもの（および一部が欠落しているもの）に関連していませんが、参考のために私の答えに一番上の部分を残しています（そこには何も間違っていません！
これは最適ではなく、提供されたBoolExprクラスを変更しないように努力しています。これを変更すると、コードの量を減らすことができます。エラーチェックも全くありません。
は、ここでの主な方法
static void Main(string[] args)
{
//We'll use ! for not, & for and, | for or and remove whitespace
string expr = @"!((A&B)|C|D)";
List<Token> tokens = new List<Token>();
StringReader reader = new StringReader(expr);
//Tokenize the expression
Token t = null;
do
{
t = new Token(reader);
tokens.Add(t);
} while (t.type != Token.TokenType.EXPR_END);
//Use a minimal version of the Shunting Yard algorithm to transform the token list to polish notation
List<Token> polishNotation = TransformToPolishNotation(tokens);
var enumerator = polishNotation.GetEnumerator();
enumerator.MoveNext();
BoolExpr root = Make(ref enumerator);
//Request boolean values for all literal operands
foreach (Token tok in polishNotation.Where(token => token.type == Token.TokenType.LITERAL))
{
Console.Write("Enter boolean value for {0}: ", tok.value);
string line = Console.ReadLine();
booleanValues[tok.value] = Boolean.Parse(line);
Console.WriteLine();
}
//Eval the expression tree
Console.WriteLine("Eval: {0}", Eval(root));
Console.ReadLine();
}
トークン化相は式のすべてのトークンのトークンオブジェクトを作成します。これは、解析を実際のアルゴリズムと分離しておくのに役立ちます。ここでは、これを実行し、トークンクラスがあります：その時点で
class Token
{
static Dictionary<char, KeyValuePair<TokenType, string>> dict = new Dictionary<char, KeyValuePair<TokenType, string>>()
{
{
'(', new KeyValuePair<TokenType, string>(TokenType.OPEN_PAREN, "(")
},
{
')', new KeyValuePair<TokenType, string>(TokenType.CLOSE_PAREN, ")")
},
{
'!', new KeyValuePair<TokenType, string>(TokenType.UNARY_OP, "NOT")
},
{
'&', new KeyValuePair<TokenType, string>(TokenType.BINARY_OP, "AND")
},
{
'|', new KeyValuePair<TokenType, string>(TokenType.BINARY_OP, "OR")
}
};
public enum TokenType
{
OPEN_PAREN,
CLOSE_PAREN,
UNARY_OP,
BINARY_OP,
LITERAL,
EXPR_END
}
public TokenType type;
public string value;
public Token(StringReader s)
{
int c = s.Read();
if (c == -1)
{
type = TokenType.EXPR_END;
value = "";
return;
}
char ch = (char)c;
if (dict.ContainsKey(ch))
{
type = dict[ch].Key;
value = dict[ch].Value;
}
else
{
string str = "";
str += ch;
while (s.Peek() != -1 && !dict.ContainsKey((char)s.Peek()))
{
str += (char)s.Read();
}
type = TokenType.LITERAL;
value = str;
}
}
}
、mainメソッドでは、あなたは私がPolish Notationために、トークンのリストを変換見ることができます。これは、ツリーの作成がはるかに簡単になり、私は、このためにShunting Yard Algorithmの変更実装を使用します。この変換後
static List<Token> TransformToPolishNotation(List<Token> infixTokenList)
{
Queue<Token> outputQueue = new Queue<Token>();
Stack<Token> stack = new Stack<Token>();
int index = 0;
while (infixTokenList.Count > index)
{
Token t = infixTokenList[index];
switch (t.type)
{
case Token.TokenType.LITERAL:
outputQueue.Enqueue(t);
break;
case Token.TokenType.BINARY_OP:
case Token.TokenType.UNARY_OP:
case Token.TokenType.OPEN_PAREN:
stack.Push(t);
break;
case Token.TokenType.CLOSE_PAREN:
while (stack.Peek().type != Token.TokenType.OPEN_PAREN)
{
outputQueue.Enqueue(stack.Pop());
}
stack.Pop();
if (stack.Count > 0 && stack.Peek().type == Token.TokenType.UNARY_OP)
{
outputQueue.Enqueue(stack.Pop());
}
break;
default:
break;
}
++index;
}
while (stack.Count > 0)
{
outputQueue.Enqueue(stack.Pop());
}
return outputQueue.Reverse().ToList();
}
、私たちのトークンリストがNOT, OR, OR, C, D, AND, A, Bになります。
ここで、式ツリーを作成する準備が整いました。
static BoolExpr Make(ref List<Token>.Enumerator polishNotationTokensEnumerator)
{
if (polishNotationTokensEnumerator.Current.type == Token.TokenType.LITERAL)
{
BoolExpr lit = BoolExpr.CreateBoolVar(polishNotationTokensEnumerator.Current.value);
polishNotationTokensEnumerator.MoveNext();
return lit;
}
else
{
if (polishNotationTokensEnumerator.Current.value == "NOT")
{
polishNotationTokensEnumerator.MoveNext();
BoolExpr operand = Make(ref polishNotationTokensEnumerator);
return BoolExpr.CreateNot(operand);
}
else if (polishNotationTokensEnumerator.Current.value == "AND")
{
polishNotationTokensEnumerator.MoveNext();
BoolExpr left = Make(ref polishNotationTokensEnumerator);
BoolExpr right = Make(ref polishNotationTokensEnumerator);
return BoolExpr.CreateAnd(left, right);
}
else if (polishNotationTokensEnumerator.Current.value == "OR")
{
polishNotationTokensEnumerator.MoveNext();
BoolExpr left = Make(ref polishNotationTokensEnumerator);
BoolExpr right = Make(ref polishNotationTokensEnumerator);
return BoolExpr.CreateOr(left, right);
}
}
return null;
}
は、今、私たちは黄金だ：私たちが行くようにポーランド記法の性質は、（私たちはあなたのBoolExprクラスを使用します）私たちはちょうどトークンリストを歩くと、再帰的にツリーノードを作成することができます！式を表す式ツリーがありますので、各リテラルオペランドの実際のブール値をユーザーに問い合わせ、ルートノードを評価します（必要に応じてツリーの残りの部分を再帰的に評価します）。
My Eval関数が続きます。BoolExprクラスを変更した場合、このクリーナーを作成するために多形性を使用します。予想通り
static bool Eval(BoolExpr expr)
{
if (expr.IsLeaf())
{
return booleanValues[expr.Lit];
}
if (expr.Op == BoolExpr.BOP.NOT)
{
return !Eval(expr.Left);
}
if (expr.Op == BoolExpr.BOP.OR)
{
return Eval(expr.Left) || Eval(expr.Right);
}
if (expr.Op == BoolExpr.BOP.AND)
{
return Eval(expr.Left) && Eval(expr.Right);
}
throw new ArgumentException();
}
は、値A, B, C, Dためfalse, true, false, trueで私たちのテスト式￢((A ∧ B) ∨ C ∨ D)を供給することは、それぞれの結果falseが得られます。
これがうまくいくかどうかわかりませんが、私は[Shunting Yard algorithm]（http://en.wikipedia.org/wiki/Shunting-yard_algorithm）を使ってポーランド語表記法に変換しようとしていますが、これは簡単に構文解析することができます – GolfWolf
[逆ポーランド記法]（http://ja.wikipedia.org/wiki/Reverse_Polish_notation）を試してみてください。インターネット上のC＃にはすでに実装とその例がたくさんあります。 –
私の場合は、この機会を利用してF＃、特に差別化された組合を手に入れよう：http://msdn.microsoft.com/en-us/library/dd233226.aspx – Tormod