|
:: MVP ::
|
|
|
:: RSS ::
|
|
|
Инфиксная нотация — это форма записи математических и логических формул, в которой операторы записываются
между операндами, на которые они воздействуют (например, a + b). В инфиксной нотации, в отличие от
префиксной и постфиксной,
скобки, окружающие группы операндов и операторов, определяют порядок, в котором будут выполнены операции (при отсутствии
скобок операции выполняются согласно правилам приоритета операторов).
- Если читаем число, то заносим его в стек;
- Если читаем знак операции, то:
- Берем 2 верхних элемента стека;
- Если в первом элементе приоритет операции меньше (и не равен 0), чем у рассматриваем операции,
то берем первый элемент в скобки;
- Аналогично для 2-го элемента;
- Записываем в стек строку вида:
- Для префиксной нотации: 1-й элемент + знак операции + 2-й элемент;
- Для постфиксной нотации: 2-й элемент + знак операции + 1-й элемент;
- Если строка полностью пройдена, то результатом является значение вершины стека.
Определим приоритеты операций:
type
TOpPriority = TDictionary<Char, Byte>;
var
OpPriority: TOpPriority;
procedure TInfixForm.FormCreate(Sender: TObject);
begin
OpPriority := TOpPriority.Create;
OpPriority.Add('^', 3);
OpPriority.Add('/', 2);
OpPriority.Add('*', 2);
OpPriority.Add('-', 1);
OpPriority.Add('+', 1);
// OpPriority.Add('(', 0);
end;
|
Разберем строку с формулой в соответствии с описанным выше алгоритмом (не забывая один важный нюанс -
если формула записана в префиксной нотации, ее предварительно нужно перевернуть):
function TInfixForm.Restore(Formula: string; Direction: TDirection): string;
var
c: Char;
MainPrior, PriorOp1, PriorOp2: Byte;
Op1, Op2: string;
sl: TStrings;
begin
sl := TStringList.Create;
if Direction = Prefix then
Formula := ReverseString(Formula);
for c in Formula do
begin
if c = ' ' then
Continue;
if CharInSet(c, ['a'..'z']) then
sl.Add(c)
else
begin
MainPrior := OpPriority.Items[c];
Op1 := sl.Pop;
PriorOp1 := GetPriority(Op1);
Op2 := sl.Pop;
PriorOp2 := GetPriority(Op2);
if (PriorOp1 < MainPrior) and (PriorOp1 <> 0) then
Op1 := '(' + Op1 + ')';
if (PriorOp2 < MainPrior) and (PriorOp2 <> 0) then
Op2 := '(' + Op2 + ')';
case Direction of
Prefix: sl.append(Op1 + c + Op2);
Postfix: sl.append(Op2 + c + Op1);
end;
end;
end;
Result := sl.Pop;
sl.Free;
end;
|
Метод извлечения последнего элемента из стека вынесен в хелпер для класса TStrings, что делает его использование
более простым и комфортным:
function TStringsHelper.Pop: string;
begin
Result := Self[Self.Count-1];
Delete(Self.Count-1);
end;
|
И не забудем, что перед разбором формулы, представленной в префиксной нотации, ее нужно развернуть:
procedure TInfixForm.Button1Click(Sender: TObject);
begin
// Исходнаяое выражение: ((a+b)*c)/(d-e)
// Префиксная нотация
ShowMessage(Restore('/*+abc-de', Prefix));
// Постфиксная нотация
ShowMessage(Restore('ab+c*de-/', Postfix));
end;
|
Ну вот и все, задача оказалась совсем не сложной. На этом все, спасибо за внимание! Успехов в программировании!
.: Пример к данной статье :.
|
|
При использовании материала - ссылка на сайт обязательна
|
|
