Simple decision tree (nested if-statement) in Python?

Question

I'd like to define a nested if-statement in JSON and test it with Python. I'm thinking about a simple decision tree with nested branches, being tested recursively.

Pseudocode:

# is_valid = (a == b OR a == a) AND c == c  # True
tree = {
    branches: [
        {
            value1: 'a',
            operator: '==',
            value2: 'b',
            child_connector: 'or'
            children: [
                {
                    value1: 'a',
                    operator: '==',
                    value2: 'a'
                }   
            ]
        },
        {
            connector: 'and',
            value1: 'c',
            operator: '==',
            value2: 'c'
        }
    ]
}

def is_tree_valid(tree):
    # TODO
    return

is_valid = is_tree_valid(tree)

When I googled for decision trees, I found a lot AI related, but often too deep. I'm looking for something simple and guess it's a common topic and was re-invented often enough.

I'd appreciate code snippets, modules or any other advice to complete is_tree_valid().

Thanks in advance!

Answer 1

This is as much about the input as the algorithm, but designing them together is only reasonable. The simplest encoding of the expression to evaluate is a direct translation of the AST:

{
  "operator": "and",
  "left": {
    "operator": "or",
    "left": {
      "operator": "==",
      "left": "a",
      "right": "b"
    },
    "right": {
      "operator": "==",
      "left": "a",
      "right": "a"
    }
  },
  "right": {
    "operator": "==",
    "left": "c",
    "right": "c"
  }
}

Then (after parsing into the obvious Python structure), evaluation looks like

def evaluate(node):
  try: op=node['operator']
  except TypeError: return node  # leaf
  l=evaluate(node['left'])
  r=node['right']  # not evaluated yet
  if op=='==': return l==evaluate(r)
  elif op=='and': return l and evaluate(r)
  elif op=='or': return l or evaluate(r)
  else: raise ValueError("unknown operator: %r"%op)