Come analizzare un'espressione booleana e caricarla in una classe?

Question

Ho il seguente BoolExpr classe:

class BoolExpr 
{ 
    public enum BOP { LEAF, AND, OR, NOT }; 

    // 
    // inner state 
    // 

    private BOP _op; 
    private BoolExpr _left; 
    private BoolExpr _right; 
    private String _lit; 

    // 
    // private constructor 
    // 

    private BoolExpr(BOP op, BoolExpr left, BoolExpr right) 
    { 
     _op = op; 
     _left = left; 
     _right = right; 
     _lit = null; 
    } 

    private BoolExpr(String literal) 
    { 
     _op = BOP.LEAF; 
     _left = null; 
     _right = null; 
     _lit = literal; 
    } 

    // 
    // accessor 
    // 

    public BOP Op 
    { 
     get { return _op; } 
     set { _op = value; } 
    } 

    public BoolExpr Left 
    { 
     get { return _left; } 
     set { _left = value; } 
    } 

    public BoolExpr Right 
    { 
     get { return _right; } 
     set { _right = value; } 
    } 

    public String Lit 
    { 
     get { return _lit; } 
     set { _lit = value; } 
    } 

    // 
    // public factory 
    // 

    public static BoolExpr CreateAnd(BoolExpr left, BoolExpr right) 
    { 
     return new BoolExpr(BOP.AND, left, right); 
    } 

    public static BoolExpr CreateNot(BoolExpr child) 
    { 
     return new BoolExpr(BOP.NOT, child, null); 
    } 

    public static BoolExpr CreateOr(BoolExpr left, BoolExpr right) 
    { 
     return new BoolExpr(BOP.OR, left, right); 
    } 

    public static BoolExpr CreateBoolVar(String str) 
    { 
     return new BoolExpr(str); 
    } 

    public BoolExpr(BoolExpr other) 
    { 
     // No share any object on purpose 
     _op = other._op; 
     _left = other._left == null ? null : new BoolExpr(other._left); 
     _right = other._right == null ? null : new BoolExpr(other._right); 
     _lit = new StringBuilder(other._lit).ToString(); 
    } 

    // 
    // state checker 
    // 

    Boolean IsLeaf() 
    { 
     return (_op == BOP.LEAF); 
    } 

    Boolean IsAtomic() 
    { 
     return (IsLeaf() || (_op == BOP.NOT && _left.IsLeaf())); 
    } 
} 

Cosa algoritmo dovrei usare per analizzare una stringa di espressione booleana di input come "￢((A ∧ B) ∨ C ∨ D)" e caricarlo nella classe di cui sopra?

Answer 1

TL; DR: Se si desidera visualizzare il codice, passare alla seconda parte della risposta.

Vorrei creare un albero dall'espressione per analizzare e quindi attraversare prima la profondità. È possibile fare riferimento allo wikipedia article about Binary Expression Trees per avere un'idea di ciò che sto suggerendo.

1. Inizia aggiungendo le parentesi opzionali omesso di fare il passo successivo più facile
2. Quando si legge tutto ciò che non è un operatore o un Parenthese, creare un nodo di tipo LEAF
3. Quando si leggono qualsiasi operatore (in il tuo caso not, and, or), crea il nodo operatore corrispondente
4. Gli operatori binari ottengono i nodi precedenti e seguenti come figli, gli operatori unari ottengono solo il successivo.

Quindi, per il tuo esempio ￢((A ∧ B) ∨ C ∨ D), l'algoritmo sarebbe andato come questo:

￢((A ∧ B) ∨ C ∨ D) diventa ￢(((A ∧ B) ∨ C) ∨ D)

1. creare un nodo NOT, otterrà il risultato delle seguenti parentesi di apertura come un bambino.
2. Creare ALEAF nodo, AND nodo e B nodo LEAF. AND ha A e B da bambini.
3. Creare il nodo OR, ha il AND creato in precedenza come un bambino e un nuovo nodo LEAF per C.
4. Creare il nodo OR, ha il OR creato in precedenza e un nuovo nodo per D come bambini.

A quel punto, il vostro albero assomiglia a questo:

NOT 
    | 
    OR 
    /\ 
OR D 
/\ 
AND C 
/\ 
A B 

È quindi possibile aggiungere un metodo Node.Evaluate() che valuta in modo ricorsivo in base al tipo (polimorfismo potrebbe essere usato qui). Ad esempio, potrebbe essere qualcosa del genere:

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

E così via e così via. Per ottenere il risultato della vostra espressione, è allora solo bisogno di chiamare

bool result = Root.Evaluate(); 

---

Va bene, dato che non è un incarico ed è in realtà una cosa divertente da realizzare, sono andato avanti. Parte del codice che pubblicherò qui non è correlato a ciò che ho descritto prima (e alcune parti sono mancanti), ma lascerò la parte superiore nella mia risposta come riferimento (nulla di ciò che c'è di sbagliato è sbagliato (si spera!)).

Tenere presente che questo è tutt'altro che ottimale e che mi sono sforzato di non modificare la classe BoolExpr fornita. La modifica potrebbe consentire di ridurre la quantità di codice. Non c'è nemmeno il controllo degli errori.

Ecco il metodo principale

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

La fase di tokenizzazione crea un oggetto token per tutti i segni di espressione. Aiuta a mantenere l'analisi separata dall'algoritmo attuale. Ecco la classe Token che esegue questa:

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

A quel punto, nel metodo principale, è possibile vedere trasformo l'elenco di token in Polish Notation ordine. Rende la creazione di un albero molto più facile e io uso un'implementazione modificata del Shunting Yard Algorithm per questo:

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

Dopo questa trasformazione, la nostra lista di token diventa NOT, OR, OR, C, D, AND, A, B.

A questo punto, siamo pronti per creare l'albero delle espressioni. Le proprietà del Polish Notation ci permettono di camminare solo la lista di token e ricorsivamente creiamo i nodi della struttura (useremo la classe BoolExpr) come andiamo:

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

Ora siamo d'oro! Abbiamo l'albero delle espressioni che rappresenta l'espressione, quindi chiederemo all'utente i valori booleani effettivi di ciascun operando letterale e valuteremo il nodo radice (che valuterà ricorsivamente il resto dell'albero come necessario).

La mia funzione Eval segue, tenete presente che utilizzerei del polimorfismo per rendere questo pulitore se ho modificato la vostra classe 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(); 
} 

Come previsto, alimentando un espressione di prova ￢((A ∧ B) ∨ C ∨ D) con valori false, true, false, true per A, B, C, D cede rispettivamente il risultato false.

Answer 2

Dal punto di vista dell'algoritmo, per analizzare un'espressione, è necessario uno stack.

Usiamo due passi algoritmo:

1. Lexing

Lo scopo di lexing è quello di ottenere 'parole chiave', 'identificatori' e 'separatori': - Una parola chiave è ' se '' then '' else '' ('') ''/\ ''/'etc ... - Un identificatore nel tuo caso è' A ',' B ',' C 'ecc ... - Un separatore è spazio vuoto, tabulazione, fine riga, fine del file, ecc ...

Lexing consiste nell'utilizzare un automa. In lexing leggerete la vostra stringa di input char per char. Quando si encouter un char che è compatibile con una parola chiave, identificatori, separatori, si avvia una sequenza di caratteri. Quando si encouter un separatore si interrompe la sequenza, cercare in una dizione della sequenza è una parola chiave (se non è un identificatore); quindi metti la tupla [sequenza, parola chiave o identificatore/classe] nello stack.

vi lascio come exercice caso della piccola parola chiave '(' che possono essere vedono anche come separatori.

1. parsing

di analisi è simile alla grammatica. Nel tuo caso la uniche regole da controllare sono virgola e operazioni binarie, e solo un semplice identificatore

formaly:.

expression:: 
    '(' expression ')' 
    expression /\ expression 
    expression \/ expression 
    identifier 

Questo può essere scritto da una funzione ricorsiva. Prima invertire il vostro stack, allora:

myParseExpression(stack, myC#ResultObject) 
{ 
    if(stack.top = kewyord.'(' ) 
     then myParseOpenComma(all stack but top, myC#ResultObject) 
    if(stack.top = keyword.'/\') 
     then myParseBinaryAnd(stack, myC#ResultObject) 
} 

myParseOpenComma(stack, myC#ResultObject) 
{ 
... 
} 

myParseBinaryAnd(stack, myC#ResultObject) 
{ 
myNewRigthPartOfExpr = new C#ResultObject 
myParseExpression(stack.top, myNewRigthPartOfExpr) 
remove top of stack; 
myNewLeftPartOfExpr = new C#ResultObject 
myParseExpression(stack.top, myNewLeftPartOfExpr) 

C#ResultObject.add("AND", myNewRigthPartOfExpr, myNewLeftPartOfExpr) 
} 

... 

C'è funzione multipla che condividono la ricorsione a vicenda. Come esercizio, prova ad aggiungere la negazione.

• Lexing è tradizionalmente fatto da un lexer (come lo strumento lex).
• L'analisi viene eseguita tradizionalmente da un parser (come lo strumento bisonte).
• Lo strumento consente di scrivere la funzione di thoses più come ho fatto nell'espressione formale.

Questo aspetto è fondamentale per la compilazione del programma. La codifica della cosa ti migliorerà molto perché è dura e fondamentale.