![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Одной из задач при разработке трансляторов является задача расшифровки арифметических выражений.
Выражение a+b записано в инфиксной форме, +ab – в префиксной, ab + – в постфиксной формах. В наиболее распространенной инфиксной форме для указания последовательности выполнения операций необходимо расставлять скобки. Польский математик Я. Лукашевич использовал тот факт, что при записи постфиксной формы скобки не нужны, а последовательность операндов и операций удобна для расшифровки.
Постфиксная запись выражений получила название обратной польской записи (ОПЗ). Например, в ОПЗ выражение
r = (a + b) *(c + d) – e;
выглядит следующим образом:
r = ab + cd + * e –.
Алгоритм преобразования выражения из инфиксной формы в формуОПЗ был предложен Э. Дейкстрой. При его реализации вводится понятие стекового приоритета операций.
Рассмотрим алгоритм получения ОПЗ из исходной строки символов, в которой записано выражение в инфиксной форме.
1. Символы-операнды переписываются в выходную строку, в которой формируется постфиксная форма выражения.
2. Открывающая скобка записывается в стек.
3. Очередная операция выталкивает в выходную строку все операции из стека с большим или равным приоритетом.
4. Закрывающая скобка выталкивает все операции из стека до ближайшей открывающей скобки в выходную строку, открывающая скобка удаляется из стека, а закрывающая – игнорируется.
5. Если после просмотра последнего символа исходной строки в стеке остались операции, то все они выталкиваются в выходную строку.
Дата публикования: 2015-02-22; Прочитано: 288 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!