Expression-Tree, C#

Language: Layout:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;

namespace Rextester
{
	public class Program
	{
		public static List<int> Rules = new List<int> { 103 , 106 };

public static void Main( string[] args )
		{
			var ruleStr = CleanupRuleString( "{100} AND (({101} OR {102}) OR ({103} AND {104})) AND NOT ({105} OR {106})" );
			var inputRules = new List<int> { 103 , 106 };
			var tree = GetTree( ruleStr );
			var resTrue = Evaluate( tree , new List<int> { 100 , 101 } );
            var resFalse = Evaluate( tree , new List<int> { 100 , 103 } );

Console.WriteLine( "resTrue: {0}" , resTrue );
            Console.WriteLine( "resFalse: {0}" , resFalse );
		}

public class Expression
		{
			public TokenTypes TokenType = TokenTypes.None;
			public List<Expression> SubExpressions = new List<Expression>();
			public string Literal = null;
		}

public static Expression GetTree( string ruleStr )
		{
			var tokens = new List<Token>();
			var reader = new StringReader( ruleStr );

for( var token = new Token( reader ) ; token.TokenType != TokenTypes.None ; token = new Token( reader ) )
			{
				tokens.Add( token );
			}

tokens = TransformToPolishNotation( tokens );

var enumerator = tokens.GetEnumerator();

enumerator.MoveNext();

return CreateExpressionTree( ref enumerator );
		}

public static string CleanupRuleString( string ruleStr )
		{
			foreach( var translation in TranslationMap )
			{
				var query = SyntaxMap.Where( x => x.Key == translation.Value ).Select( x => x.Key );

if( query.Any() )
					ruleStr = ruleStr.Replace( translation.Key , query.Single().ToString() );
			}

return new string( ruleStr.ToCharArray().Where( c => !char.IsWhiteSpace( c ) && c != '{' && c != '}' ).ToArray() );
		}

public static bool Evaluate( Expression expr , List<int> rules )
		{
			if( expr.TokenType == TokenTypes.None )
			{
				return rules.Contains( Convert.ToInt32( expr.Literal ) );
			}
			else if( expr.TokenType == TokenTypes.Not )
			{
				return !Evaluate( expr.SubExpressions.Single() , rules );
			}
			else // binary op
			{
				if( expr.TokenType == TokenTypes.Or )
					return Evaluate( expr.SubExpressions[ 0 ] , rules ) || Evaluate( expr.SubExpressions[ 1 ] , rules );
				else if( expr.TokenType == TokenTypes.And )
					return Evaluate( expr.SubExpressions[ 0 ] , rules ) && Evaluate( expr.SubExpressions[ 1 ] , rules );
			}

throw new ArgumentException();
		}

public static List<Token> TransformToPolishNotation( List<Token> infixTokenList )
		{
			var outputQueue = new Queue<Token>();
			var stack = new Stack<Token>();

foreach( var token in infixTokenList )
			{
				switch( token.TokenType )
				{
					case TokenTypes.Literal:
					{
						outputQueue.Enqueue( token );
					}
					break;

case TokenTypes.Not:
					case TokenTypes.And:
					case TokenTypes.Or:
					case TokenTypes.OpenParen:
					{
						stack.Push( token );
					}
					break;

case TokenTypes.CloseParen:
					{
						while( stack.Peek().TokenType != TokenTypes.OpenParen )
						{
							outputQueue.Enqueue( stack.Pop() );
						}

stack.Pop();

if( stack.Count > 0 && stack.Peek().TokenType == TokenTypes.Not )
							outputQueue.Enqueue( stack.Pop() );
					}
					break;

default:
					break;
				}
			}

while( stack.Count > 0 )
			{
				outputQueue.Enqueue( stack.Pop() );
			}

return outputQueue.Reverse().ToList();
		}

public static Expression CreateExpressionTree( ref List<Token>.Enumerator tokenEnumerator )
		{
			var expression = new Expression();

if( tokenEnumerator.Current.TokenType == TokenTypes.Literal )
			{
				expression.Literal = tokenEnumerator.Current.Value;

tokenEnumerator.MoveNext();

return expression;
			}
			else if( tokenEnumerator.Current.TokenType != TokenTypes.None )
			{
				expression.TokenType = tokenEnumerator.Current.TokenType;

tokenEnumerator.MoveNext();

if( expression.TokenType == TokenTypes.Not )
				{
					expression.SubExpressions.Add( CreateExpressionTree( ref tokenEnumerator ) );
				}
				else if( expression.TokenType == TokenTypes.And || expression.TokenType == TokenTypes.Or )
				{
					expression.SubExpressions.Add( CreateExpressionTree( ref tokenEnumerator ) );
					expression.SubExpressions.Add( CreateExpressionTree( ref tokenEnumerator ) );
				}
			}

return expression;
		}

public static Dictionary<string,char> TranslationMap = new Dictionary<string,char> {
				{ "NOT" , '!' } ,
				{ "AND" , '&' } ,
				{ "OR" , '|' } ,
			};

public static Dictionary<char,TokenTypes> SyntaxMap = new Dictionary<char,TokenTypes>() {
				{ '(' , TokenTypes.OpenParen } ,
				{ ')' , TokenTypes.CloseParen } ,
				{ '!' , TokenTypes.Not } ,
				{ '&' , TokenTypes.And } ,
				{ '|' , TokenTypes.Or } ,
			};

public enum TokenTypes
		{
			None = -1,
			OpenParen,
			CloseParen,
			And,
			Or,
			Not,
			Literal,
		}

public class Token
		{
			public TokenTypes TokenType;
			public string Value;

public Token( StringReader s )
			{
				var charValue = s.Read();

if( charValue == -1 )
				{
					this.TokenType = TokenTypes.None;
					this.Value = string.Empty;

return;
				}

var ch = (char)charValue;

if( SyntaxMap.ContainsKey( ch ) )
				{
					this.TokenType = SyntaxMap[ ch ];
					this.Value = string.Empty;
				}
				else // read literal
				{
					var sb = new StringBuilder();

sb.Append( ch );

while( s.Peek() != -1 && !SyntaxMap.ContainsKey( (char)s.Peek() ) )
					{
						sb.Append( (char)s.Read() );
					}

this.TokenType = TokenTypes.Literal;
					this.Value = sb.ToString();
				}
			}
		}
	}
}

Show compiler warnings [ + ] Show input
Compilation time: 0,19 sec, absolute running time: 0,17 sec, cpu time: 0,16 sec, average memory usage: 16 Mb, average nr of threads: 3