Блог

Учитывая произвольное количество входных данных текстового поля (t1, t2, t3, …) и пользовательскую логическую строку, введенную из области JTextArea, мне нужно проверить, соответствуют ли строки в файле пользовательскому логическому выражению. Он должен поддерживать вложенные скобки.

Пример:

Пользователь вводит «str1» в t1 , «str2» в t2, «str3» в t3, «str4» в t4, «str5» в t5.

Пользователь вводит следующее в область JTextArea для пользовательского логического значения:

«не ((t1 и не t3) или (t4 и t2)) или t5»

Затем на основе этих входных данных я должен отфильтровать файл и возвращать строки в файле, соответствующие пользовательскому логическому значению, на основе отношения «содержит» (например, «t1, а не t3» означает, что строка должна содержать строку t1, а не строку t3).

Например, файл со следующими двумя строками:

ул. 5

str4 str2

Фильтр вернет только str5, потому что это единственная строка, которая соответствует пользовательскому логическому значению.

У меня возникли проблемы даже с началом работы. Я пытался придумать рекурсивное решение, но ничего не смог придумать. Также я пробовал нерекурсивные решения, но тоже ничего не могу придумать.

Существует также проблема с логическим значением конечного результата, требующим ввода параметра (каждой строки в файле). Я подумал о том, чтобы, возможно, создать последовательность операций для выполнения, а не логическое значение, которое каким-то образом принимает параметр. Но я не могу понять, как получить эту последовательность в первую очередь.

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

 public class CustomInputParser {
private ArrayList<String> pairs;
private String inp;
private HashMap<Integer,String> atomMap;

public CustomInputParser() {
    this.pairs = null;
    this.inp = "";
    this.atomMap = new HashMap<Integer,String>();
}

public void findAtoms() {
    int i = 0;
    for(String s : this.pairs) {
        String[] indices = s.split(",");
        int begin = Integer.valueOf(indices[0]);
        int end = Integer.valueOf(indices[1]);
        if(!inp.substring(begin 1, end).contains("(")) {

            this.pairs.set(i, this.pairs.get(i)   ",@");
        }
        i  ;
    }
    
}

public void computeAtoms() {
    int i = 0;
    for(String s : this.pairs) {
        if(s.contains(",@")) {
            String[] indices = s.split(",");
            int begin = Integer.valueOf(indices[0]);
            int end = Integer.valueOf(indices[1]);
                //this.pairs.set(i,this.pairs.get(i).replace(",a", ""));
                this.pairs.set(i, this.pairs.get(i)   "," inp.substring(begin 1, end));
                this.atomMap.put(begin,this.pairs.get(i).split(",")[3] "#" String.valueOf(end));
            
        }
        i  ;
    }
    System.out.println(this.pairs.toString());
    System.out.println(this.atomMap.toString());
}

public void replaceAtoms() {
    int i = 0;
    for(String s : this.pairs) {
        if(!(s.contains("o") || s.contains("a") || s.contains("n"))) {
            String[] indices = s.split(",");
            int begin = Integer.valueOf(indices[0]) 1;
            int end = Integer.valueOf(indices[1]);
            for(int j = begin; j < end; j  ) {
                if(inp.charAt(j) == '(') {
                    if(atomMap.containsKey(j)) {
                        this.pairs.set(i, this.pairs.get(i)   "," j "#" atomMap.get(j).split("#")[1] ">" atomMap.get(j).split("#")[0]);
                    }
                    else {
                        this.pairs.set(i,"!"  this.pairs.get(i));
                    }
                }
            }
            
            
        }
        i  ;
    }
    System.out.println(this.pairs.toString());
}
public ArrayList<String> getPairs(String str){
    this.inp = str;
    ArrayList<String> res = new ArrayList<String>();
    char[] arr = str.toCharArray();
    Stack<Integer> s = new Stack<Integer>();
    for(int i = 0; i < arr.length; i  ) {
        if(arr[i] == '(') {
            
            s.push(i);
        }
        if(arr[i] == ')') {
            if(s.empty()) {
                return null;
            }
            else {
                Integer start  = s.pop();
                Integer end = Integer.valueOf(i);
                res.add(start.toString()   ","   end.toString());
                
                
            }
        }
        
    }
    
    if(!s.empty()) {
        return null;
    }
    this.pairs = res;
    return res;
    
}


public static void main(String[] args) {
    String x = "((not t1 and ((not t2 or t4) or (t3 or t4))) or (t5 and not t6)) and t7";
    x = x.replace("not", "n").replace("and","a").replace("or", "o").replace("t", "").replace(" ", "");
    System.out.println(x);
    CustomInputParser c = new CustomInputParser();
    System.out.println(c.getPairs(x).toString());
    c.findAtoms();
    c.computeAtoms();
    c.replaceAtoms();
    
}
 

}

Первым шагом является маркировка входных данных. Определять

 enum Token {VAR, LP, RP, NOT, AND, OR, END}
 

LP и RP являются круглыми скобками. Теперь определите класс токенизатора, который выглядит примерно так:

 class Tokenizer {
  Tokenizer(String input) {...}
  void reset() {...}
  Token getNext() {...}
  String getVarName() {...}
}
 

Вызов getNext() вашего примера в цикле должен возвращать

 LP LP NOT VAR AND LP LP NOT VAR OR VAR RP OR LP VAR OR VAR RP RP RP OR LP VAR AND NOT VAR RP RP AND VAR END
 

Вызов getVarName() сразу после того, как a VAR был возвращен, getNext() дает вам имя переменной (например "t42" ).

Существует множество способов реализации подобных маленьких сканеров. Вы должны сделать это в первую очередь и убедиться, что он пуленепробиваемый, протестировав его. Попытка построить синтаксический анализатор поверх облупленного сканера-пытка.

Как я уже говорил в комментариях, я бы рассмотрел рекурсивный анализ спуска. Если у вас есть подходящая грамматика, написание синтаксического анализатора RD-это очень короткий шаг, как показано в книге Dragon (также упомянутой выше).

Разумная грамматика (с использованием токенов, как указано выше) — это

 Expr -> Term AND Term
     | Term OR Term 
     | Term END

Term -> NOT Term 
     | Opnd

Opnd -> VAR 
     | LP Expr RP
 

Например, вот как бы вы начали. На нем показано первое правило, преобразованное в функцию:

 class Evaluator {
  final Tokenizer tokenizer = ...;     // Contains the expression text.
  final Map<String, Boolean> env = ... // Environment: variables to values.

  Token lookAhead;  // Holds the token we're parsing right now.

  Evaluator(Tokenizer tokenizer, Map<String, Boolean> env) { ... }

  void advance() {
    lookAhead = tokenizer.getNext();
  }

  boolean expr() {
    boolean leftHandSide = term();  // Parse the left hand side recursively.
    Token op = lookAhead;           // Remember the operator.
    if (op == Token.END) return leftHandSide; // Oops. That's all.
    advance();                      // Skip past the operator.
    boolean rightHandSide = term(); // Parse the right hand side recursively.
    if (op == Token.AND) return leftHandSide amp;amp; rightHandSide;  // Evaluate!
    if (op == Token.OR) return leftHandSide || rightHandSide;
    dieWithSyntaxError("Expected op, found "   op);
  }

  boolean term() {...}

  boolean opnd() {...}
    
}
 

Среда используется при анализе VAR. Его логическое значение равно env.get(tokenizer.getVarName()) .

Поэтому, чтобы обработать файл, вы должны

 For each line
   For each variable tX in the expression
      See if the line contains the string tX is bound to in its text field.
         If so, put the mapping tX -> true in the environment
         else put tX -> false
   Reset the tokenizer
   Call Evaluator.evaluate(tokenizer, environment)
   If it returns true, print the line, else skip it.
 

Это самый простой подход, который я могу придумать. Около 150 строк. Возможно множество оптимизаций.

Добавлен

Что ж, поскольку я больше не могу лишать себя острых ощущений от открытия, вот моя версия:

 import static java.lang.Character.isDigit;
import static java.lang.Character.isWhitespace;
import java.util.HashMap;
import java.util.Map;
import static java.util.stream.Collectors.toMap;

public class TextExpressionSearch {
  enum Token { VAR, LP, RP, NOT, AND, OR, END }
  
  static class Tokenizer {
    final String input;
    int pos = 0;
    String var;
    
    Tokenizer(String input) {
      this.input = input;
    }
        
    void reset() {
      pos = 0;
      var = null;
    }
    
    String getRead() {
      return input.substring(0, pos);
    }
    
    Token getNext() {
      var = null;
      while (pos < input.length() amp;amp; isWhitespace(input.charAt(pos))) {
          pos;
      }
      if (pos >= input.length()) {
        return Token.END;
      }
      int start = pos  ;
      switch (input.charAt(start)) {
      case 't':
        while (pos < input.length() amp;amp; isDigit(input.charAt(pos))) {
            pos;
        }
        var = input.substring(start, pos);
        return Token.VAR;
      case '(':
        return Token.LP;
      case ')':
        return Token.RP;
      case 'n':
        if (input.startsWith("ot", pos)) {
          pos  = 2;
          return Token.NOT;
        }
        break;
      case 'a':
        if (input.startsWith("nd", pos)) {
          pos  = 2;
          return Token.AND;
        }
        break;
      case 'o':
        if (input.startsWith("r", pos)) {
          pos  = 1;
          return Token.OR;
        }
        break;
      }
      throw new AssertionError("Can't tokenize: "   input.substring(start));
    }
  }
  
  static class Evaluator {
    final Tokenizer tokenizer;
    final Map<String, Boolean> env;
    Token lookAhead;
        
    Evaluator(Tokenizer tokenizer, Map<String, Boolean> env) {
      this.tokenizer = tokenizer;
      this.env = env;
      advance();
    }
    
    boolean die(String msg) {
      throw new AssertionError(msg   "nRead: "   tokenizer.getRead());
    }
    
    void advance() {
      lookAhead = tokenizer.getNext();
    }
    
    void match(Token token) {
      if (lookAhead != token) {
        die("Expected "   token   ", found "   lookAhead);
      }
      advance();
    }
    
    boolean evaluate() {
      boolean exprVal = expr();
      match(Token.END); 
      return exprVal;
    }
    
    boolean expr() {
      boolean lhs = negated();
      switch (lookAhead) {
      case AND:
        advance();
        return negated() amp;amp; lhs;
      case OR:
        advance();
        return negated() || lhs;
      case END:
        return lhs;
      }
      return die("Expected expr, found "   lookAhead);
    }

    boolean negated() {
      switch (lookAhead) {
      case NOT:
        advance();
        return !negated();
      default:
        return operand();
      }
    }
    
    boolean operand() {
      switch (lookAhead) {
      case VAR:
        if (!env.containsKey(tokenizer.var)) {
          die("Undefined variable: "   tokenizer.var);
        }
        boolean varVal = env.get(tokenizer.var);
        advance();
        return varVal;
      case LP:
        advance();
        boolean exprVal = expr();
        match(Token.RP);
        return exprVal;
      }
      return die("Expected operand, found "   lookAhead);
    }
  }
  
  public static void main(String [] args) {
    String expr = "((not t1 and ((not t2 or t4) or (t3 or t4))) or (t5 and not t6)) and t7";
    Map<String, String> bindings = new HashMap<>();
    bindings.put("t1", "str1");
    bindings.put("t2", "str2");
    bindings.put("t3", "str3");
    bindings.put("t4", "str4");
    bindings.put("t5", "str5");
    bindings.put("t6", "str6");
    bindings.put("t7", "str7");    
    String [] lines = {"str5 str7", "str4 str2"};
    Tokenizer tokenizer = new Tokenizer(expr);
    for (String line : lines) {
      Map<String, Boolean> env = 
          bindings.entrySet().stream()
              .collect(toMap(e -> e.getKey(), e -> line.contains(e.getValue())));
      tokenizer.reset();
      if (new Evaluator(tokenizer, env).evaluate()) {
        System.out.println(line);
      }
    }
  }
}
 

Для потомков, вот мое решение для маневрового двора, которое включает проверку ввода:

 public class CustomInputParser {
private Stack<Character> ops;
private LinkedList<Character> postFix;
private HashMap<Character, Integer> precedence;
private Stack<Boolean> eval; 
private HashMap<Integer, String> termsMap;
private String customBool;

public CustomInputParser(HashMap<Integer, String> tMap, String custBool) {
    this.ops = new Stack<Character>();
    this.eval = new Stack<Boolean>();
    this.postFix = new LinkedList<Character>();
    this.termsMap = tMap;
    this.customBool = custBool;
    this.precedence = new HashMap<Character, Integer>();
    precedence.put('n', 1);
    precedence.put('a', 2);
    precedence.put('o',3);
    precedence.put('(', 4);
     
}

private int inToPost() {
    char[] expr = convertToArr(this.customBool);
    char c;
    for(int i = 0; i < expr.length; i  ) {
        c = expr[i];
        if(isOp(c)) {
            if(processOp(c) != 0) return -1;
        }
        else {
            if(!Character.isDigit(c)) {
                return -1;
            }
            
            
            
            //I made the mistake of using a queue of Characters for postfix initially
            //This only worked for up to 9 operands (multi digit would add mutiple chars to
            // postfix for a single reference.
            //This loops is a lazy workaround: 
            //   1. get the string of the reference (e.g. "11")
            //   2. convert it to int
            //   3. store the char value of the int in postfix
            //   4. when evaluating operands in postfix eval, convert char back to int to get the termsMap key
            String num = "";
            while(i < expr.length) {
                if(!Character.isDigit(expr[i])) {
                    i--;
                    break;
                }
                c = expr[i];
                num  = c;
                i  ;
            }
            int j = Integer.valueOf(num);
            c = (char) j;
            postFix.offer(c); //enqueue
            
            
        }
    }
    while(!ops.empty()) {
        if(ops.peek() == '(')return -1; //no matching close paren for the open paren
        postFix.offer(ops.pop()); //pop and enqueue all remaining ops from stack
    }
    return 0;
}

private boolean isOp(char c) {
    if(c == '(' || c == ')' || c =='n' || c=='a' || c=='o') {
        return true;
    }
    return false;
}

private int processOp(char c) {
    if (ops.empty() || c == '(') {
        ops.push(c);
    }
    else if(c == ')') {
        while(ops.peek() != '(') {
            postFix.offer(ops.pop()); //pop and equeue ops wrapped in parens
            if(ops.empty()) return -1; //no matching open paren for the close paren
        }
        ops.pop(); // don't enqueue open paren, just remove it from stack
    }
    else if(precedence.get(c) > precedence.get(ops.peek())) {
        postFix.offer(ops.pop()); //pop and enqueue the higher precedence op
        ops.push(c);
    }
    else {
        ops.push(c);
    }
    return 0;
    
}

public boolean evaluate(String s) {
    while(!postFix.isEmpty()) {
        char c = postFix.poll();
        boolean op1, op2;
        switch(c) {
            case 'n':
                op1 = eval.pop();
                eval.push(!op1);
                break;
                
            case 'a':
                op1 = eval.pop();
                op2 = eval.pop();
                eval.push(op1 amp;amp; op2);
                break;
                
            case 'o':
                op1 = eval.pop();
                op2 = eval.pop();
                eval.push(op1 || op2);
                break;
            
            default:
                int termKey = (int) c;
                String term = this.termsMap.get(termKey);
                eval.push(s.contains(String.valueOf(term)));
                break;
        }
    }
    return eval.pop();
}

private char[] convertToArr(String x) {
    x = x.replace("not", "n").replace("and","a").replace("or", "o").replace("t", "").replace(" ", "");
    return x.toCharArray();
}


public static void main(String[] args) {
    String customBool = "(t1 and not (t2 and t3)) or (t4 and not t5)";
    HashMap<Integer,String> termsMap = new HashMap<Integer, String>();
    termsMap.put(1,"str1");
    termsMap.put(2,"str2");
    termsMap.put(3,"str3");
    termsMap.put(4,"str4");
    termsMap.put(5,"str5");
    CustomInputParser c = new CustomInputParser(termsMap, customBool);
    if(c.inToPost() != 0) {
        System.out.println("invalid custom boolean");
    }
    else {
    System.out.println(c.evaluate("str1str5"));
    }
    
    
}
 

}

Вы можете определить анализатор, который возвращает Predicate<String> значение, которое проверяет, удовлетворяет ли данная строка условному выражению.

 static Predicate<String> parse(String s, Map<String, String> map) {
    return new Object() {
        String[] tokens = Pattern.compile("[()]|[a-z][a-z0-9]*")
            .matcher(s).results()
            .map(MatchResult::group)
            .toArray(String[]::new);
        int length = tokens.length;
        int index = 0;
        String token = get();

        String get() {
            return token = index < length ? tokens[index  ] : null;
        }

        boolean eat(String expect) {
            if (expect.equals(token)) {
                get();
                return true;
            }
            return false;
        }

        Predicate<String> identifier() {
            String id = token;
            return s -> {
                String value = map.get(id);
                if (value == null)
                    throw new RuntimeException(
                        "identifier '"   id   "' undefined");
                return s.contains(value);
            };
        }

        Predicate<String> factor() {
            boolean not = false;
            Predicate<String> p;
            if (eat("not"))
                not = true;
            switch (token) {
            case "(":
                get();
                p = expression();
                if (!eat(")"))
                    throw new RuntimeException("')' expected");
                break;
            case ")": case "not": case "and": case "or":
                throw new RuntimeException("syntax error at '"   token   "'");
            default:
                p = identifier();
                get();
                break;
            }
            if (not)
                p = p.negate();
            return p;
        }

        Predicate<String> term() {
            Predicate<String> p = factor();
            while (eat("and"))
                p = p.and(factor());
            return p;
        }

        Predicate<String> expression() {
            Predicate<String> p = term();
            while (eat("or"))
                p = p.or(term());
            return p;
        }

        Predicate<String> parse() {
            Predicate<String> p = expression();
            if (token != null)
                throw new RuntimeException("extra tokens string");
            return p;
        }
    }.parse();
}
 

тестовый случай:

 @Test
public void testParse() {
    String s = "not ((t1 and not t3) or (t4 and t2)) or t5";
    Map<String, String> map = new HashMap<>(Map.of(
        "t1", "str1",
        "t2", "str2",
        "t3", "str3",
        "t4", "str4",
        "t5", "str5"));
    Predicate<String> p = parse(s, map);
    assertTrue(p.test("str5"));
    assertTrue(p.test("str3"));
    assertTrue(p.test("str1 str3"));
    assertFalse(p.test("str1"));
    assertFalse(p.test("str2 str4"));
    // you can change value of variables.
    assertFalse(p.test("str1 FOO"));
    map.put("t5", "FOO");
    assertTrue(p.test("str1 FOO"));
}
 

синтаксис:

 expression = term { "or" term }
term       = factor { "and" factor }
factor     = [ "not" ] ( "(" expression ")" | identifier )
identifier = letter { letter | digit }
letter     = "a" | "b" | ... | "z"
digit      = "0" | "1" | ... | "9"