Преобразование выражения к Обратной Польской Нотации

Delphi , Синтаксис , Математика

Автор: Avr555
WEB-сайт: http://delphibase.endimus.com

{ **** 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 result

  function 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) do
  begin
    if Prior(AStr[i]) = -1 then //Значит просто переменная
      AddToResult(AStr[i])
    else //Операции
    begin
      if High(Stack) = -1 then {a}
        AddToStack(AStr[i])
      else
      begin
        if AStr[i] = '(' then {в}
          AddToStack(AStr[i])
        else
        begin

          if AStr[i] = ')' then {г}
          begin
            k := High(Stack);
            while (k >= 0) and (Stack[k] <> '(') do
            begin
              AddToResult(Stack[k]);
              SetLength(Stack, High(Stack)); //Удаляем элемент из стека
              k := k - 1;
            end;
            //Удаляем открывающуюся скобку
            SetLength(Stack, High(Stack)); //Удаляем элемент из стека

          end
          else
          begin
            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 do
  begin
    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) do
  begin
    SetLength(tmp, high(tmp) + 2);
    tmp[high(tmp)] := S[i];
  end;
  rtmp := ConvertToRPN(tmp);
  s1 := '';

  for i := 1 to High(rtmp) do
  begin
    s1 := s1 + rtmp[i];
  end;
end;

Перевод контента на русский язык:

Функции и процедуры

• ConvertToRPN: Основная функция, которая принимает массив строк (OperList) в качестве входного параметра и возвращает другой массив строк в формате обратной польской нотации (RPN).
• Prior: Помощник-функция, определяющая приоритет оператора (например, NOT, +, -, и т.д.) на основе его типа. Приоритет используется для определения момента, когда нужно извлечь операторы из стека.
• AddToStack и AddToResult: Процедуры, добавляющие элементы в стек или массив результатов соответственно.

Основной алгоритм Конвертирующий процесс涉гает следующие шаги: 1. Инициализируйте пустой стек (Stack) и пустой массив результатов (AResult). 2. Перейдите по выражению входного параметра (AStr). Для каждого элемента: * Если это переменная (т.е., не оператор), добавьте ее в массив результатов. * Если это оператор, проверьте его приоритет с помощью функции Prior. * Если стек пуст или текущий оператор имеет более высокий или равный приоритет, чем верхушка стека, поместите его на стек. * Если стек не пуст и текущий оператор имеет ниже приоритет, чем верхушка стека, извлекайте операторы из стека до тех пор, пока не будет найден оператор с более низким приоритетом или стек не будет пустым. Затем поместите текущий оператор на стек. * Если текущий элемент является открывающей скобкой (, поместите ее на стек. * Если текущий элемент является закрывающей скобкой ), извлекайте операторы из стека до тех пор, пока не будет найдена открывающая скобка, а затем отбросьте обе скобки.

Пример использования Предоставленный пример демонстрирует, как использовать эту функцию для конвертации выражения из инфиксной нотации в RPN. Он определяет процедуру test, которая конвертирует выражение (A+B)*(C+D)-E и печатает результат в формате RPN.

Предложения по улучшению * Рассмотрите добавление обработки ошибок для недопустимых входных выражений. * Вы можете улучшить код, используя более описательные имена переменных и комментарии к сложной логике. * Вместо использования стека в виде массива можно использовать динамический массив или связанный список для улучшения эффективности реализации. * Функция Prior может быть упрощена с помощью словаря или таблицы поиска вместо длинного ряда if-запросов.

Преобразование выражения в Обратную Польскую Нотацию (RPN) - это процесс, при котором исходное выражение преобразуется в последовательность операторов и переменных, соответствующую порядку выполнения операций.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Математика ::