Solved

Expressions / String parsing

Posted on 2001-07-23
16
715 Views
Last Modified: 2010-04-06
Hi,

I'm having problem to make a scriptish class that
is suppose to parse string expressions into delphi.

This is what I had in mind:

I have a string, lets say:
myStr := '(("Variable1" = "Variable2") OR
("Variable3" <> "Variable4")) AND (Variable5 > 0)';

Of course, this string could contain any delphish expression, such as: (just examples)
myStr := '"Variable1" = "Variable2"';
myStr := '("Variable1" <> "Variable2") AND ("Variable3" = "Variable4")';

Ok, now you should have an idea on how the input string
to my class should look.

TExpressionParser is a class,
with the events:
 OnCheckExpression(Token1, Operator,
   Token2: String; var IsTrue: Boolean);

 OnComplete(Final: Boolean);

and the procedure:
 ParseExpression(Expression: String);

What ParseExpression does is:
(this proc is called with myStr (see above) as parameter)

1) Parses the expression into many parts (i think
   a tree like structure would fit here?)

2) On every expression, it is to raise the
   OnCheckExpression with those parameter, where
   Token1 is the left variable, Operator is the
   operator ('>', '<>', '=' ..etc), Token2 is the
   rightmost variable.

3) User sets IsTrue to whatever he/she wishes.

4) TExpressionParsers takes the respons from every
   OnCheckExpression result and put it togheter
   and return a final variable (by raising the OnComplete
   event). TExpressionParsers should of course
   use all logical operators (and, not, or...etc),
   this should not be even showed to the user. (he is only
   to answer if each expression is true or false!

So, I want to know how I make this class :]
I lack the skills to write the actual parsing &
tree structure thing; i hope anyone could help/hint
me!

I will reward you well!
0
Comment
Question by:blasse
  • 6
  • 3
  • 2
  • +4
16 Comments
 
LVL 5

Expert Comment

by:scrapdog
Comment Utility
Is this meant only for parsing boolean expressions?

Given that you are passing the operands to an event, you are giving the user the responsibility for evaluating anything is not boolean (i.e. you are not going to evaluate x > y * (z + 1);  you will send "x", ">", and "y * (z + 1)" to the event handler).

If so, you only need to assign precedence to the boolean operators (NOT, AND, OR, in that order).  Relational operators will be evaluated from left to right as they are encountered, regardless of precedence.

I don't believe you will need a tree...a stack will probably suffice.  It will also help to convert the expression to postfix.

If the above description matches your needs, let me know, and I will help you work out an algorithm.

0
 
LVL 1

Expert Comment

by:alx512
Comment Utility
This is part of code what i use to calculate the arifmetic expressions. Make some modifications for yuor purpose.
I have not enouge time to write working code for you.
But i hope this example can help in your task.

  TCalcFunc = function(Params: Variant): Double of object;
  TStackDataType = (stOperator, stObject,  stConstant, stFunction);
  TOperation = (soNone, soAdd, soSub, soMul, soDiv);

  TStack = class(TObject)
  private
    { Private declarations }
    FStack: array [0..MaxStackSize] of Double;
    FStackPoint: integer;
    FCalculator: TCalculator;
  public
    { Public declarations }
    procedure Clear;
    function Current: Double;
    procedure push(Value: Double);
    function pop: Double;
  end;

  TFormulaTranslator = class(TObject)
  private
    { Private declarations }
    FCalculator: TCalculator;
    FCalcItem: TCalcItem;

    procedure GetExpression(const Expression: string; OperandType: TOperandType);
    procedure GetMultiplicand(const Multiplicand: string);
    procedure GetIdentificator(const Idn: string);
    procedure GetVariable(const Variable: string);
    procedure GetFunction(const Func: string; VarCount: integer);
    procedure GetConstant(const Constant: string);
    function FindNextOperand(const Expression: string;
      OperandType: TOperandType; var Operator: TOperation): string;

    function GetNamePart(const idn: string): string;
    function GetMonthPart(const idn: string): string;

    function CheckFunctionList(const FuncName: string; VarCount: integer): TCalcFunc;
    function CheckFunctionParams(Params: string): integer;
  public
    { Public declarations }
    constructor Create(ACalculator: TCalculator);
    destructor Destroy; override;
    procedure Translate(CalcItem: TCalcItem);
  end;


procedure TFormulaTranslator.Translate(CalcItem: TCalcItem);
var i: integer;
begin
  FCalcItem := CalcItem;
  for i:=0 to CalcItem.FormulaList.Count-1 do
    Dispose( PStackData(CalcItem.FormulaList.Items[i]));
  CalcItem.FormulaList.Clear;
  GetExpression(CalcItem.Formula, otComposer);
end;

function TFormulaTranslator.FindNextOperand(const Expression: string;
  OperandType: TOperandType; var Operator: TOperation): string;
var
  i, l, lp, rp: integer;
  Operators: set of char;
  ErrorText: string;
  NextExpr : string;
  MF: Boolean;
begin
  Result := '';
  case OperandType of
    otComposer:     Operators := ['+','-'];
    otMultiplicand: Operators := ['*','/'];
  end;
  l := length(Expression);
  lp := 0;
  rp := 0;
  MF := False;
  for i:=1 to l do
  begin
    if Expression[i] = '(' then Inc(lp);
    if Expression[i] = ')' then Inc(rp);
    if Expression[i] = '[' then MF := True;
    if Expression[i] = ']' then MF := False;
    if (lp=rp) and ((Expression[i] in Operators) and not MF or (i=l)) then
    begin
      case Expression[i] of
        '+': Operator := soAdd;
        '-': Operator := soSub;
        '*': Operator := soMul;
        '/': Operator := soDiv;
        else Operator := soNone;
      end;
      NextExpr := copy(Expression, 1, i-1+integer(Operator=soNone));
      case OperandType of
        otComposer: GetExpression( NextExpr, otMultiplicand);
        otMultiplicand: GetMultiplicand( NextExpr );
      end;
      if i<l then
        Result := copy(Expression, i+integer(Operator<>soNone),
          l-i-integer(Operator=soNone));
      Exit;
    end;
  end;
  if lp <> rp then
    ErrorText := esParNotEqul + Expression
  else if Expression[1]='-' then
    GetExpression( Expression, otMultiplicand)
  else
    ErrorText := esWrongSintax + Expression;
  raise ETranslateError.Create(ErrorText);
end;

procedure TFormulaTranslator.GetExpression(const Expression: string; OperandType: TOperandType);
var
  Operator: PStackData;
  Operation1, Operation2: TOperation;
  s: string;
begin
  s := Trim(Expression);
  if s = '' then Exit;
  s := FindNextOperand(s, OperandType, Operation1);
  while s <> '' do
  begin
    s := FindNextOperand(s, OperandType, Operation2);
    if Operation1 <> soNone then
    begin
      new(Operator);
      Operator^.DataType := stOperator;
      Operator^.Operation := Operation1;
      FCalcItem.FormulaList.Add(Operator);
    end;
    Operation1 := Operation2;
  end;
end;

procedure TFormulaTranslator.GetMultiplicand(const Multiplicand: string);
var
  l: integer;
  s: string;
  CalculatedObject: ICalculatedObject;
  Data: PStackData;
begin
  s := Trim(Multiplicand);
  l := length(s);
  case s[1] of
    '0'..'9': GetConstant(S);
    'a'..'z', 'A'..'Z': GetIdentificator(S);
    '(': GetExpression(copy(s,2,l-2), otComposer);
    '@':  begin
      CalculatedObject := FCalculator.GetObject(copy(s,2,l-1));
      if CalculatedObject = nil then
        raise ETranslateError.Create(esIdnExpected + s);
      New(Data);
      Data^.DataType := stConstant;
      Data^.Constant := CalculatedObject.Id;
      FCalcItem.FormulaList.Add(Data);
    end;
  end;
end;

procedure TFormulaTranslator.GetIdentificator(const Idn: string);
var
  i, l: integer;
  FuncName: string;
  CalcFunc: TCalcFunc;
  VarCount: integer;
  MF: Boolean;
begin
  MF := False;
  l := length(Idn);
  for i:=1 to l do
  if (Idn[i] in ['a'..'z','A'..'Z','0'..'9','_', '[', ']' ]) or MF then
  begin
    if Idn[i] = '[' then MF := True;
    if Idn[i] = ']' then MF := False;
  end
  else
    if (Idn[i] = '(') and (i>1) then
    begin
      FuncName := copy(idn,1,i-1);
      VarCount := CheckFunctionParams(copy(idn,i+1,l-i-1));
      CalcFunc := CheckFunctionList(FuncName, VarCount);
      if not Assigned(CalcFunc) then
        raise ETranslateError.Create(esUnknownFunction + Idn)
      else GetFunction(FuncName, VarCount);
      Exit;
    end
    else raise ETranslateError.Create(esWrongSintax+Idn);
  CalcFunc := CheckFunctionList(idn, 0);
  if Assigned(CalcFunc) then GetFunction(Idn, 0) else GetVariable(Idn);
end;

procedure TFormulaTranslator.GetVariable(const Variable: string);
var
  Data: PStackData;
  CalculatedObject: ICalculatedObject;
  Item: TAutoIntfObject;
  Month, Name: string;
  i: integer;
  Flag: Boolean;
begin
  Name := GetNamePart(Variable);
  Month := GetMonthPart(Variable);

  CalculatedObject := FCalculator.GetObject(Name);
  if CalculatedObject = nil then
    raise ETranslateError.Create(esUnknownIdn + Variable);
  Item := TAutoIntfObject(CalculatedObject.Instance);
  if Item is TCalcParam then
  begin
    Flag := False;
    for i:=0 to FCalcItem.Params.Count-1 do
      if FCalcItem.Params[i] = Item then
      begin
        Flag := True;
        break;
      end;
    if not Flag then
      raise ETranslateError.Create(esParamNotInList + Name);
  end;

  New(Data);
  Data^.Item := Item;
  Data^.DataType := stObject;

  if Month <> '' then
    GetExpression(Month, otComposer);
  Data^.SetMonth := (Month <> '');
  FCalcItem.FormulaList.Add(Data);
end;

procedure TFormulaTranslator.GetConstant(const Constant: string);
var
  i, l: integer;
  Data: PStackData;
  s: string;
begin
  s := Constant;
  l := length(s);
  for i:=1 to l do
  if not (s[i] in ['0'..'9', '.', ',']) then
     raise ETranslateError.Create(esNumberExpected + Constant)
  else
    if s[i] in ['.', ','] then s[i] := DecimalSeparator;
  New(Data);
  Data^.DataType := stConstant;
  Data^.Constant := StrToFloat(s);
  FCalcItem.FormulaList.Add(Data);
end;

procedure TFormulaTranslator.GetFunction(const Func: string; VarCount: integer);
var
  Data: PStackData;
begin
  New(Data);
  Data^.DataType := stFunction;
  Data^.FuncAdress := CheckFunctionList(Func, VarCount);
  Data^.VarCount := VarCount;
  FCalcItem.FormulaList.Add(Data);
end;

function TFormulaTranslator.CheckFunctionList(const FuncName: string; VarCount: integer): TCalcFunc;
var
  Count, i: integer;
begin
  Result := nil;
  with FCalculator do
  for i:=0 to FuncTable.Count-1 do
    if TFuncItem(FuncTable.Items[i]).FuncName = FuncName then
    begin
      Result := TFuncItem(FuncTable.Items[i]).FuncAdress;
      Count := TFuncItem(FuncTable.Items[i]).VarCount;
      if (VarCount = Count) or (Count = -1) then Exit
      else raise ETranslateError.Create(esWrongParamCount + FuncName);
    end;
end;

function TFormulaTranslator.CheckFunctionParams(Params: string): integer;
var
  i,j,l, ParIn, ParOut: integer;
begin
  Result := 0;
  ParIn := 0;
  ParOut := 0;
  i := 1;
  j := 1;
  l := length(Params);
  while i <= l do
  begin
    if Params[i] = '(' then Inc(ParIn);
    if Params[i] = ')' then Inc(ParOut);
    if ((Params[i] = ',') and (ParIn = ParOut)) or (i=l) then
    begin
      GetExpression(Copy(Params, j, i-j+integer(i=l)), otComposer);
      inc(Result);
      j := i+1;
    end;
    inc(i);
  end;
end;


function TCalculator.Calculate(FormulaList: TList): Double;
var Data: PStackData;
    i: integer;
    Operand1, Operand2, SubResult: Double;
begin
  SubResult := 0;
  Result := 0;
  if FormulaList.Count = 0 then Exit;
  for i:=0 to FormulaList.Count-1 do
  begin
    Data := PStackData(FormulaList.Items[i]);
    if Data^.DataType = stOperator then
    begin
      Operand2 := FStack.pop;
      Operand1 := FStack.pop;
      case Data^.Operation of
        soAdd: SubResult := Operand1 + Operand2;
        soSub: SubResult := Operand1 - Operand2;
        soMul: SubResult := Operand1 * Operand2;
        soDiv: if Operand2 <> 0 then
          SubResult := Operand1 / Operand2 else
          SubResult := 0;
      end;
      FStack.push( SubResult );
    end
    else
    begin
      SubResult := 0;
      try
        SubResult := GetValue(Data);
      finally
        FStack.Push(SubResult);
        //AddErrorMessage('?????? ??????? ??????: '+TDataItem(GlobalCalc.DataItemStack.Current).CalcItem.Caption);
      end;
    end;
  end;
  Result := FStack.pop;
end;
0
 
LVL 27

Expert Comment

by:kretzschmar
Comment Utility
0
 
LVL 27

Expert Comment

by:kretzschmar
Comment Utility
my favourite is available at
http://delphi.icm.edu.pl/ftp/d10free/parser10.zip
(link above doesn't work)
0
 

Author Comment

by:blasse
Comment Utility
Scrapdog, yes only boolean expressions.

In a expression like this:

(x > y * (z + 1))

the class should raise the
OnCheckExpression(Token1, Operator,
  Token2: String; var IsTrue: Boolean);
once with parameters:
Token1 = x;
Operator = '>';
Token2 = y * (z + 1);

//evaluate x > y * (z + 1);  you will send
// "x", ">", and "y * (z + 1)" to the event handler).

0
 

Expert Comment

by:comptebidon81
Comment Utility
If I understand right, you want to build a function that analyzes a string and give as a result a boolean of the evaluation of the string?

A recursive function would do well here.
You would first need a loop in this function that tries to find the operand by priority ('(', '=', '<'...shouldn't be that hard). Then call your recursive function two times, one for each part. And it will go on like this until you come back to the first recursive function that will finish with something like Result := MyFunc(String) < MyFunc(String) .

It's gonna make a preaty big function, but it should run fast anyway.

Hope I went in the right direction...
GunDamn
0
 
LVL 6

Expert Comment

by:edey
Comment Utility
Just out of curiosity, why not use the scripting control?

GL
Mike
0
 
LVL 5

Accepted Solution

by:
scrapdog earned 300 total points
Comment Utility


Here is an algorithm that you can use.  This may not be the best, but it should work.


First of it, it will be a lot simpler if you have *two* event handlers...one for evaulating boolean expressions (like the one you described above), and one for evaluating other expressions (such as 2 + 2).  This will make it easier for YOU to parse the expression, AND it will remove the burden of further parsing by the user.

Therefore, an "operator" in this context is defined as any legal operator, not just relational operators.



First, we will convert the expression to postfix.

1.  Create a stack that holds operators (the operator stack).
2.  Create a linked list to hold tokens (we'll call this the output stream).
2.  Parse the expression from left to right:
     
     If the current token is:

     An identifier or constant:    Add it to the output stream
     An opening parenthesis '(':   Place it on the top of the operator stack
     A closing parenthesis ')':    
                          Pop the stack and add the popped value to the output stream.
                          Repeat until you encounter the matching '('.  Both parentheses
                          are discarded.

     An operator:
                          a.  If the stack is empty, or a '(' is on the top, place the operator
                              on the top of the stack.
                                      b.  If the top of the stack is an operator:
                                 1.  If the current operator is of greater priority than the one
                                  on the stack, then push the current operator on to the
                                  top of the stack
                                                2.  If not, then pop the operator of the stack and add it to the
                                  output stream.
                              3.  Jump back to step A and repeat until the current operator can
                                  be placed on the top of the stack


Now, the "output stream" contains the expression in postfix (Reverse Polish Notation).


To evaluate the postfix expression:

1.  Start at the beginning of the list, and iterate from left to right
2.  Whenever you encounter an operator:
     If the operator is a relational operator:
         
          Pass the node at i-2 (the left operand), the node at i-1 (the right operand), and the operator to
          your event handler.  Remove all three of the nodes, and replace it with a single node containing the
          result (TRUE or FALSE)

     If the operator is not relational (i.e., the result isn't boolean):

          Pass the node at i-2 (the left operand), the node at i-1 (the right operand), and the operator to
          another event handler that evaluates non-boolean expressions.  Remove all three of the nodes, and
          replace it with a single node containing the result (some number)

     If the operator is a logical operator:

          Evaluate using the node at i-2 (the left operand), and the node at i-1 (the right operand), and the
          operator.  Remove all three of the nodes, and replace it with a single node containing the result you
          evaluated internally (TRUE or FALSE)

3.  By the time you get to the end of the list, you should have one operator (at the end) and two operands (at i-2 and i-1) left.  This should
    be evaluated the same way as in step 2, but the result of this evaluation is your final result.

                                 

This should work for any expression, not just boolean expressions.  If you want to enforce a rule in which only boolean expressions are allowed, simply check to see whether the final result is a valid boolean value (TRUE or FALSE)    
0
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 
LVL 5

Expert Comment

by:scrapdog
Comment Utility
Please forgive E-E for mangling my formatting!
0
 
LVL 5

Expert Comment

by:scrapdog
Comment Utility
It might be easier to ride if you cut and paste it into notepad, etc.
0
 
LVL 5

Expert Comment

by:scrapdog
Comment Utility
ride = read
0
 

Author Comment

by:blasse
Comment Utility
Ok, now I'm all lost :/

I don't know what pop, stack, operator, "linked list to hold tokens" and many more things is?

Sorry, my english is very bad...

Maybe you could give me a basic code sample? =)
0
 
LVL 6

Expert Comment

by:zebada
Comment Utility
The source code for a simple expression parser/evaluator that I write can be downloaded at

http://www.blacky.co.nz/free/expr.zip

It can parse and evaluate expressions like these:

1+2*3+4
(1+2)*(3+4)

x+y
x+123

Func(arg1,arg2...argn)
Func1(Func2(Funcn(arg1,arg2,...,argn)))

"string1"+"string2"
"String1"+1234

The developer is required to supply "call back" functions to supply values for variables (x,y etc) and to evaluate functions. Variables can be of type string or numeric, functions can have multiple string and numeric args, and may return string or numeric. Functions may be nested.

It may help, it may not.
Cheers
Paul

0
 
LVL 6

Expert Comment

by:zebada
Comment Utility
It would be a trivial exercise to implement the comparison operators: <, <=, =, >= and >.

You'd need to define true=1 and false=0 and then just check the result of an expression for 0=true or 1=false.

I could modify the code if this is waht you would need to get your solution.

Cheers
Paul

0
 

Author Comment

by:blasse
Comment Utility
After a couple of hours decoding your high-tech english
i managed to get it working! Thank you for all your help!
0
 
LVL 5

Expert Comment

by:scrapdog
Comment Utility
That's great!  Sorry for sounding so "high-tech";  I made a few assumptions on what you would comprehend.  Thanks for the generous amount of points.
0

Featured Post

Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

Join & Write a Comment

Objective: - This article will help user in how to convert their numeric value become words. How to use 1. You can copy this code in your Unit as function 2. than you can perform your function by type this code The Code   (CODE) The Im…
Introduction The parallel port is a very commonly known port, it was widely used to connect a printer to the PC, if you look at the back of your computer, for those who don't have newer computers, there will be a port with 25 pins and a small print…
Here's a very brief overview of the methods PRTG Network Monitor (https://www.paessler.com/prtg) offers for monitoring bandwidth, to help you decide which methods you´d like to investigate in more detail.  The methods are covered in more detail in o…
This video explains how to create simple products associated to Magento configurable product and offers fast way of their generation with Store Manager for Magento tool.

772 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now