Разбор логических выражений - PullRequest
Новая
       93

Разбор логических выражений

3 голосов
/ 14 июля 2020

У меня есть задача, в которой мне нужно отфильтровать Pandas DataFrame на основе указанного пользователем логического выражения. Теперь я видел модуль PyParser или LARK, который я хотел бы использовать, но не могу понять, как их настроить.

У меня есть несколько операторов, например CONTAINS, EQUAL, FUZZY_MATCH и c. Кроме того, я хотел бы объединить некоторые выражения в более сложные.

Пример выражения:

ColumnA CONTAINS [1, 2, 3] AND (ColumnB FUZZY_MATCH 'bla' OR ColumnC EQUAL 45)

В результате я хотел бы иметь несколько структурированный Dict или List с уровнями операций в порядке их выполнения. Итак, желаемый результат для этого примера выражения будет примерно таким: 

[['ColumnA', 'CONTAINS', '[1, 2, 3]'], 'AND', [['ColumnB', 'FUZZY_MATCH', 'bla'], OR, ['ColumnC', 'EQUAL', '45']]]

или в форме dict: 

{
  'EXPR1': {
    'col': 'ColumnA', 
    'oper': 'CONTAINS', 
    'value': '[1, 2, 3]']
  },
  'OPERATOR': 'AND', 
  'EXPR2': {
    'EXPR21': {
      'col': 'ColumnB', 
      'oper': 'FUZZY_MATCH', 
      'value': 'bla'
    }, 
    'OPERATOR': OR, 
    'EXPR22': {
      'col': 'ColumnC', 
      'oper': 'EQUAL', 
      'value': '45'
    }
  }
}

Или что-то в этом роде. Если у вас есть лучший способ структурировать результат, я открыт для предложений. Я новичок в этом, поэтому уверен, что это можно улучшить.

1 Ответ

1 голос
/ 14 июля 2020

Интересная задача:)

Похоже на относительно простое применение алгоритма маневровой площадки . Я написал код для синтаксического анализа выражений вроде "((20 - 10 ) * (30 - 20) / 10 + 10 ) * 2" поверх здесь . 

import re


def tokenize(str):
   return re.findall("[+/*()-]|\d+", expression)

def is_number(str):
    try:
        int(str)
        return True
    except ValueError:
        return False


def peek(stack):
    return stack[-1] if stack else None


def apply_operator(operators, values):
    operator = operators.pop()
    right = values.pop()
    left = values.pop()
    values.append(eval("{0}{1}{2}".format(left, operator, right)))


def greater_precedence(op1, op2):
    precedences = {"+": 0, "-": 0, "*": 1, "/": 1}
    return precedences[op1] > precedences[op2]


def evaluate(expression):
    tokens = tokenize(expression)
    values = []
    operators = []
    for token in tokens:
        if is_number(token):
            values.append(int(token))
        elif token == "(":
            operators.append(token)
        elif token == ")":
            top = peek(operators)
            while top is not None and top != "(":
                apply_operator(operators, values)
                top = peek(operators)
            operators.pop()  # Discard the '('
        else:
            # Operator
            top = peek(operators)
            while top is not None and top != "(" and greater_precedence(top, token):
                apply_operator(operators, values)
                top = peek(operators)
            operators.append(token)
    while peek(operators) is not None:
        apply_operator(operators, values)

    return values[0]


def main():
    expression = "((20 - 10 ) * (30 - 20) / 10 + 10 ) * 2"
    print(evaluate(expression))


if __name__ == "__main__":
    main()

Я думаю, мы можем немного изменить код, чтобы он работал в вашем случае:

  1. Нам нужно изменить способ токенизации входной строки в tokenize(). В принципе, учитывая строку ColumnA CONTAINS [1, 2, 3] AND (ColumnB FUZZY_MATCH 'bla' OR ColumnC EQUAL 45), нам нужен список токенов: ['ColumnA', 'CONTAINS', '[1, 2, 3]', 'AND', '(', 'ColumnB', 'FUZZY_MATCH', "'bla'", 'OR', 'ColumnC', 'EQUAL', '45', ')']. Это в значительной степени будет зависеть от того, насколько сложной может быть входная строка, и потребует некоторой обработки строки, но это довольно просто, и я оставлю это вам.
  2. Измените функцию is_number(), чтобы определять такие вещи, как ColumnA, [1, 2, 3] и c. По сути, все, кроме предикатов CONTAINS / FUZZY_MATCH / EQUAL, операторов AND / OR и скобок ( / ).
  3. Измените greater_precedence(op1, op2), чтобы вернуть true в case op1 находится среди ['CONTAINS', 'EQUAL', ..], а op2 - это ['AND', 'OR']. Это потому, что мы хотим, чтобы contains и equals всегда оценивались перед AND / OR.
  4. Измените apply_operator(operators, values), чтобы реализовать logi c того, как оценивать логическое выражение ColumnA CONTAINS [1, 2, 3] или выражение true AND false. Помните, что CONTAINS / FUZZY_MATCH / EQUAL / AND / OR et c все здесь операторы. Вероятно, вам нужно будет написать здесь много случаев if-else, так как может быть много разных операторов.
...