Польський інверсний запис для регулярних виразів

Польський інверсний запис (ПОЛІЗ) для регулярних виразів будується на основі початкового регулярного виразу на основі наступних правил:

- Порядок операндів в початковому виразі і в перетвореному виразі співпадають.

- Операції в перетвореному виразу йдуть з урахуванням пріоритету безпосередньо за операндами.

Наприклад, ПОЛІЗ для виразу (a*+b)*c має такий вигляд: a*b+*c^. .

В цьому прикладі в стандартному записі регулярного виразу бінарна операція конкатенація (^.) природньо опущена, але в ПОЛІЗ потрібно завжди цю операцію явно вказувати. Важливою характеристикою ПОЛІЗ є відсутність дужок в запису виразу.

Алгоритм. Перетворення регулярного виразу в ПОЛІЗ.

Для перетворення виразу в ПОЛІЗ необхідно з кожною операцією зв’язати деяке число, яке будемо називати “пріоритет” (0 – найвищий пріоритет присвоїмо дужці '(').

П0. Прочитати поточну лексему.

П1. Якщо поточна лексема операнд, то занести її в поле результату та перейти

на П0.

П2. Якщо поточна лексема '(', то занести її в стек та перейти на П0.

П3. Якщо поточна лексема код операції, то доки пріоритет операції на вершині стека більший або рівний пріоритетові поточної операції, елементи з вершини стека перенести в поле результату. Поточну лексему занести в стек та перейти на П0.

П4. Якщо поточна лексема ')', то з вершини стека в поле результату перенести всі коди операцій, які передують в стеку ')'. Дужку '(' зняти з вершини стека та перейти на П0.

П5. Якщо досягли кінця вхідного виразу, то всі елементи із стека перенести в поле результату.