Wyrażenia matematyczne w formie tradycyjnej notacji algebraicznej można obliczyć za pomocą algorytmu ONP (Odwrotna Notacja Polska). W pierwszej części artykułu pokażę jak zaimplementować parser konwertujący wyrażenie matematyczne z tradycyjnej postaci na notację ONP. Natomiast w drugiej części artykułu, algorytm obliczania takiego wyrażenia oraz architekturę pozwalającą na łatwe rozszerzenie parsera o nowe własne funkcje.

Notacja infiksowa i postfiksowa

Priorytet wykonywania działań algebraicznych w tradycyjnej postaci infiksowej można zmienić za pomocą nawiasów. W tej postaci, operator działania jest umieszczony pomiędzy operandami. W notacji postfiksowej (beznawiasowej), operator jest umieszczony za operandami. Tak więc w tym zapisie można całkowicie zrezygnować z używania nawiasów, ponieważ kolejność wykonywania działań wynika z priorytetu operatorów

Konwersja wyrażenia do postaci ONP

Przedstawiony algorytm wykorzystuje stos do odkładania operatorów oraz kolejki dla operandów i funkcji. W przeciwieństwie do algorytmu opisanego na Wikipedii, obsługuje sytuację dla unarnego plus/minus.

Przebieg iteracyjnego algorytmu

Implementacja klasy konwersji do ONP

Napiszemy klasę dokonującą konwersji wyrażenia infiksowego na postfiksową. Jako struktury pomocnicze, zostaną wykorzystane stos i kolejka. W poniższym listingu te struktury korzystają z generycznych kolekcji dostępnych dopiero w środowisku od wersji XE. Dla niższych wersji Delphi należy użyć obiektów TStack i TQueue z modułu Contnrs i ręcznie rzutować wskaźniki na odpowiedni typ danych.

Deklaracja klasy TParser

unit ONPParser;
interface
uses
  Generics.Collections, SysUtils;
type
  TParser = class
    const
      PRIORITY_ADD = Byte(1);
      PRIORITY_MULTI = Byte(2);
      PRIORITY_POWER = Byte(3);
      PRIORITY_FUNC = Byte(4);
    private
     FStack: TStack<TMathObject>;
      FQueue: TQueue<TMathObject>;
      FExpression: string;
      FResult: Double;
      FPriorityRules: TDictionary<Char, Byte>;
      procedure EraseCntr(Sender: TObject; const Item: TMathObject; Action: TCollectionNotification);
      procedure InfixToPostfix;
      procedure Calc;
      procedure Clear;
    public
      constructor Create;
      destructor Destroy; override;
      procedure Calculate(const Expression: string);
      function GetResult: Double;
end;

Deklaracja klasy TMathObject

Klasa będzie odpowiedzialna za obsługę obiektu matematycznego i operacji konwersji danych.

type
  TMathObject = class;
  TMathObjectType = (mtUndefined, mtString, mtFloat);
  TMathArgs = Generics.Collections.TList<TMathObject>;
  TMathObject = class
    private
      FData: Variant;
      FType: TMathObjectType;
      FPriority: Byte;
    public
      function ToFloat: Double;
      function ToInt: Integer;
      function ToString: string; override;
      function ToChar: Char;
      function GetPriority(): Byte; inline;
      function IsFunction(): Boolean; inline;
      constructor Create(const Data: Double); overload;
      constructor Create(const Data: string); overload;
      constructor Create(const Data: string; Priority: Byte); overload;
end;

Implementacja klasy TMathObject

constructor TMathObject.Create(const Data: string);
begin
  FData := Data;
  FType := mtUndefined;
end;
constructor TMathObject.Create(const Data: Double);
begin
  FData := Data;
  FType := mtFloat;
end;
constructor TMathObject.Create(const Data: string; Priority: Byte);
begin
  FData := Data;
  FType := mtString;
  FPriority := Priority;
end;
function TMathObject.ToFloat: Double;
begin
  if FType <> TMathObjectType.mtFloat then
    Result := StrToFloat(FData, Fmt)
  else
    Result := Double(FData);
end;
function TMathObject.ToInt: Integer;
begin
  if FType<> TMathObjectType.mtFloat then
    Result := StrToInt(FData)
  else
    Result := Trunc(FData);
end;
function TMathObject.ToString: string;
begin
  if FType = TMathObjectType.mtFloat then
    Result := FloatToStr(FData, Fmt)
  else
    Result := FData;
end;
function TMathObject.ToChar: Char;
begin
  Result := ToString[1];
end;
function TMathObject.GetPriority(): Byte;
begin
  Result := FPriority;
end;
function TMathObject.IsFunction(): Boolean;
begin
  Result := FType = mtString;
end;

Mając gotową implementację klasy TMathObject, uzupełnijmy definicję klasy TParser.

Konstruktor i destruktor klasy

constructor TParser.Create;
begin
  FResult := NaN;
  FStack := TStack<TMathObject>.Create();
  FQueue := TQueue<TMathObject>.Create();
  FStack.OnNotify := EraseCntr;
  FQueue.OnNotify := EraseCntr;
  FPriorityRules := TDictionary<Char, Byte>.Create(5);
  FPriorityRules.Add('+', PRIORITY_ADD);
  FPriorityRules.Add('-', PRIORITY_ADD);
  FPriorityRules.Add('*', PRIORITY_MULTI);
  FPriorityRules.Add('/', PRIORITY_MULTI);
  FPriorityRules.Add('^', PRIORITY_POWER);
end;

destructor TParser.Destroy;
begin
  Clear;
  FPriorityRules.Free;
  FQueue.Free;
  FStack.Free;
end;

Definicje pozostałych metod

procedure TParser.EraseCntr(Sender: TObject; const Item: TMathObject; Action: TCollectionNotification);
begin
  if Action = cnRemoved then
    Item.Free;
end;
function TParser.GetResult;
begin
  Result := FResult;
end;
procedure TParser.Calculate(const Expression: string);
begin
  FExpression := Expression;
  Clear;
  InfixToPostfix;
  Calc;
end;
procedure TParser.Clear;
begin
  FStack.Clear;
  FQueue.Clear;
end;

Implementacja metody parsujÄ…cej

procedure TParser.InfixToPostfix;
const
  Brackets = ['(', ')'];
  OperatorSet = ['+', '-', '*', '/', '^'];
  NumberSet = ['0' .. '9', '.'];
  FunctionSet = ['A' .. 'Z'];
  UnarySet = ['+', '-'];
  ArgsSeparator = ';';
var
  I, Ind: Integer;
  Len: Integer;
  MathObject: TMathObject;
  Unary: Boolean;
  Priorit: Byte;
begin
  I := 1;
  Len := Length(FExpression);
  Unary := True;
  while I <= Len do
  begin
    if CharInSet(FExpression[I], NumberSet) then
    begin
      Unary := False;
      Ind := I;
      while (I <= Len) and CharInSet(FExpression[I], NumberSet) do
        Inc(I);
      MathObject := TMathObject.Create(Copy(FExpression, Ind, I - Ind));
      FQueue.Enqueue(MathObject);
    end
    else if CharInSet(FExpression[I], FunctionSet) then
    begin
      Ind := I;
      while (I <= Len) and CharInSet(FExpression[I], FunctionSet) do
        Inc(I);
      MathObject := TMathObject.Create(Copy(FExpression, Ind, I - Ind),
                      PRIORITY_FUNC);
      FStack.Push(MathObject);
    end
    else if Unary and CharInSet(FExpression[I], UnarySet) then
    begin
      if FExpression[I] = '-' then
      begin
        MathObject := TMathObject.Create('NEG', PRIORITY_FUNC);
        FStack.Push(MathObject);
      end;
      Inc(I);
    end
    else if FExpression[I] = ArgsSeparator then
    begin
      while (FStack.Count > 0) and (FStack.Peek.ToString() <> '(') do
        FQueue.Enqueue(FStack.Extract);
      if FStack.Count = 0 then
        raise EParserError.Create('Left bracket not found');
      Inc(I);
      Unary := True;
    end
    else if FExpression[I] = '(' then
    begin
      MathObject := TMathObject.Create('(');
      FStack.Push(MathObject);
      Inc(I);
      Unary := True;
    end
    else if FExpression[I] = ')' then
    begin
      while (FStack.Count > 0) and (FStack.Peek.ToString() <> '(') do
        FQueue.Enqueue(FStack.Extract);
      if FStack.Count = 0 then
        raise EParserError.Create('Left bracket not found');
      FStack.Extract.Free;
      Inc(I);
      Unary := False;
    end
    else if CharInSet(FExpression[I], OperatorSet) then
    begin
      Priorit := FPriorityRules.Items[FExpression[I]];
      while (FStack.Count <> 0) and (Priorit <= FStack.Peek.GetPriority()) do
        FQueue.Enqueue(FStack.Extract);
      MathObject := TMathObject.Create(FExpression[I], Priorit);
      FStack.Push(MathObject);
      Inc(I);
      Unary := True;
    end
  end;
while FStack.Count <> 0 do
  begin
    if CharInSet(FStack.Peek.ToChar, Brackets) then
      raise EParserError.Create('Incorrect brackets');
    FQueue.Enqueue(FStack.Extract);
  end;
end;

Wykorzystanie

JeÅ›li chcesz wykorzystać mój parser komercyjnie i/lub potrzebujesz pomocy aby go dostosować do swoich potrzeb – zapraszam do kontaktu.

Podsumowanie

W pierwszej części artykułu przedstawiona została implementacja algorytmu konwersji wyrażenia matematycznego do postaci ONP. W następnej części artykułu, uzupełniona zostanie metoda obliczająca to wyrażenie oraz sposób na rozbudowanie możliwości parsera o obsługę nowych funkcji matematycznych bez konieczności modyfikacji istniejącego kodu.

---

---

Podobne artykuły