解析特定格式的字符串以构建二叉决策树

Question

我正在尝试解析一个带括号的字符串，格式是 ((问题)(左节点)(右节点))。

比如，问题的内容可能是“如果段大小小于1.5，就选择左节点，否则选择右节点”。这个问题可以看作是一个字典，里面有一个键和一个值。左节点和右节点代表一棵完整的左半树或右半树，我们会递归地遍历这些节点，直到到达叶子节点。通过这种方式，我们将构建一个二叉决策树。

Answer 1

如果你能确定输入格式的细节，那就可以直接用原生的Python代码来处理。例如，你可以把你的树结构存储在一个Python字典里，字典里的每个节点就像是一个小盒子：

tree = {
    "root": ("a", "b")
    "a": ("c", "d"),
    "b": ("e", "f"),
    "c": (None, None), #No children, a leaf.
    "d": (None, None),
    "e": (None, None),
    "f": (None, None),
}

这样，你就可以很简单地用Python的解析器来解析这个树结构了。

from tree_data import tree #We're done parsing!

root_node = tree["root"]
left_child = tree[root_node[0]]

不过，如果输入格式已经确定了，我们就没办法帮你，除非你分享这个格式的具体细节。

Answer 2

这种语法实际上是pyparsing的目标。基本格式相对简单，在pyparsing中，它看起来像这样：

decision = '(' + '('+question+')' + '('+action+')' + '('+action+')' + ')'

但是，一旦你开始添加算术表达式、布尔操作以及对“与”和“或”运算符的支持，事情就变得复杂了。此外，这是一种递归语法，因为一个动作本身可以是一个嵌套的决策。

Pyparsing内置了简化算术和布尔表达式定义的功能，包括运算的优先级和括号中的分组，以及递归表达式。下面是pyparsing语法的各个部分。首先是一些基本的解析元素：

LPAR,RPAR = map(Suppress,"()")
# old pyparsing way
number = Regex(r"[+-]?\d+(\.\d*)?").setParseAction(lambda tokens:float(tokens[0]))
# new pyparsing way - parses many numeric formats, and uses a parse action
# to convert to float
number = pyparsing_common.fnumber()
varname = Word(alphas+'_', alphanums+'_')

与数字表达式关联的解析动作会在解析时自动将解析出的数字转换为浮点值。Word类需要两个字符串：一个是所有有效前导字符的字符串，另一个是所有有效主体字符的字符串。这个变量名定义支持类似于Python标识符的变量名。

Pyparsing有一个infixNotation方法，它接受一个表达式作为基本操作数的定义，以及一个元组列表来定义每个运算符的级别：一个运算符的表达式，一个整数表示运算符是单目、双目还是三目，以及它是左结合还是右结合。infixNotation处理嵌套在括号中的算术表达式的递归定义。这个表达式定义了基本的四则运算：

operand = number | varname
arithExpr = infixNotation(operand,
    [
    (oneOf("+ -"), 1, opAssoc.RIGHT),
    (oneOf("* /"), 2, opAssoc.LEFT),
    (oneOf("+ -"), 2, opAssoc.LEFT),
    ])

现在这里是布尔条件的定义（我们最终会用它来定义决策问题）：

TRUE = CaselessKeyword("TRUE") | Keyword("T")
FALSE = CaselessKeyword("FALSE") | Keyword("F")
comparisonOp = oneOf("< > <= >= = !=")
boolLiteral = TRUE | FALSE
arithComparison = arithExpr + comparisonOp + arithExpr
boolOperand = boolLiteral | arithComparison
booleanExpr = infixNotation(boolOperand,
    [
    ('not', 1, opAssoc.RIGHT),
    ('and', 2, opAssoc.LEFT),
    ('or', 2, opAssoc.LEFT),
    ])

你对动作的定义有点模糊，所以我编了一些可能的语句：一个赋值语句，一个print语句，以及由于这是一个语音应用程序，一个与print非常相似的say语句。

rhs = booleanExpr | arithExpr
assignment = varname("assign_var") + '=' + Group(rhs)("assign_value")
print_cmd = Keyword("print") + Group(delimitedList(rhs  | quotedString))
say_cmd = Keyword("say") + Group(delimitedList(rhs | quotedString))
cmd = print_cmd | say_cmd | assignment

除了表达式定义外，你会注意到一些表达式后面跟着一个引号字符串，就好像这个表达式是用那个字符串调用的函数。实际上，这个“调用”实际上返回的是表达式的一个副本，匹配的标记会被标记上那个名字。这些结果名称在解析后提取单个匹配元素时非常有用（类似于正则表达式中的命名组）。

最后，为了将这些部分组合成你的决策表达式，这里是问题和动作表达式：

IF = CaselessKeyword("IF")
question = LPAR + IF + Group(booleanExpr)("condition") + RPAR
action = LPAR + cmd + RPAR | Group(decision)

注意，动作定义可以包含一个决策，但动作是用来定义决策的。为了打破这种鸡生蛋的依赖关系，我们在这一部分前面定义decision，但使用pyparsing的Forward类来占位：

decision = Forward()

然后在定义了question和action之后，我们使用‘<<=’运算符将实际的表达式定义“插入”到现有的decision变量中：

decision <<= (LPAR
              + question
              + Group(action)("ifAction")
              + Optional(Group(action)("elseAction"))
              + RPAR)

再次说明，我对你定义的格式进行了些许修改，认为可选的else子句可能会有用。如果你不想让它可选，只需去掉Optional包裹在Group(action)("elseAction")周围的部分。

这定义了语法，现在这里有一些测试用例。使用dump()函数打印parseString返回的结果是一个很好的方法，可以输出标记及其附加的任何名称。

tests = """\
    ((if TRUE)(a=99))

    ((if TRUE)(a = (a=99)))

    ((if a<100)(a = a + 1))

    ((if a<100)(a = a + 1)(a = a-1))

    (
     (if a<100)
     (print a, "is too small") 
     ( (if a>100) (print a,"is too big") (print a, "is just right") )
    )

    (
     (if a<100)
     (say a, "is too small!") 
     ( (if a>100) (say a,"is too big!") (say a, "is just right!") )
    )
    """

for d in decision.searchString(tests):
    print d.dump()
    print

这是输出结果：

['IF', ['TRUE'], ['a', '=', [99.0]]]
- condition: ['TRUE']
- ifAction: ['a', '=', [99.0]]
  - assign_value: [99.0]
  - assign_var: a

['IF', ['TRUE'], ['a', '=', ['a', '=', 99.0]]]
- condition: ['TRUE']
- ifAction: ['a', '=', ['a', '=', 99.0]]
  - assign_value: ['a', '=', 99.0]
  - assign_var: a

['IF', ['a', '<', 100.0], ['a', '=', [['a', '+', 1.0]]]]
- condition: ['a', '<', 100.0]
- ifAction: ['a', '=', [['a', '+', 1.0]]]
  - assign_value: [['a', '+', 1.0]]
  - assign_var: a

['IF', ['a', '<', 100.0], ['a', '=', [['a', '+', 1.0]]], 
    ['a', '=', [['a', '-', 1.0]]]]
- condition: ['a', '<', 100.0]
- elseAction: ['a', '=', [['a', '-', 1.0]]]
  - assign_value: [['a', '-', 1.0]]
  - assign_var: a
- ifAction: ['a', '=', [['a', '+', 1.0]]]
  - assign_value: [['a', '+', 1.0]]
  - assign_var: a

['IF', ['a', '<', 100.0], ['print', ['a', '"is too small"']], 
    [['IF', ['a', '>', 100.0], ['print', ['a', '"is too big"']], 
    ['print', ['a', '"is just right"']]]]]
- condition: ['a', '<', 100.0]
- elseAction: [['IF', ['a', '>', 100.0], ['print', ['a', '"is too big"']], 
                ['print', ['a', '"is just right"']]]]
- ifAction: ['print', ['a', '"is too small"']]

['IF', ['a', '<', 100.0], ['say', ['a', '"is too small!"']], 
    [['IF', ['a', '>', 100.0], ['say', ['a', '"is too big!"']], 
        ['say', ['a', '"is just right!"']]]]]
- condition: ['a', '<', 100.0]
- elseAction: [['IF', ['a', '>', 100.0], ['say', ['a', '"is too big!"']], 
                ['say', ['a', '"is just right!"']]]]
- ifAction: ['say', ['a', '"is too small!"']]

这里是完整解析程序的链接 - http://pastebin.com/DnaNrx7j。

这只是第一阶段，解析输入。下一步是通过处理返回的标记来实际评估表达式。pyparsing示例SimpleBool.py（https://github.com/pyparsing/pyparsing/blob/master/examples/simpleBool.py）包括一个示例，展示如何将解析动作附加到解析的标记，以将其转换为可调用的类实例，从而简化结果的评估。

希望这对你有帮助。