Traverse JSON logic into a statement

Question

JSON input as:

{
  "AND": 
     [ 
       {"OR": [ { "EQUALS" : {"X":"Y"} }, { "EQUALS": {"Z":"W"} } ]},
       {"EQUALS" : {"A": "B"} } 
     ]
}

EQUALS takes a pair
AND - OR take a list

               AND
             /    \
            OR     EQ
            / \    / \
           EQ  EQ  A B
           / \ / \
          X  Y Z  W

Output after traversing should be:

( A EQUALS B AND ( X EQUALS Y OR Z EQUALS W ) )

Theoretically I understand that I should have the JSON as a tree and traverse it in an In-Order (left-root-right) method.

Practically, I implemented the in-order method that accepts a tree (tagged with root and left and right.. as deep as it can get). However, I can't seem to have the right idea of how to read the JSON as a tree and tag its content, if that's the right idea!

Any ideas?

Answer 1

Indeed, you can use an in-order traversal. Using recursion, it could look like this:

def dfs(node):
    key, value = list(node.items())[0]
    if isinstance(value, list):
        yield "("
        yield from dfs(value[0])
        yield ")"
        yield key
        yield "("
        yield from dfs(value[1])
        yield ")"
    else:
        a, b = list(value.items())[0]
        if isinstance(b, (list, dict)):
            yield key
            yield "("
            yield from dfs(value)
            yield ")"
        else:
            yield a
            yield key
            yield b

Example use:

tree = {
    "NOT": {
        "AND": [{
            "OR": [{
                "NOT": {
                    "EQUALS" : {"X":"Y"}
                } 
            }, {
                "EQUALS": {"Z":"W"}
            }]
        }, {
            "EQUALS" : {"A": "B"}
        }]
    }
}

print(" ".join(dfs(tree)))

Output for this example:

NOT ( ( ( NOT ( X EQUALS Y ) ) OR ( Z EQUALS W ) ) AND ( A EQUALS B ) )