Python recursive function or cycle to convert string to json logical object
<p>I have this function:</p>

<pre><code>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) &gt; 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
</code></pre>

<p>It is intended to convert to json-logic conditions a strings like this one:</p>

<pre><code>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
</code></pre>

<p>json_logic condition is looks like this:</p>

<pre><code>{
    "and": [
            {
            "or": [
                "Gateway",
                "Warpgate"
            ]
        },
        "Cybernetics Core"
    ]
}
</code></pre>

<p>How my recursive function should work to help me to split the string to the condition object like the example above?</p>

<hr>

<p>To help you understand the problem: </p>

<p><a href="http://jsonlogic.com/" rel="nofollow">json_logic</a> is a module that checks the condition, like the dictionary you see above and returns some result, depending with what you compare it.</p>

<p>And how the condition works: 
key-value par is one single logical statement.
The key stands for logical condition.
And the values in list is stands for operands.
if a value itself not a list but a dictionary, it recurses.</p>

<p>You can compare it to "<a href="https://en.wikipedia.org/wiki/Polish_notation" rel="nofollow">polish notation</a>"</p>

<p>And last thing - AND statements has more priority than OR statements, and OR statements are always together.</p>

<p>You'll need to write a simple top-down parser. The inimitable effbot wrote a <a href="http://effbot.org/zone/simple-top-down-parsing.htm" rel="nofollow">great tutorial</a> about just that kind of thing.</p>

<p>Tokenizing is just splitting on the <code>r'\s+(OR|AND)\s+'</code> regex, then recognising <code>OR</code> and <code>AND</code> as operators, the rest as literals. The <code>AND</code> and <code>OR</code> token <code>.led()</code> methods could flatten out directly nested operators of the same type.</p>

<p>I've implemented what is described there using a little more OOP (and not globals), and made it Python 2 and 3 compatible:</p>

<pre><code>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 &lt; 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()
</code></pre>

<p>This parses your format into the expected output:</p>

<pre><code>&gt;&gt;&gt; Parser('foo AND bar OR spam AND eggs').parse()
{'and': ['foo', {'or': ['bar', 'spam']}, 'eggs']}
</code></pre>

<p>Demo on your input lines:</p>

<pre><code>&gt;&gt;&gt; from pprint import pprint
&gt;&gt;&gt; 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()
&gt;&gt;&gt; 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']}
</code></pre>

<p>Note that for multiple <code>OR</code> or <code>AND</code> operators in a row the operands are combined.</p>

<p>I'll leave adding support for <code>(...)</code> parentheses to the reader; the tutorial shows you how to do this (just make the <code>advance()</code> function a method on the <code>Parser</code> class and pass the parser in to <code>.nud()</code> calls too, or pass in the parser when creating token class instances).</p>

python json recursion logic polish-notation