Всё для Учёбы — студенческий файлообменник
1 монета
doc

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

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

Пример 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; begin

if (ptrStackNil) then //если стек не пустой

begin ptr:= ptrStack; //запоминаем указатель на бывшую вершину стека

Pop:=ptrStack^.oper; //значение функции - верхний символ

ptrStack:=ptrStack^.pred; //делаем новую вершину стека

dispose (ptr); //освобождаем память из-под старой вершины стека

end

else Pop:=CHR(0);

end; //функция выдает значение приоритета операции

function prior (oper:char):integer;

begin

case oper of '(': prior:=0;

'-': prior:=1;

'+': prior:=1;

'*': prior:=2;

'/': prior:=2;

else prior:=2

end; end; BEGIN

writeln('Введите арифметическое выражение:');

readln(inStr);

for i:=1 to Length(inStr) do

case inStr[i] of

'A'..'Z','a'..'z': OutStr:=OutStr+InStr[i];

'(': Push('(',0);

')':

Begin while(ptrStacknil) and (ptrStack^.oper'(') do OutStr:=OutStr+Pop;

if ptrStack=nil then

begin writeln('Нет открывающей скобки для закрывающей в позиции: ',i);

Readln;Halt;

end; Pop;

end;

'+','-','*','/':

begin while (ptrStacknil) and (prior(InStr[i])

Показать полностью…
Похожие документы в приложении