Здесь проще всего написать рекурсивную функцию разбора или конечный автомат со стеком. Будут проблемы в реализации - пиши, поможем
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Построение дерева синтаксического анализа |
| Автор: Stampede 17.5.2005, 18:14 |
| Вот столкнулся с задачкой: имеется строка, содержащая некое выражение в инфиксной нотации, примерно такого вида: (A B C) где A и C - некие операнды, каждый из которых, в свою очередь, может быть рекурсивно представлен формулой аналогичного вида, и так далее: ((a b ((c d e) f (g h i))) j (k l m)) Построить собственно дерево - не вопрос, но возникла идея приспособить для этого дела регулярное выражение - чтобы, так сказать, попользоваться плодами технического прогресса. В принципе грамматика тривиальная, но как составить регексп таким образом, чтобы он коррестно находил и возвращал самые внешние операнды? То есть в случае данного примера: A = (a b ((c d e) f (g h i))) B = j C = (k l m) Если такое возможно, то всех делов будет - организовать рекурсию. Но вот возможно ли, в этом я не очень уверен, тем более что с регекспами я тово, не сильно дружу. Будут какие-нибудь идеи? |
| Автор: Void 17.5.2005, 19:40 |
| Приспособить регулярные выражения для распознавания такой записи невозможно. Дело в том, что эта скобочная запись - контекстно свободная грамматика, а регэкспы распознают только праволинейные (автоматные) грамматики, которые являются подмножеством КС-грамматик. Здесь проще всего написать рекурсивную функцию разбора или конечный автомат со стеком. Будут проблемы в реализации - пиши, поможем |
| Автор: Stampede 17.5.2005, 20:04 | ||
Вот за что ценю экспертное знание - за способность мгновенно отсекать тупиковые варианты Я, кстати, уже и сам спинным мозгом прочуствовал, что ерунда какая-то получается с регекспом: громоздко, некрасиво и ненадежно, даже если бы принципиально это оказалось возможно. Тем более что распарсить рекурсивно вручную всех делов оказалось где-то на (линенйых) полметра кода |