Индивидуальные задания

Написать программу по созданию, добавлению (в начало, в конец), просмотру (с начала, с конца) и решению поставленной в лаб.раб.3 задачи для двунаправленных линейных списков.

Лабораторная работа №5. Обратная польская запись

Цель работы: изучить правила формирования постфиксной записи арифметических выражений с использованием стека.

Краткие теоретические сведения

Одной из задач при разработке трансляторов является задача расшифровки арифметических выражений.

Выражение a+b записано в инфиксной форме, +ab – в префиксной, ab + – в постфиксной формах. В наиболее распространенной инфиксной форме для указания последовательности выполнения операций необходимо расставлять скобки. Польский математик Я. Лукашевич использовал тот факт, что при записи постфиксной формы скобки не нужны, а последовательность операндов и операций удобна для расшифровки.

Постфиксная запись выражений получила название обратной польской записи (ОПЗ). Например, в ОПЗ выражение

r = (a + b) *(c + d) – e;

выглядит следующим образом:

r = ab + cd + * e –.

Алгоритм преобразования выражения из инфиксной формы в формуОПЗ был предложен Дейкстрой. При его реализации вводится понятие стекового приоритета операций.

Рассмотрим алгоритм получения ОПЗ из исходной строки символов, в которой записано выражение в инфиксной форме.

1. Символы-операнды переписываются в выходную строку, в которой формируется постфиксная форма выражения.

2. Открывающая скобка записывается в стек.

3. Очередная операция выталкивает в выходную строку все операции из стека с большим или равным приоритетом.

4. Закрывающая скобка выталкивает все операции из стека до ближайшей открывающей скобки в выходную строку, открывающая скобка удаляется из стека, а закрывающая – игнорируется.

5. Если после просмотра последнего символа исходной строки в стеке остались операции, то все они выталкиваются в выходную строку.