Программирование — работа в Москве

Язык программирования: Python, Z3 Для себя На вход программе подаётся регулярное выражение, содержащее буквы латинского алфавита, круглые скобки, альтернативу, итерацию и опцию (вопросительный знак). Ассоциативность учитывается, т.е. выражения вида abc(a|b|) корректны. Тут же демонстрируется, что у альтернативы могут быть и пустые аргументы. Приоритеты тоже учитываются: итерация имеет максимальный приоритет, на втором месте конкатенация, слабее всех - альтернатива. Т.е. a|ba|bc*a читаем как (a)|(ba)|(b(c*)a). Необходимо построить (бинарное) дерево разбора регулярного выражения, сохраняющее его семантику. Метки узлов - конкатенация, альтернатива (опцию рассахариваем до альтернативы), итерация (у итерации только один потомок), пустая метка или буква (листовые метки).