Рекурсивная функция или цикл Python для преобразования строки в логический объект json

Question

У меня есть эта функция:

def req_splitter(req_string):
    req = {}
    if " AND " in req_string:
        cond = "AND"
        req_splitted = req_string.split(" AND ")
    elif " OR " in req_string:
        cond = "OR"
        req_splitted = req_string.split(" OR ")
    else:
        cond = "AND"
        req_splitted = [req_string]

    if len(req_splitted) > 1:
        for sub_req in req_splitted:
            sub_req_splitted = req_splitter(sub_req)
            req[cond] = list()#new_req
            req[cond].append(sub_req_splitted)
    else:
        req[cond] = req_splitted
    return req

Он предназначен для преобразования в json-логические условия строк, подобных этой:

Barracks AND Tech Lab
Lair OR Hive
Hatchery OR Lair OR Hive
Cybernetics Core AND Gateway OR Warpgate
Forge AND Twilight Council AND Ground Armor 1
Spire OR Greater Spire AND Hive AND Flyer Flyer Carapace 2
Spire OR Greater Spire AND Lair OR Hive AND Flyer Attacks 1

Условие json_logic выглядит следующим образом:

{
    "and": [
            {
            "or": [
                "Gateway",
                "Warpgate"
            ]
        },
        "Cybernetics Core"
    ]
}

Как должна работать моя рекурсивная функция, чтобы помочь мне разбить строку на объект условия, как в примере выше?

---

Чтобы помочь вам понять проблему:

json_logic - это модуль, который проверяет условие, как словарь, который вы видите выше, и возвращает некоторый результат, в зависимости от того, с чем вы его сравниваете.

И как работает условие: ключ-значение par - это одно логическое утверждение. Ключ обозначает логическое условие. И значения в списке обозначают операнды. если само значение не список, а словарь, оно рекурсивно.

Вы можете сравнить его с " польской нотацией"

И последнее - операторы AND имеют больший приоритет, чем операторы OR, а операторы OR всегда вместе.

Answer 1

Вам нужно написать простой анализатор сверху вниз. Неподражаемый effbot написал отличный урок о таких вещах.

Токенизация просто делится на r'\s+(OR|AND)\s+' регулярное выражение, а затем признавая OR а также AND как операторы, остальные как литералы. AND а также OR знак .led() методы могут сгладить непосредственно вложенные операторы одного типа.

Я реализовал то, что описано там, используя немного больше ООП (а не глобальных), и сделал его совместимым с Python 2 и 3:

import re
from functools import partial


class OpAndToken(object):
    lbp = 10
    op = 'and'
    def led(self, parser, left):
        right = parser.expression(self.lbp)
        operands = []
        for operand in left, right:
            # flatten out nested operands of the same type
            if isinstance(operand, dict) and self.op in operand:
                operands.extend(operand[self.op])
            else:
                operands.append(operand)
        return {self.op: operands}


class OpOrToken(OpAndToken):
    lbp = 20
    op = 'or'


class LiteralToken(object):
    def __init__(self, value):
        self.value = value
    def nud(self):
        return self.value


class EndToken(object):
    lbp = 0


class Parser(object):
    operators = {'AND': OpAndToken, 'OR': OpOrToken}
    token_pat = re.compile("\s+(AND|OR)\s+")

    def __init__(self, program):
        self.program = program
        self.tokens = self.tokenizer()
        self.token = next(self.tokens)

    def expression(self, rbp=0):
        t = self.token
        self.token = next(self.tokens)
        left = t.nud()
        while rbp < self.token.lbp:
            t = self.token
            self.token = next(self.tokens)
            left = t.led(self, left)
        return left

    def tokenizer(self):
        for tok in self.token_pat.split(self.program):
            if tok in self.operators:
                yield self.operators[tok]()
            else:
                yield LiteralToken(tok)
        yield EndToken()

    def parse(self):
        return self.expression()

Это анализирует ваш формат в ожидаемый результат:

>>> Parser('foo AND bar OR spam AND eggs').parse()
{'and': ['foo', {'or': ['bar', 'spam']}, 'eggs']}

Демо на ваших входных строках:

>>> from pprint import pprint
>>> tests = '''\
... Barracks AND Tech Lab
... Lair OR Hive
... Hatchery OR Lair OR Hive
... Cybernetics Core AND Gateway OR Warpgate
... Forge AND Twilight Council AND Ground Armor 1
... Spire OR Greater Spire AND Hive AND Flyer Flyer Carapace 2
... Spire OR Greater Spire AND Lair OR Hive AND Flyer Attacks 1
... '''.splitlines()
>>> for test in tests:
...     pprint(Parser(test).parse())
...
{'and': ['Barracks', 'Tech Lab']}
{'or': ['Lair', 'Hive']}
{'or': ['Hatchery', 'Lair', 'Hive']}
{'and': ['Cybernetics Core', {'or': ['Gateway', 'Warpgate']}]}
{'and': ['Forge', 'Twilight Council', 'Ground Armor 1']}
{'and': [{'or': ['Spire', 'Greater Spire']}, 'Hive', 'Flyer Flyer Carapace 2']}
{'and': [{'or': ['Spire', 'Greater Spire']},
         {'or': ['Lair', 'Hive']},
         'Flyer Attacks 1']}

Обратите внимание, что для нескольких OR или же AND Операторы подряд операнды объединяются.

Я оставлю добавление поддержки для (...) скобки для читателя; учебник покажет вам, как это сделать (просто сделайте advance() функционировать метод на Parser класс и передать парсер в .nud() также вызывает или передает парсер при создании экземпляров класса токена).