Как динамически оценивать логическую логику в строке в c # без использования выражений? [Дубликат]

TL; DR: Если вы хотите увидеть код, перейдите ко второй части ответа.

Я бы построил дерево из выражения для синтаксического анализа, а затем сначала переместил его по глубине. Вы можете обратиться к статье wikipedia о деревьях двоичных выражений , чтобы понять, что я предлагаю.

1. Начните с добавления опускаемых необязательных круглых скобок, чтобы сделать следующий
3. Когда вы читаете что-либо, что не является оператором или родительским, создайте узел типа LEAF
4. . Когда вы читаете какой-либо оператор (в вашем случае not, and , or), создайте соответствующий операторный узел
5. . Бинарные операторы получают предыдущий и следующие узлы в качестве дочерних, унарные операторы получают только следующий.

Итак, для вашего примера ￢((A ∧ B) ∨ C ∨ D), алгоритм будет выглядеть следующим образом:

￢((A ∧ B) ∨ C ∨ D) становится ￢(((A ∧ B) ∨ C) ∨ D)

1. Создайте узел NOT, он получит результат следующего открытия в качестве дочернего.
2. Создайте узел A LEAF, узел AND и B LEAF. AND имеет A и B как дети.
3. Создайте узел OR, у него есть ранее созданный AND как дочерний элемент и новый узел LEAF для C.
4. Создайте узел 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();
}

Фаза токенизации создает объект Token для всех токенов выражения. Это помогает разделить парсинг от реального алгоритма. Вот класс Token, который выполняет это:

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;
        }
    }
}

. В этот момент в основном методе вы можете увидеть, что я преобразую список токенов в польский 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.

На этом этапе мы готовы создать дерево выражений. Свойства польской нотации позволяют нам просто ходить по списку токенов и рекурсивно создавать узлы дерева (мы будем использовать ваш класс BoolExpr):

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;
}

Теперь мы золотые! У нас есть дерево выражений, которое представляет выражение, поэтому мы будем запрашивать у пользователя фактические логические значения каждого литерала и оценивать корневой узел (который будет рекурсивно оценивать остальную часть дерева по мере необходимости).

Моя функция 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.