Solved

Expressions / String parsing

Posted on 2001-07-23
16
724 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
ID: 6310670
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
ID: 6311143
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
ID: 6311149
0
Master Your Team's Linux and Cloud Stack!

The average business loses $13.5M per year to ineffective training (per 1,000 employees). Keep ahead of the competition and combine in-person quality with online cost and flexibility by training with Linux Academy.

 
LVL 27

Expert Comment

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

Author Comment

by:blasse
ID: 6311525
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
ID: 6321780
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
ID: 6322229
Just out of curiosity, why not use the scripting control?

GL
Mike
0
 
LVL 5

Accepted Solution

by:
scrapdog earned 300 total points
ID: 6322980


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
 
LVL 5

Expert Comment

by:scrapdog
ID: 6322989
Please forgive E-E for mangling my formatting!
0
 
LVL 5

Expert Comment

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

Expert Comment

by:scrapdog
ID: 6322995
ride = read
0
 

Author Comment

by:blasse
ID: 6324265
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
ID: 6325088
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
ID: 6325092
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
ID: 6325188
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
ID: 6325328
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

DevOps Toolchain Recommendations

Read this Gartner Research Note and discover how your IT organization can automate and optimize DevOps processes using a toolchain architecture.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

The uses clause is one of those things that just tends to grow and grow. Most of the time this is in the main form, as it's from this form that all others are called. If you have a big application (including many forms), the uses clause in the in…
Introduction I have seen many questions in this Delphi topic area where queries in threads are needed or suggested. I know bumped into a similar need. This article will address some of the concepts when dealing with a multithreaded delphi database…
This Micro Tutorial demonstrates using Microsoft Excel pivot tables, how to reverse engineer competitors' marketing strategies through backlinks.
Established in 1997, Technology Architects has become one of the most reputable technology solutions companies in the country. TA have been providing businesses with cost effective state-of-the-art solutions and unparalleled service that is designed…

777 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