Such-String parsen mit Klammern

[ben_]

Hallo,

ich möchte gerne für ein kleines Projekt eine "Minisuchmaschine" bauen. Dazu soll der User eine Suche im folgenden Stil eingeben können:

(wert1 AND wert2) NOT wert 3

Und ähnliches....mit OR etc.

Kann mir einer von euch vielleicht einen Tipp geben, wie ich den Eingabe-String so parsen kann, dass die Klammerung und die gewählten Operatoren berücksichtigt werden? Gibt es hier vielleicht eine Lib oder ähnliches wo man aufsetzen kann? Ich habe leider nichts konkretes finden können.


Besten Dank für eure Ideen.

Gruß,
Ben

 

[DrZoidberg]

Ich hab hier einen Parser für mathematische Ausdrücke. Den müsste man nur ein wenig anpassen.

import java.util.HashMap;
import java.util.Map;
import java.util.Collection;
import java.util.ArrayList;
import java.util.ArrayDeque;
import java.util.regex.Pattern;
import java.util.regex.Matcher;

public class Eval {    
    static int getPriority(String op) {
        switch(op) {
            case "+": case "-": return 1;
            case "*": case "/": return 2;
            case "(": return 0;
            default: return 3;
        }
    }
    
    static Collection<Object> tokenize(String str) {
        str = str.toLowerCase();
        ArrayList<Object> tokens = new ArrayList<>();
        Matcher m = Pattern.compile("[0-9.]+|[a-z]+|\\S").matcher(str);
        while(m.find()) {
            String s = m.group();
            try {
                tokens.add(Double.valueOf(s));
            } catch(NumberFormatException e) {
                tokens.add(s);
            }
        }
        return tokens;
    }
    
    static Collection<Object> toPostfix(Collection<Object> infix) {
        ArrayDeque<String> stack = new ArrayDeque<>();
        ArrayList<Object> postfix = new ArrayList<>();
        for(Object o: infix) {
            if(o instanceof Double) postfix.add(o);
            else {
                String str = (String)o;
                if(str.equals("(")) stack.push(str);
                else if(str.equals(")")) {
                    while(!stack.peek().equals("(")) postfix.add(stack.pop());
                    stack.pop();
                } else {
                    int pri = getPriority(str);
                    while(!stack.isEmpty() && getPriority(stack.peek()) >= pri) postfix.add(stack.pop());
                    stack.push(str);
                }
            }
        }
        while(!stack.isEmpty()) postfix.add(stack.pop());
        return postfix;
    }
    
    static Collection<Object> insertVars(Collection<Object> expr, Map<String, Double> vars) {
        ArrayList<Object> result = new ArrayList<>();
        for(Object o: expr) {
            if(o instanceof String && vars.containsKey((String)o)) {
                result.add(vars.get((String)o));
            } else {
                result.add(o);
            }
        }
        return result;
    }
    
    static double eval(Collection<Object> postfix) {
        ArrayDeque<Double> stack = new ArrayDeque<>();
        for(Object o: postfix) {
            if(o instanceof Double) stack.push((Double)o);
            else {
                switch((String)o) {
                    case "+": stack.push(stack.pop() + stack.pop()); break;
                    case "-": stack.push(-stack.pop() + stack.pop()); break;
                    case "*": stack.push(stack.pop() * stack.pop()); break;
                    case "/": stack.push(1/stack.pop() * stack.pop()); break;
                }
            }
        }
        return stack.pop();
    }
    
    public static void main(String[] args) throws Exception {
        String expr = "3*x*(x + 2)*x + x";
        Map<String, Double> vars = new HashMap<>();
        vars.put("x", 3.0);
        
        System.out.println("expr = " + expr);
        
        Collection<Object> infix = tokenize(expr);
        System.out.println("infix = " + infix);
        
        infix = insertVars(infix, vars);
        System.out.println("infix = " + infix);
        
        Collection<Object> postfix = toPostfix(infix);
        System.out.println("postfix = " + postfix);
        
        System.out.println(eval(postfix));
    }
}

 

[Barista]

Ich habe da mal was gemacht

Expression Parser Heiner Kücker

Ansonsten ist in Java seit der Version 6 immer JavaScript mit dabei.

Entsprechende Beispiele solltest Du mit den üblichen Suchmaschinen finden.

Bei meiner Expression-Engine und bei JavaScript wird immer ein korrekter Ausdruck mit
korrekt geschriebenen(encodeten) Strings erwartet.

Das müsstest Du aus der ursprünglichen Such-Anfrage ableiten.

Eine alternative Lösung wäre ein Parser auf Basis einer Grammatik oder selbstgeschrieben nach dem Prinzip rekursiver Abstieg.