Разбор строки заданного формата для построения двоичного дерева решений

Question

Я пытаюсь разобрать строку с круглыми скобками формы ((Question)(Left_Node)(right_node)).

Вопрос, например, будет иметь форму «если размер сегмента < 1,5, а затем выбрать левый узел, иначе правый». Вопрос может быть словарем с ключом и значением. Левый и правый узлы представляют собой полное левое или правое половинное дерево, которое будет проходить рекурсивно до тех пор, пока не будет достигнут лист. Таким образом мы построим двоичное дерево решений.

Answer 1

Если вы можете определить детали входного формата, используйте исходный исходный код 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), 
} 

Теперь вы можете разобрать это дерево просто с питона анализатором.

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,"()") 
number = Regex(r"[+-]?\d+(\.\d*)?").setParseAction(lambda tokens:float(tokens[0])) 
varname = Word(alphas+'_', alphanums+'_') 

разбора действия прилагаются к выражению номера будет автоматически преобразовывать разобранное число в значение с плавающей точкой во время синтаксического анализа. Класс Word принимает две строки: строку, содержащую все допустимые ведущие символы, и строку всех действительных символов тела. Это определение varname поддерживает имена переменных, похожие на идентификаторы Python.

Pyparsing имеет метод operatorPrecedence, который принимает выражение для определения основного операнда и список кортежей для определения каждого уровня операторов: выражение для операторов, целое число, является ли оператор унарным, двоичным или троичным, и является ли левым или право-ассоциативным. operatorPrecedence заботится о рекурсивном определении арифметических выражений, вложенных в круглые скобки. Это выражение определяет основные 4-математическую функции:

operand = number | varname 
arithExpr = operatorPrecedence(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 = operatorPrecedence(boolOperand, 
    [ 
    ('not', 1, opAssoc.RIGHT), 
    ('and', 2, opAssoc.LEFT), 
    ('or', 2, opAssoc.LEFT), 
    ]) 

Вашего определение действий был немного отрывочным, поэтому я составил некоторые возможные утверждения: оператор присваивания, оператор print, и поскольку это речевое приложение, оператор say, который очень близок к print.

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) 

Опять же, я принял вольность с определенным форматом, думая, что факультативный еще придаточного может быть полезным. Если вы не хотите, чтобы это было необязательным, просто удалите обертку 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.

Это только первый этап анализа синтаксического анализа. Следующий шаг фактически оценивает выражение, обрабатывая возвращенные маркеры. Пример википарации wiki SimpleBool.py (http://pyparsing.wikispaces.com/file/view/simpleBool.py) включает пример присоединения действий синтаксического анализа для преобразования обработанных токенов в вызываемые экземпляры классов, которые упрощают оценку результатов.

Надеюсь, это поможет.