{ **** UBPFD *********** by delphibase.endimus.com ****
>> Преобразование выражения к Обратной Польской Нотации
Для работы функции необходимо определить тип:
type
OperList = array of widestring;
Параметром функции служит массив из переменных и операторов.
Результат - массив из переменных и операторов
Зависимости: SysUtils
Автор: avr555, avr555@mail.ru, ICQ:15782989
Copyright: Переделано с http://algolist.manual.ru/syntax/revpn.php
Дата: 26 мая 2002 г.
***************************************************** }function ConvertToRPN(AStr: OperList): OperList;
var
i, k: integer;
Stack: OperList; //Stack
AResult: OperList; //Tmp for resultfunction Prior(AOper: widestring): integer;
begin{Приоритет операции:
NOT - 8
унарный "-" - 7
"*", "/" - 6
"+", "-" - 5
">", "<", "=",
"<>", ">=",
"<=" - 4
"AND" - 3
"OR" - 2
"(", ")" - 1
}
AOper := trim(AOper);
result := -1;
if AOper = "NOT" then
Result := 8;
if (AOper = "*") or (AOper = "/") then
Result := 6;
if (AOper = "+") or (AOper = "-") then
Result := 5;
if (AOper = ">") or (AOper = "<") or (AOper = "<>") or (AOper = ">=")
or (AOper = "<=") or (AOper = "=") then
Result := 4;
if AOper = "AND" then
Result := 3;
if AOper = "OR" then
Result := 2;
if (AOper = "(") or (AOper = ")") then
Result := 1;
end;
procedure AddToStack(AOper: widestring);
begin{Добавление элементы в стек}
SetLength(Stack, High(Stack) + 2);
Stack[High(Stack)] := AOper;
end;
procedure AddToResult(AOper: widestring);
begin
SetLength(AResult, High(AResult) + 2);
AResult[High(AResult)] := AOper;
end;
begin{Конвертирование строку в Обратную Польскую Нотацию
Возвращает - массив
Алгоритм:
а) если стек пуст, то опеpация из входной стpоки пеpеписывается в стек;
б) опеpация выталкивает из стека все опеpации с большим или pавным
пpиоpитетом в выходную стpоку;
в) если очеpедной символ из исходной стpоки есть откpывающая скобка,
то он пpоталкивается в стек;
г) закpывающая кpуглая скобка выталкивает все опеpации из стека до
ближайшей откpывающей скобки, сами скобки в выходную стpоку не
пеpеписываются, а уничтожают дpуг дpуга.
}
Result := nil;
AResult := nil;
i := 0;
while i <= High(AStr) dobeginif Prior(AStr[i]) = -1 then//Значит просто переменная
AddToResult(AStr[i])
else//Операцииbeginif High(Stack) = -1 then{a}
AddToStack(AStr[i])
elsebeginif AStr[i] = "(" then{в}
AddToStack(AStr[i])
elsebeginif AStr[i] = ")" then{г}begin
k := High(Stack);
while (k >= 0) and (Stack[k] <> "(") dobegin
AddToResult(Stack[k]);
SetLength(Stack, High(Stack)); //Удаляем элемент из стека
k := k - 1;
end;
//Удаляем открывающуюся скобку
SetLength(Stack, High(Stack)); //Удаляем элемент из стекаendelsebegin
k := High(Stack);
while (k >= 0) and (Prior(Stack[k]) >= Prior(AStr[i])) do{б}begin
AddToResult(Stack[k]);
SetLength(Stack, high(Stack)); //Удаляем элемент из стека
k := k - 1;
end;
AddToStack(AStr[i]); //Если не скобка просто добавляем в стекend;
end;
end;
end;
i := i + 1;
end; //while//Сбрасываем все оставшееся из стекаfor i := high(Stack) downto 0 dobegin
AddToResult(Stack[i]);
end;
result := AResult;
end;
Пример использования:
procedure test;
var
s, s1: widestring;
tmp,
rtmp: OperList;
i: integer;
begin
s := "(A+B)*(C+D)-E";
tmp := nil;
rtmp := nil;
for i := 1 to Length(S) dobegin
SetLength(tmp, high(tmp) + 2);
tmp[high(tmp)] := S[i];
end;
rtmp := ConvertToRPN(tmp);
s1 := "";
for i := 1 to High(rtmp) dobegin
s1 := s1 + rtmp[i];
end;
end;
Если Вас заинтересовала или понравилась информация по разработке на Delph - "Преобразование выражения к Обратной Польской Нотации", Вы можете поставить закладку в социальной сети или в своём блоге на данную страницу: Так же Вы можете задать вопрос по работе этого модуля или примера через форму обратной связи, в сообщение обязательно указывайте название или ссылку на статью!