Solved

evaluating brackets

Posted on 2001-07-25
5
486 Views
Last Modified: 2010-04-06
Does anyone have code or an algorithm to evaluate brackets for macthematical expressions. I can get the conditions, but am heaving trouble working out there relationship to each other

E.g,

IF (((X=Y) AND (A=B)) OR (C=D)) THEN blah blah blah

Can't quite get my head around it! I've gone "bracket blind" i've been staring at it for so long.

I've marked the question as hard coz I can't find anyone who has done this. I guess if you've done it before it'll pretty simple.

Cheers,

Mark.
0
Comment
Question by:sparkido
5 Comments
 
LVL 27

Expert Comment

by:kretzschmar
ID: 6316807
0
 

Author Comment

by:sparkido
ID: 6316985
Thanks for thin link, but the code seems to be geared towards evaluating mathematical equations. I guess I can now refine my question ...

I don't actually want to evaluate the expression, as the conditions themselves aren't "real" mathematical conditions, and themselves need to be resolved. I really want to extract the conditions from the brackets, and determine the relationship between them. I'm more interested in the structure of the expression, rather than evaluating it automatically.

I'll keep looking though...
0
 
LVL 9

Expert Comment

by:ITugay
ID: 6317109
Hi sparkido,

I'm not sure, but may be my unit will be usefull for you.

-----
Igor.

unit O2_parse;
//-----------------------------------------------------------------------------------------------------------------------------
//
//   Copyright (c) Igor Tugay , 2001
//
//-----------------------------------------------------------------------------------------------------------------------------
//
//   Unit has class that allow to parse recursive text construction
//   Sample:
//          struc=(
//             column=(width=100, color=(R=255, G=255, B=240), caption = "(c)"),
//             column=(width=120, color=(255, 255, 240), caption = "(c)")
//          )
//
//   Result:
//   O2Expr.Value = "struct"
//       List[0].Value = column
//          List[0].Value = width
//          List[0].Data = 100
//          List[1].Value = color
//              List[0].Value = R
//              List[0].Data = 255
//              ...
//          List[2].Value = "caption"
//          List[2].Data = "(C)"
//       List[1].Value = column
//       .....
//
//-----------------------------------------------------------------------------------------------------------------------------
interface

uses
  windows, classes, sysutils, contnrs;

type
  TO2Expr = class(TObjectList)
  private
    FValue: String;
    FData: String;
    FList: TO2Expr; // if FList is nil then FData has Data
                    // otherwise FList has list of enclosed data
    function GetItem(Index: Integer): TO2Expr;
  public
    constructor Create;
    destructor Destroy; override;

    // I should be 1 for top level expression
    //  ...Parse('some data = (v=10)', 1)
    function Parse(const S: String; I: Integer): Integer;
    function GetByValue(const S: String): TO2Expr;

    // X - number of spaces to show current level indent
    procedure Show(L: TStrings; X: Integer);

    property Value: String read FValue;
    property Data: String read FData;
    property List: TO2Expr read FList;
    property Items[Index: Integer]: TO2Expr read GetItem; default;
  end;

implementation

//-----------------------------------------------------------------------------------------------------------------------------

function GetTextConst(const S: String; var I: Integer): String;
var L: Integer;
begin
  Result := '';
  inc(I);
  L := Length(S);
  while (I <= L) and (S[I] <> '"') do
  begin
    Result := Result + S[I];
    inc(I);
  end;
  Result := '"'+Result + '"';
  inc(I);
end;

//-----------------------------------------------------------------------------------------------------------------------------

procedure SkipCtlChar(const S:String; var I: Integer);
var L: Integer;
begin
  L := Length(S);
  while (I<=L) and (S[I] <= ' ') do inc(I);
end;

//----------------- TO2Expr ---------------------------------------------------------------------------------------------------

constructor TO2Expr.Create;
begin
  inherited;
end;

//-----------------------------------------------------------------------------------------------------------------------------

destructor TO2Expr.Destroy;
begin
  List.Free;
  inherited;
end;

//-----------------------------------------------------------------------------------------------------------------------------

function TO2Expr.GetItem(Index: Integer): TO2Expr;
begin
  Result := TO2Expr(Inherited Items[Index]);
end;

//-----------------------------------------------------------------------------------------------------------------------------

function TO2Expr.GetByValue(const S: String): TO2Expr;
var
  I: Integer;
begin
  Result := nil;
  for I := 0 to Count-1 do
    if CompareText(Trim(S), Trim(Items[I].Value)) = 0 then
    begin
      Result := Items[I];
      Break;
    end;
end;

//-----------------------------------------------------------------------------------------------------------------------------

function TO2Expr.Parse(const S: String; I: Integer): Integer;
var
  L: Integer;
  T: TO2Expr;
begin                        
  L := Length(S);
  while (I <= L) and (S[I] <> ')') do
  begin
    T := TO2Expr.Create;

    SkipCtlChar(S, I);
    while (I<=L) and (S[I] <> '=') and (S[I] <> ',') and (S[I] <> ')') do
    begin
      T.FValue := T.FValue+S[I];
      inc(I);
    end;
    T.FValue := Trim(T.FValue);

    if (I <= L) and (S[I] <> ',') and (S[I] <> ')') then
    begin
      inc(I);
      SkipCtlChar(S, I);
      if (I <= L) and (S[I] = '(') then
      begin
        inc(I);
        T.FList := TO2Expr.Create;
        I := T.List.Parse(S, I);
      end else
      while (I<=L) and (S[I] <> ',') and (S[I] <> ')') do
      begin
        if S[I] = '"' then
          T.FData := T.FData+GetTextConst(S, I) else
        begin
          T.FData := T.FData+S[I];
          inc(I);
        end;
      end;

      SkipCtlChar(S, I);
    end;

    while (I<=L) and (S[I] = ',') do Inc(I);

    T.FData := Trim(T.FData);
    Add(T);
  end;
  if (I<=L) and (S[I] = ')') then inc(I);

  Result := I;
end;

//-----------------------------------------------------------------------------------------------------------------------------

procedure TO2Expr.Show(L: TStrings; X: Integer);
var
  S: String;
  I: Integer;
  T: TO2Expr;
begin
  S := '';
  for I := 1 to X-1 do S:=S+' ';
  for I := 0 to Count-1 do
  begin
    T := TO2Expr(Items[I]);
    if T.List = nil then
      L.Add(S+T.Value+' = '+T.Data)
    else begin
      L.Add(S+T.Value+' = (');
      T.List.Show(L, X+3);
      L.Add(S+' )');
    end;
  end;
end;


end.
0
 
LVL 2

Accepted Solution

by:
FrodoBeggins earned 200 total points
ID: 6317821
Basicaly I would put the expresion in a tree. The tree gives you the posibility of using parent-chld(s) relations just as the brackets. The result is on the root of the tree, and you should start evaluating it with the deepest leaves.
Of course that could be done brutely, but with a structure like a tree is so... nice ;-). Afterwards you can combine expresions, evaluate them partialy and so on. Maybe I'll try to write one such parser, if noone else gives you correct answer.

Rgds,
Frodo
0
 

Author Comment

by:sparkido
ID: 6326063
Cheers for that. Took me a while to work this out, but the theory runs that :

Call a function create a new treenode.
Get all characters from the string until you hit an open bracket.
Now recusively call the function and create a new treenode and continue processing.

When you get a close bracket you add the contents to the node.
If your brackets match up, this will eventually unwind itself back to root.
I think it's important to point out that evaluating brackets should be a two step process. Gather the data, then process it. Probably not wise (if not impossible) to do both at the same time.

You start at the deepest node and evaluate each node working back towards root. Evaluating all nodes at each level, and a parent node combines the results of it's children. This means that when you get to root, the answer of the condition in root is the answer for the entire bracket.

Thanks very much for your help.

Mark.
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

A lot of questions regard threads in Delphi.   One of the more specific questions is how to show progress of the thread.   Updating a progressbar from inside a thread is a mistake. A solution to this would be to send a synchronized message to the…
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…
This Micro Tutorial will give you a basic overview how to record your screen with Microsoft Expression Encoder. This program is still free and open for the public to download. This will be demonstrated using Microsoft Expression Encoder 4.
Windows 10 is mostly good. However the one thing that annoys me is how many clicks you have to do to dial a VPN connection. You have to go to settings from the start menu, (2 clicks), Network and Internet (1 click), Click VPN (another click) then fi…

911 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

17 Experts available now in Live!

Get 1:1 Help Now