Лабораторная работа №12. Алгоритм перевода выражения в обратную польскую запись (Алгоритм Дейкстра).
Задание 1.
Используя записи и указатели, а также функции динамического распределения памяти (NEW, DISPOSE), реализовать программу для алгоритма Дейкстра. (ошибки ввода учесть).
Алгоритм Дейкстра – алгоритм перевода выражения в обратную польскую запись. Обратная польская запись представляет собой промежуточную форму выражения, которая используется в компиляторах и интерпретаторах для вычисления значения выражения. В обратной польской записи отсутствуют скобки, а операции всегда следуют за операндами, а не между ними.
Алгоритм Дейкстра
1) В стек (стек – это структура данных, хранящая совокупность однотипных элементов, которые поступают в стек и выходят из него по правилу «последний вошел - первый вышел») будут помещаться только символы операций.
2) Символы операндов из входной строки поступают сразу в выходную строку.
3) Символы операций сначала поступают в стек и при определенных условиях выталкиваются в выходную строку.
4) Открывающаяся скобка всегда попадает в стек.
5) Закрывающаяся скобка ни в стек, ни в выходную строку не попадает.
6) Когда встречается в выходной строке закрывающаяся скобка, из стека выталкиваются все символы до первой встречной открывающейся скобки включительно. Причем знаки операций выталкиваются в выходную строку, а открывающаяся скобка пропадает.
7) Необходимо использовать приоритеты операций:
( 0
+, - 1
*, / 2
Чем больше значение приоритета, тем сильнее операция связывает операнды.
8) Если во входной строке текущий символ – знак операции, то сравниваются приоритеты операций из строки и верхушки стека.
9) Если приоритет операции из входной строки больше приоритета операции из верхушки стека, то операция из входной строки стека перемещается в стек. В противном случае из стека выталкиваются все операции с приоритетами большими либо равными приоритетам операций из входной строки. После чего операция из входной строки помещается в стек.
10) При встрече конца входной строки содержимое стека выталкивается в выходную строку.
Например:
Входная строка: (a+b*c)*(a-b)/(d-(a+b*d))
Стек:
| ( | + | * | * | ( | - | * | / | ( | - | ( | + | * | - | / |
| ( | + | * | ( | / | ( | - | ( | + | ( | |||||
| ( | * | / | ( | - | ( | / | ||||||||
| / | ( | - | ||||||||||||
| / | ( | |||||||||||||
| / |
Выходная строка: abc*+ab-*dabd*+-/
Рекомендации.
1) 
Стек можно рассматривать как случай списка.
Для стека обязательно наличие указателя на вершину.
2) Если стек пуст, то указатель на вершину пустой (NIL).
3) Для данного примера данные в структуре списка это символы и числа (приоритеты).
4) Для работы со стеком необходимы как минимум две процедуры: push(втолкнуть) и pop(вытолкнуть). Для процедуры push необходимы два параметра (символ и приоритет); для процедуры pop в общем случае параметры не нужны, но в нашем примере необходим один параметр типа Boolean (TRUE-выталкивать в выходную строку; FALSE-выталкивать, но не в выходную строку).
5) Желательно написать функцию, которая бы по входному параметру-символу выдавала его приоритет.
type
point=^elsteka;
elsteka=record
oper:char;
prior:integer;
next:point;
end;
var instr, outstr:string;
uk_steka:point;
procedure push (oper:char; prior:integer);
var r_uk:point;
begin new(r_uk);
r_uk^.next:=uk_steka;
uk_steka:=r_uk;
uk_steka^.oper:=oper;
uk_steka^.prior:=prior;
end;
procedure pop (priznak:boolean);
var r_uk:point;
begin
if (priznak) and (uk_steka^.oper<>'(') then
outstr:=outstr+uk_steka^.oper;
r_uk:=uk_steka^.next;
dispose (uk_steka);
uk_steka:=r_uk;
end;
function prior (oper:char):integer;
type
el_t_prior=record
oper:char;
prior:integer;
end;
const tabl_prior:array[0..4] of el_t_prior=
( (oper:'('; prior:0),
(oper: '-'; prior:1),
(oper:'+'; prior:1),
(oper: '*'; prior:2),
(oper:'/'; prior:2)
);
var i:integer;
begin
for i:=0 to 4 do begin
if tabl_prior[i].oper=oper then
begin
prior:=tabl_prior[i].prior;
exit;
end;
end;
end;
6) Графический алгоритм программы:
 | |||
 |