Контрольная «Обратная польская запись» по Информатике (Попов Д. И.)

Кирилл Николоев вс, 12.03.2017 19:35

Обратная польская запись (ОПЗ) – это способ записи выражений (как правило алгебраических) в так называемом постфиксном (или суффиксном) виде, т.е. в таком виде, когда сначала записываются все операнды, а потом выполняемые над ними операции, т.е. для обычных бинарных операций сложения, вычитания, умножения и деления знак операции располагается после операндов, а не между ними как в привычном «инфиксном» виде. Одна из особенностей ОПЗ – отсутствие скобок, что позволяет вычислять ОПЗ за один проход слева направо. ОПЗ как правило используется в трансляторах и компиляторах для преобразования выражений в машинный код, их последующего вычисления, а также для анализа и трансляции синтаксических конструкций языка к виду, удобному для генерации машинного кода.

Пример 37. Представим выражение (a+b)/(c/a*c – e*d) в постфиксном виде: ОПЗ: ab+ca/c*ed*–/. Вычислим ОПЗ слева на право, при вычислении пользуемся правилом: «в операции участвуют два операнда, расположенные слева от знака операции».

1. Первое вычисление: R1 = ab+ = a+b, подставляем в исходную строку вместо ab+ вычисленный результат R1 получается ОПЗ: R1ca/c*ed*–/. 2. Второе действие: R2 = ca/ = c/a ОПЗ: R1R2c*ed*–/ 3. Третье действие: R3 = R2c* = R2*c = c/a*c

ОПЗ: R1R3ed*–/ 4. Четвертое действие: R4 = ed* = e*d ОПЗ: R1R3R4–/ 5. Пятое действие: R5 = R3R4– = R3–R4 = c/a*c–e*d ОПЗ: R1R5/ 6. Шестое действие: R6 = R1R5/ = R1/R5=(a+b)/(c/a*c–e*d) ОПЗ: R6 ОПЗ вычислено и его значением стало значение выражения R6.

Наиболе известным алгоритмом перевода простого алгебраического выражения в ОПЗ является алгоритм Дейкстры (Э́дсгер Ви́бе Де́йкстра, 1930–2002, – выдающийся нидерландский ученый, идеи которого оказали огромное влияние на развитие компьютерной индустрии). Идея алгоритма основывается на использовании стека и анализе приоритета операций и заключается в следующем:

1. Исходная строка просматривается посимвольно, слева направо до достижения конца строки. 2. Если встречается символ операция, то эта операция при определенных условиях помещается в стек (затем при определенных условиях операции выталкиваются в выходную строку).

3. Если встречаются символы операндов, то они из входной строки поступают сразу в выходную строку. 4. Если встречается открывающаяся скобка, то она всегда помещается в стек. 5. Закрывающаяся скобка ни в стек, ни в выходную строку не помещается. Когда она встречается во входной строке, то из стека выталкиваются все символы до первой встречной открывающейся скобки включительно. При этом знаки операций выталкиваются в выходную строку, а открывающаяся скобка просто удаляется из стека.

6. Необходимо использовать следующие приоритеты операций (табл. 35). Чем больше значение приоритета, тем сильнее операция связывает операнды: Таблица 35. Приоритеты операций для вычисления ОПЗ Операции ( + – * /

Приоритет 0 1 1 2 2 7. Если во входной строке текущий символ – знак операции, то сравниваются приоритеты операций из строки и верхушки стека. 8. Если приоритет операции из входной строки больше приоритета операции из верхушки стека, то операция из входной строки стека перемещается в стек.

9. В противном случае из стека выталкиваются все операции с приоритетами большими либо равными приоритету операции из входной строки. После чего операция из входной строки помещается в стек. 10. При встрече конца входной строки содержимое стека выталкивается в выходную строку.

Пример 38. Напишем программу перевода входной строки в ОПЗ. program Project1; {$APPTYPE CONSOLE} uses SysUtils; type pStack=^ElemSteka; ElemSteka=record //в стеке храним два информационных поля oper : char; // операция

prior: integer; //приоритет pred : pStack; //Предыдущий (нижний) элемент стека end; //глобальные переменные var InStr:String=''; OutStr:string=''; //входная и выходная строка ptrStack:pStack=Nil; //указатель на вершину стека

i:integer; //процедура помещает в стек символ операции и ее приоритет procedure Push (oper:char; prior:integer); var ptr:pStack; begin new(ptr); //создаем новый узел - верхушку стека ptr^.pred:= ptrStack; //связываем с бывшей вершиной стека

ptrStack:=ptr; //теперь это есть новая верхушка ptrStack^.oper:=oper; //записываем данные в информационныую часть ptrStack^.prior:=prior; end; //удаляет эемент из вершины стека Function Pop:Char; var ptr:pStack;

Скачать файлы

Похожие документы