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" 
    ] 
} 

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

---

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

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

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

Вы можете сравнить его с «polish notation»

И последняя вещь - И заявление имеет более высокий приоритет, чем OR заявления и OR заявление всегда вместе.

Answer 1

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

Tokenizing - это просто расщепление на регулярном выражении r'\s+(OR|AND)\s+', затем распознавание OR и 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']} 

Demo на ваших входных линий:

>>> 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() вызовы или передайте в парсер при создании экземпляров класса токенов).