In the first part of article I presented the parser for conversion a traditional algebraic expression to the RPN representation. In this part, I will show you, how to implement the algorithm for calculating the RPN expression and the architecture to extending abilities of the parser to support custom functions.

Custom mathematical functions

The main goal of our parser is to support any custom functions, without modification of the parser code. At beginning, we have to define the signature of the mathematical function, which will be responsible to execution of specific operations (such as: addition, substraction, multiplying etc.). Next, we define an interface, which will provide these functions for a parser. This will allow you to register a set of custom functions to the parser, so in easy way to extend the parser for handling a new formulas.

Prototype of the math function

I will define the type of mathematical function. All mathematical functions will be of this type. The first argument will contain definition of the function, and the second argument, a list of arguments required for the compute a result.

Add below code to the MathObjects.pas module:

TMathArgs = Generics.Collections.TList<TMathObject>;
TMathFunc = function(Functor: TMathObject; Args: TMathArgs): Double of object;

For each custom mathematical function, we have to define its name to inform the parser that this function has to be called and a list of arguments should be taken from the stack. For example: “NEG” function that negates the value, it requires one argument.

Definition of the mathematical function packet

TMathBind = record
  Name: string;
  Func: TMathFunc;
  ArgsCount: Integer;
  constructor Create(const AName: string; const AFunc: TMathFunc;
    const AValue: Integer);
end;
 
constructor TMathBind.Create(const AName: string; const AFunc: TMathFunc;
                                const AValue: Integer);
begin
  Name := AName;
  Func := AFunc;
  ArgsCount := AValue;
end;

Definition of the mathematical function provider interface. Each class that provide a collection of mathematical functions will implement this interface.

TMathFunctions = Generics.Collections.TList<TMathBind>;
  IMathProvider = interface
    function MathFunctions(): TMathFunctions;
end;

Implementation of basic mathematical functions

In this section I will define a class of basic mathematical functions. For this purpose, we use IMathProvider interface, which will be implemented by the TArithmeticProvider class to return the collection of the TMathBind records.

Declaration of the TArithmeticProvider

type
  TArithmeticProvider = class(IMathProvider)
    protected
      Funcs: TMathFunctions;
    public
      constructor Create;
      destructor Destroy; override;
      function MathFunctions(): TMathFunctions;
      class function Add(Functor: TMathObject; Args: TMathArgs): Double;
      class function Sub(Functor: TMathObject; Args: TMathArgs): Double;
      class function Divide(Functor: TMathObject; Args: TMathArgs): Double;
      class function Multi(Functor: TMathObject; Args: TMathArgs): Double;
      class function Power(Functor: TMathObject; Args: TMathArgs): Double;
      class function Negate(Functor: TMathObject; Args: TMathArgs): Double;
end;

Implementation

constructor TArithmeticProvider.Create;
begin
  Funcs := TMathFunctions.Create;
  Funcs.Add(TMathBind.Create('+', TArithmeticProvider.Add, 2));
  Funcs.Add(TMathBind.Create('-', TArithmeticProvider.Sub, 2));
  Funcs.Add(TMathBind.Create('/', TArithmeticProvider.Divide, 2));
  Funcs.Add(TMathBind.Create('*', TArithmeticProvider.Multi, 2));
  Funcs.Add(TMathBind.Create('^', TArithmeticProvider.Power, 2));
  Funcs.Add(TMathBind.Create('NEG', TArithmeticProvider.Negate, 1));
end;
 
destructor TArithmeticProvider.Destroy;
begin
  Funcs.Free;
end;
 
function TArithmeticProvider.MathFunctions: TMathFunctions;
begin
  Result := Funcs;
end;

Definition of the basic mathematical functions

class function TArithmeticProvider.Negate(Functor: TMathObject; Args: TMathArgs): Double;
begin
  Result := -Args[0].ToFloat();
end;
 
class function TArithmeticProvider.Add(Functor: TMathObject; Args: TMathArgs): Double;
begin
  Result := Args[0].ToFloat() + Args[1].ToFloat();
end;
 
class function TArithmeticProvider.Sub(Functor: TMathObject; Args: TMathArgs): Double;
begin
  Result := Args[0].ToFloat() - Args[1].ToFloat();
end;
 
class function TArithmeticProvider.Divide(Functor: TMathObject; Args: TMathArgs): Double;
begin
  if SameValue(Args[1].ToFloat(), 0.0) then
    raise Exception.Create('Division by zero');
  Result := Args[0].ToFloat() / Args[1].ToFloat();
end;
 
class function TArithmeticProvider.Multi(Functor: TMathObject; Args: TMathArgs): Double;
begin
  Result := Args[0].ToFloat() * Args[1].ToFloat();
end;
 
class function TArithmeticProvider.Power(Functor: TMathObject; Args: TMathArgs): Double;
begin
  if SameValue(Args[0].ToFloat(), 0.0) and SameValue(Args[1].ToFloat(), 0.0) then
    raise Exception.Create('0 ^ 0');
  Result := Math.Power(Args[0].ToFloat(), Args[1].ToFloat());
end;

As mentioned previously, the Args array contains necessary arguments to compute value of function. The length of array depends on the ArgsCount parameter. The parser pops from the stack these parameters. The Args array is a collection of TMathObject object . The TMathObject class allows to easy manipulate the data. Supporting a new formula, comes to creating new function according to the TMathFunc type.

Calculating the RPN expression

The TParser class has implemented function of conversion to the RPN format. After executing a InfixToPostfix function, the TQueue queue will contain a sequence of tokens according to the RPN notation. Based on this sequence, the result will be computed by the RPN algorithm.

RPN algorithm

  1. For each token of the RPN expression:
    • If the token is a value, pop it from the queue onto the stack
    • If the token is an operator/function:
      • Pop appropriate amount of tokens from the stack. Call appropriate function and pass a list of arguments
      • Push the returned result onto the stack
  2. The value of RPN expression will be at the top of the stack.

TParser – registration functions

In the TParser class is missing a Calc method implementation, for computing RPN expression. First, we add the ability to register a previously created mathematical functions, which will be used in the Calc method. To do it, we create a dictionary of the TMathBind records.

Add a below code to the declaration of the TParser class:

FFunctions: TDictionary<string, TMathBind>;
procedure RegisterProvider(Provider: IMathProvider);

Initialization of the dictionary in the constructor:

FFunctions := TDictionary<string, TMathBind>.Create(20);

and release the memory of dictionary in destructor:

FFunctions.Free;

Implementation of the RegisterProvider function:

procedure TParser.RegisterProvider(Provider: IMathProvider);
var
  Func: TMathBind;
begin
  for Func in Provider.MathFunctions() do
    FFunctions.Add(Func.Name, Func);
end;

Now, we can extend the parser abilities by registering a mathematical functions.

Implementation of the RPN algorithm

procedure TParser.Calc;
var
  MathBinder: TMathBind;
  Res: Double;
  MathArgs: TMathArgs;
begin
  while FQueue.Count <> 0 do
  begin
    if not FQueue.Peek.IsFunction() then
      FStack.Push(FQueue.Extract)
    else
    begin
      if FFunctions.ContainsKey(FQueue.Peek.ToString()) then
      begin
        MathArgs := TMathArgs.Create;
        MathBind := FFunctions.Items[FQueue.Peek.ToString()];
        while (FStack.Count > 0) and (MathBind.ArgsCount > 0) do
        begin
          MathArgs.Add(FStack.Extract);
          Dec(MathBind.ArgsCount);
        end;
        MathArgs.Reverse;
        Res := MathBind.Func(FQueue.Peek, MathArgs);
        FStack.Push(TMathObject.Create(Res));
        MathArgs.Free;
      end;
      FQueue.Extract.Free;
    end;
  end;
  FResult := FStack.Peek.ToFloat();
end;

Usage

With a full implementation of the RPN parser and implementations of the basic mathematical functions we can combine everything together and test the calculations on a simple formula.

procedure btnTest_click(sender: TObject);
var
  Parser: TParser;
  Provider: IMathProvider;
begin
  Parser := TLsCalc.Create;
  Provider := TArithmeticProvider.Create;
  try
    Parser.RegisterProvider(Provider);
    Parser.Calculate('-2+2*2');
    ShowMessage(FloatToStr(Parser.GetResult));
  finally
    Parser.Free;
    Provider.Free;
  end;
end;

First, we create instance of the TParser class and provider of the basic mathematical functions. We have to register the provider in the instance of parser by the RegisterProvider function. After this, we can test the parser by entering a simple mathematical expression.

Usage

If you want to use my parser code or need help to fit it to your requirements, you can contact with me.

Summary

In a two-part article, I presented a way to implement the RPN algorithm. In a flexible way, you can add your own custom functions for computing complex expressions.

If you find any errors or questions, please contact me via the contact form or comment.


Related posts

Comments

5 responses to “Calculation of mathematical expressions using RPN in Delphi”

  1. Jim Rohlf says:

    This is very instructive! How much difficulty would there be to modify the parser to allow variable names rather than just numerical values to operate on? In my application there would be some predefined quantities (like pi, e, etc.).

    Thanks for posting such useful and well-documented code.

    • Tomasz Maciejewski Tomasz Maciejewski says:

      You can create PI function with the same signature like presented above functions which returns Math.PI
      Next, you have to register this function with 0 arguments count.

  2. Jim Rohlf says:

    Oh, they can be handled as “functions” but with no arguments. I will try that. Thanks.

  3. B.Siva says:

    what to use for IMathProvider in the use section of the programm in delphi????

Leave a Reply

Your email address will not be published. Required fields are marked *