[C#] Expressie evalueren

[Avalaxy]

Ik ben een stuk code aan het schrijven waarmee je zoekqueries in kunt voeren als:

code:

p2 | p1 & (foo | bar)

Je hebt een aantal dingen waar je op kunt zoeken:

- Prioriteit: p1 t/m p4
- Zoekterm: hier als voorbeeld foo en bar, maar kan alles zijn
- Datum: in het formaat yyyy-mm-dd

En dan zijn er een aantal operators:

- & returnt alleen de resultaten waarvan de condities aan beide kanten van de & voldaan worden
- | returnt de gecombineerd (doch unieke) resultaten waarvan de condities aan beide kanten van de | voldaan worden.
- ( en ) om precedence aan te geven net als bij normale wiskunde

In het bovenstaande voorbeeld wordt dus alles gereturnd met prioriteit 2 en alles met prioriteit 1 waarvan de tekst 'foo' of 'bar' bevat.

Ik zit nog een beetje te puzzelen wat de beste manier is om dergelijke expressies te evalueren (in C#), maar ik ben er nog niet over uit. Zijn er bepaalde algoritmen voor om dit aan te pakken?

[ Voor 7% gewijzigd door Avalaxy op 10-01-2016 20:48 ]

[Daos]

Stap 1: parse de string en bouw een 'expression tree' bestaande uit And, Or en Literal objecten. Jij hebt een grammar met 'operator precedence' en moet zelf maar even zoeken hoe je daar een parser voor maakt (je kan ook haakjes verplichten of reverse polish notation gebruiken om het parsen te versimpelen).

Stap 2: evalueer de expression tree. Bij een Literal return je de dataset die aan die zoekterm voldoet. Bij Or pak je de Union en bij And de Intersection van de 2 subtrees.

[Avalaxy]

Hmm, heb je een voorbeeldje voor het opbouwen van de expression tree? Met de uitleg van MSDN over ExpressionTree kome ik niet echt verder: MSDN: Expression Trees (C# and Visual Basic).

[butsubutsu]

Hoi Avalanxy, je zou de Shunting yard algoritme kunnen gebruiken om een mathematische uitdrukking
in infixnotatie (zoals p2 | p1 & (foo | bar) ) te verwerken.

Hieronder vind je een link naar Wikipedia met een uitleg van de algoritme.
Wikipedia: Shunting-yardalgoritme

Hier kan je een voorbeeld van hoe je een dynamische query met behulp van syntax trees kan bouwen:
MSDN: How to: Use Expression Trees to Build Dynamic Queries (C# and Visual Basic)
Een extra voordeel van dit voorbeeld is dat je een IQueryable query als output krijgt die direct naar de databron zal worden gestuurd en daar werverkt.

Wat het vertalen van een RPN uitdrukking in een AST (abstract syntax tree ) kan je een iteratieve algoritme gebruiken die
"terminal symbols" (dwz alles wat geen operator is) van je RPN leest en die met elkaar combineert met behulp van de eerste gevonden operator.
(bjvb: RPN:'a b +' wordt AST Expression.Add(Expression.Constant(a),expression.Constant(b)))
Je gaat op deze manier door totdat je RPN leeg is.

Ik hoop dat je een beetje heb kunnen helpen.

[Avalaxy]

Dankjewel, ik was zelf al bij shunting-yard uitgekomen maar omdat ik niet bekend was met reverse polish nam ik aan dat het niet deed wat ik nodig heb. Ik ga er nog eens goed naar kijken morgen en hopelijk iets moois bakken

[Daos]

Ik weet zo niet of je genoeg hebt aan de standaard klassen uit het framework. Waarschijnlijk moet je je eigen klassen maken voor je expressies.

Parsen van RPN en daarvan een boom bouwen is vrij simpel:

code:

maak een lege stack voor Expressions

splits de input-string op spaties zodat je tokens krijgt
loop door de tokens
  constant/literal -> push new Literal() op de stack
  or -> pop 2 expr van de stack en push new Or(a,b) 
  and -> lijkt op or

root = stack.Pop();

[Creepy]

Vergeet niet dat er parser generator zijn die je ook zouden kunnen helpen. Zie bijv http://sourceforge.net/projects/csflex/ en http://www.antlr.org/ .

[Avalaxy]

Ja, ik had ANTLR al gevonden maar volgens mij heb ik eerst een boek nodig om uit te vinden hoe het allemaal werkt, dit is meer iets wat ik binnen 5~10 uur moet bouwen.

[Woy]

Ik zou eerst de string omzetten naar een token stream (Gewoon lineair door de string heenlopen en d.m.v. een simpele state-machine tokens genereren). Die token stream is daarna vrij eenvoudig om te zetten naar een AST ( Bijvoorbeeld met het shunting-yard algoritme ).

[ Voor 4% gewijzigd door Woy op 11-01-2016 12:56 ]

[Feanathiel]

Ik kwam laatst Sprache (tutorial) tegen. Aangezien daar ook een rekenmachine in zit, zit het volgens mij ook wel goed met de precedence. Syntax ziet er makkelijk uit, dus wellicht een bezoekje waard. In ieder geval voor het parse-gedeelte.

Edit: ik had even niks te doen, en vond het zelf ook wel interessant om een keer uit te zoeken. Kun je wellicht als referentie gebruiken: https://gist.github.com/Feanathiel/727bd659d7d4d7999576

[ Voor 41% gewijzigd door Feanathiel op 17-01-2016 10:59 ]

[Avalaxy]

butsubutsu schreef op maandag 11 januari 2016 @ 00:53:

Ik heb nu dit gemaakt:

Input:

code:

p1 | (p2 & (foo | bar | test string))

Code:

C#:

public class ItemFilter
{
    private const string And = "&";
    private const string Or = "|";
    private const string LeftBracket = "(";
    private const string RightBracket = ")"; 

    private readonly List<string> _precedence = new List<string> { And, Or }; 

    public Section FilterItems(IEnumerable<Item> items, string query)
    {
        var results = new Section();

        var operatorStack = new Stack<string>();
        var outputQueue = new Queue<string>();

        string[] tokens = TokenizeQuery(query);
        foreach (string token in tokens)
        {
            if (_precedence.Contains(token))
            {
                while (operatorStack.Any()
                    && (!HasHigherPrecedenceThanOtherOperator(token, operatorStack.Peek()) 
                    || token.Equals(operatorStack.Peek())))
                {
                    outputQueue.Enqueue(operatorStack.Pop());
                }
                operatorStack.Push(token);
            } 
            else if (token.Equals(LeftBracket)) operatorStack.Push(token);
            else if (token.Equals(RightBracket))
            {
                while (operatorStack.Any())
                {
                    var @operator = operatorStack.Pop();
                    if (@operator != LeftBracket) outputQueue.Enqueue(@operator);
                    else break;
                }
            }
            else outputQueue.Enqueue(token);
        }
        foreach (string @operator in operatorStack)
        {
            outputQueue.Enqueue(@operator);
        }

        while (outputQueue.Any())
        {
            string token = outputQueue.Dequeue();

            //expression tree opbouwen
        }

        return results;
    }

    private string[] TokenizeQuery(string query)
    {
        string[] rawTokens = Regex.Split(query, @"(&|\||\(|\))");

        string[] cleanedTokens = (
            from rawToken in rawTokens
            where !string.IsNullOrWhiteSpace(rawToken)
            select rawToken.Trim()
            ).ToArray();

        return cleanedTokens;
    }

    private bool HasHigherPrecedenceThanOtherOperator(string @operator, string otherOperator)
    {
        foreach (string operatorPrecedence in _precedence)
        {
            if (operatorPrecedence == @operator) return true;
            if (operatorPrecedence == otherOperator) return false;
        }

        throw new Exception($"Operator {@operator} not supported.");
    }

    private bool IsPriority(string token)
    {
        return Regex.IsMatch(token, @"^p[1-4]$", RegexOptions.Compiled);
    }

    private bool IsDate(string token)
    {
        return Regex.IsMatch(token, @"^\d{4]-\d{1,2}-\d{1,2}", RegexOptions.Compiled);
    }
}

Output van de queue:

code:

p1
p2
foo
bar
|
test string
|
&
|

Ik weet niet of de output goed is (zal wel niet), maar waar ik nu niet goed uitkom: hoe lees ik deze queue uit om er de expression tree van te maken? Stel ik dequeue #1 (p1) en dan dequeue #2 (p2), hoe weet ik dan welke operator ik daar op toe moet passen? Verder weet ik nog niet hoe ik de expressions kan chainen voor als ik veel geneste dingen heb of bv. meerdere ORs achter elkaar, maar daar kom ik wel uit met Google denk ik.

En mocht iemand tijd over hebben, is mijn code enigszins correct?

[Daos]

Je hebt nu reverse polish notation. Ergens hierboven heb ik al beschreven hoe je met een stack daarvan een boom bouwt (tokens heb je al, dus dat splitsen van de input is niet nodig)

[Camulos]

Toevallig laatst een stuk over gelezen, over het evalueren van een rekensom zoals

code:

( ( 1 + sqrt ( 5 ) ) / 2.0 )

Met het Shunting Yard algoritme (dual stacks) is dit makkelijk te evalueren.
Neem een kijkje op een java voorbeeld uit het boek

Volgens mij kun je dit eenvoudig omzetten naar een expressie zoals jij die voor ogen hebt

[ Voor 12% gewijzigd door Camulos op 13-01-2016 12:58 ]

[Daos]

Bij jouw voorbeeld zijn de haakjes (en zelfs de spaties) verplicht. Ik had dit al geopperd om het parsen te versimpelen.

Avalaxy heeft nu al een goed werkend algoritme met optionele haakjes.

Verder ben ik er persoonlijk voorstander van het parsen en evalueren gescheiden te houden. In jouw voorbeeld wordt de expressie direct tijdens het parsen geëvalueerd.

[Avalaxy]

Sorry, ik kom er echt niet uit hoe ik het nu naar een Expression omzet Ik ben niet zo slim als dat ik lijk. Zou iemand me een voorzetje willen geven?

[Daos]

Het is echt alleen een stack met dat simpele loopje dat ik al gegeven had.

Voorbeeld:
Push Lit(p1)
Push Lit(p2)
Push Lit(Foo)
Push Lit(Bar)
Pop b en Pop a, Push Or(a, b)
...

Op het eind staat er 1 Or op je stack en dat is de root van je tree/boom.

Naast dit algoritme heb je 3 klassen nodig die overerven van een abstracte Expression. De Or en And hebben 2 velden van het type Expression. Dit zijn de subtrees/deelbomen die er onder hangen