Boolean expression evaluation routine required

I think it was Railgunner who suggested that the OP break up parentheses into a set of individual IF statements, which sounds brilliant.

My first guess would be to keep a constant copy of the original string, so that it never gets changed. Then I would look for the innermost set of parentheses (i.e. find '(' until there are none left), get the portion of the string from this '(' to the next ')', and evaluate it. Inside each set of ()s, you'd have to check for ANDs, ORs, etc. individually.

You could somehow find out how many evaluations you would need to perform and declare a bool array of that size. For instance, if I was evaluating IF (A == B), I only need 1 evaluation - if I was evaluating IF (A < B || B == C), I would need 3 evaluations (One for A < B, one for B == C, and one for the || in the middle). As you figure out different parts of the original, you can set the corresponding element to TRUE or FALSE.

These are all just ideas, though - not sure how easy/hard it would be to implement.

Break the expression into a binary tree, with each boolean operator being a node, and each constant/expression becoming a leaf. Then use a recursive approach to determine the boolean status of the expression.

I think it was Railgunner who suggested that the OP break up parentheses into a set of individual IF statements, which sounds brilliant.

Well, I'm trying to avoid doing this. Problem is, say you have

000001 IF (A=1 AND B=1) OR (C=1 AND D=1)
000002 Do something
000003 END-IF

Yes, I could convert the OR into an ELSE-IF like this...

000001 IF A=1 AND B=1
000002 Do something
000003 ELSE-IF C=1 and D=1
000004 Do something
000005 END-IF

But I end up repeating 'Do something' and if 'Do something' is 10 more levels
of nested IFs this gets nasty and explodes the size of the resulting "object" code.

I'm wondering is there any "standard" most efficient routine for evaluating
boolean expressions. I'm thinking there's probably some kind of reverse polish notation for boolean logic? If so, I could modify the compiler to translate
the parens into an equivalent RPN expression at compile time and the
processor to simply evaluate this expression from left to right at runtime?
I just can't get my head around how you could evaluate a boolean expression in RPN from left to right and still be able to short-circuit and avoid evaluating
the entire expression before determining if the overall result is true or false.

Using a binary tree data structure will allow you to handle the entire system recursively.

Does this make sense?

Then you can implement short-circuit evaluation and recursion in the determining each node.

Using a binary tree data structure will allow you to handle the entire system recursively.

Expand|Select|Wrap|Line Numbers

1. (A && B) || C
2.  
3. becomes
4.  
5.       ||
6.      /  \
7.    &&    C
8.   /  \
9.  A    B
10.  

Does this make sense?

Then you can implement short-circuit evaluation and recursion in the determining each node.

kinda... but I was looking for someone who had a canned routine or knew where I could find one. I could probably write one, but it might take me two months to do it. I don't want to recreate the wheel if I don't have to.

kinda... but I was looking for someone who had a canned routine or knew where I could find one. I could probably write one, but it might take me two months to do it. I don't want to recreate the wheel if I don't have to.

Sometimes you can find this sort of potted algorithm on Wikipedia, sometimes with samples in various languages. I just tried to have a look there for boolean logic, but it was blocked as an "entertainment" site. Go figure.

kinda... but I was looking for someone who had a canned routine or knew where I could find one. I could probably write one, but it might take me two months to do it. I don't want to recreate the wheel if I don't have to.

Well this method should be quite straight forward; a node can be defined in two ways: either a boolean operator and two nodes, or a constant/variable.
To evaluate() a node of the first type, you perform the evaluate function on both child nodes, and then perform the boolean operation on the result.
To evaluate() a node of the second type, you return the value of that node.

short pseudocode:

Alternatively, you could look at existing systems called Computer Algebra Systems, and a list of CAS's can be found here. These seem like they would be a little bit overkill, though.

Well, spent the last few nights looking for an algorithm and have not found anything. I'm not sure I even know the terminology of what I'm looking for.
Finding plenty of stuff on infix to postfix but it's all for mathematical expressions.
A few posts I found hinted that you could somehow convert boolean expressions
into some kind of postfix form but finding info about this is difficult because
it's mixed in with all the stuff about evaluating mathematical expressions.
I get the feeling I'm missing some "key word" in searching for what I'm looking for.

Just to restate the problem... I need a routine that will evaluate
boolean expressions like:

IF (X=1 AND (B=1 OR C=D))

IF X=1 OR (C>1 AND D<2)

where I determine if the individual terms are true or false (X=1 is TRUE or FALSE), etc. and the routine determines if the entire expression is true of false taking into account the parentheses.

The "perfect" routine would accept the expression as a string...

E$ = "IF (X=1 AND (B=1 OR C=D))"

and contain a point where I can branch to my code that determines the truth of the individual terms (X=1, etc) as required.

I'm guessing the routine will contain two parts...

a. Some kind of front end parsing of the expression where the expression
is checked for mismatched parens, and perhaps reformated into somekind
of postfix boolean expression.

b. The actual evaluation where given the true/false state of the terms,
the routine determines if the entire expression is true/false.

c. Routine should contain logic to short-circuit once the entire expression is
known to be true or false.

Surely there's some grad student out there who needs some pocket money
that knows where to find such a routine or can write one?

$500.00 to a paypal account of your choice for the 1st person to post a working routine with comments explaining what the code is doing... Don't care what language it's developed in as long as it's translated to BASIC before I get it.

$500.00 to a paypal account of your choice for the 1st person to post a working routine with comments explaining what the code is doing... Don't care what language it's developed in as long as it's translated to BASIC before I get it.

O.O

dang. I should do that, if I didn't feel grossly underqualified. Plus, no clue how to do BASIC.

As a more formal sidenote, if you are offering pay, you may want to post this in the Jobs/Contract Work section. Don't know if mmccarthy will deem that appropriate.

BASIC?
As in the DOS crap language of yesteryear? Or do you mean Visual Basic? Or something else?
Yikes.

O.O

dang. I should do that, if I didn't feel grossly underqualified. Plus, no clue how to do BASIC.

As a more formal sidenote, if you are offering pay, you may want to post this in the Jobs/Contract Work section. Don't know if mmccarthy will deem that appropriate.

As a job it should be in the jobs forum. But no suggestions regarding code will be posted there so I would suggest continuing original thread to try to find an answer on thescripts and post a job ad also to see if someone wishes to take the job on.

Mary

BASIC?
As in the DOS crap language of yesteryear? Or do you mean Visual Basic? Or something else?

Just for fun, we should do it in Applesoft BASIC. :D

BASIC?
As in the DOS crap language of yesteryear? Or do you mean Visual Basic? Or something else?
Yikes.

VB would be fine. I can handle rewriting that to run on the crap mainframe of yesteryear:)

It's just, I thought this was going to be written with a 4GL. BASIC is not a 4GL.
It severely lacks the structures and support that a higher level language can provide.

VB would be fine. I can handle rewriting that to run on the crap mainframe of yesteryear:)

Hey, no mainframe-bashing in this forum, please.

It's just, I thought this was going to be written with a 4GL. BASIC is not a 4GL.
It severely lacks the structures and support that a higher level language can provide.

The 4GL this would be rewritten in is really nothing more than a COBOL
generator so BASIC would actually be a pretty close. GOSUBS translated to
PERFORMS, etc.

They say the highest level language would only have one statement... generate program. It would always work but you could never get it to do what you want...

Hey, no mainframe-bashing in this forum, please.

The biggest secret in IT is... Mainframes still rule the world:)

Are you going to be using strings to make value assignments as well? Or are your variables going to actually be variables in the code?

If the former, what you are actually trying to do is create a new language; in which case, you need to build BNF for your new language. Once you have your language in BNF, you will be able to make a proper request for help.

If the latter is your goal, this is simply undoable in any language which does not have dynamic typing, does not load variables at runtime, or is not interpreted at runtime..

What language are you actually using. You have been quite vague on this matter, and at this point, I think it really does matter.

What language are you actually using. You have been quite vague on this matter, and at this point, I think it really does matter.

It's been said a few times that the final solution needs to be in BASIC.

"BASIC would actually be pretty close" != "We are using BASIC":

The 4GL this would be rewritten in is really nothing more than a COBOL
generator so BASIC would actually be a pretty close. GOSUBS translated to
PERFORMS, etc.

Are you going to be using strings to make value assignments as well? Or are your variables going to actually be variables in the code?

If the former, what you are actually trying to do is create a new language; in which case, you need to build BNF for your new language. Once you have your language in BNF, you will be able to make a proper request for help.

If the latter is your goal, this is simply undoable in any language which does not have dynamic typing, does not load variables at runtime, or is not interpreted at runtime..

What language are you actually using. You have been quite vague on this matter, and at this point, I think it really does matter.

Yes, I need this for a new language. The language is already developed, it just does not support parentheses in boolean expressions. If you try and code them you get a compile error.

Users currently get around this by just coding ELSE-IFs and nested IFs.

Example 1:

IF X=1 OR (Y=1 AND Z=1)
Do something
END-IF

Ends up being coded as:

IF X=1
Do Something
ELSE-IF Y=1 AND Z=1
Do Something
END-IF

Example 2:

IF X=1 AND (Y=1 OR Z=1)
Do Something
END-IF

Would end up being coded as:

IF X=1
IF Y=1 OR Z=1
Do Something
END-IF
END-IF

The language is not put into BNF before it's executed. What "executes" is not
machine code. The language is actually "executed" by a program. This program (we call it the "processor") acts like a virtual machine in a sense. The language is "compiled" but the resulting "object" code really looks pretty much like the source code except that branch addresses are added so that it so that the processor "knows" where to branch to when a condition is false. This allows
the processor to "skip" through the code as it's executed.

Yes the variables are actually variables in the code but this is already working.
The language supports field to literal, and field to field evaluations, substring
checks, SUM, COUNT, MIN, MAX, AVG, direct references to specific occurences in passed lists or direct references to specific occurences, etc.

I think I may have solved my problem today... I can simply translate the
parentheses into ELSE-IF's and nested IFs and evaluate the overall
result once the translated expression is evaluated.

For example:

IF (X=1 AND (Y=1 OR Z=1)) OR Q=1 would get translated as follows...

1st pass:

IF X=1 AND (Y=1 OR Z=1)
TRUE
ELSE-IF Q=1
TRUE
END-IF

2nd pass:

IF X=1
IF Y=1 OR Z=1
TRUE
END-IF
ELSE-IF Q=1
TRUE
END-IF

At this point the existing processor can execute the code.

"BASIC would actually be pretty close" != "We are using BASIC":

Sorry, I had made that logical jump; guess you didn't (and were right).

The language we developed does of course have a syntax. We have not
explicitly put it into BNF format. Have not had any reason to.

It's really pretty simple. It does not do any file I/O or computations. It's pretty much nothing but IF/ELSE-IF conditions that act on variables passed at runtime and the only thing it does when conditions are true is returns values to the calling application that requested it's execution. It's probably closer to something like a subset of SQL that a full blown programming language.

And what are we doing with the "Do somethings?"

"Do something" can be moving literals to fields that are returned to the calling application when the program has completed execution, setting user defined boolean flags true/false that are referenced in subsequent IF/ELSE-IF conditions, or escaping.

Just imagine a black box, you call it passing the name of a "program" and a list of field names and values. The box fetches the program in-core or finds it already loaded in-core, executes it, and returns back a list of field names and values.

The language is simple because it's designed for end-users (non-programmers). It can't go into a loop and it can't ABEND. About the worst thing it can do is return a runtime error if the calling application passes character data in a field that's defined as numeric. Passed and returned field names and data types are defined on reference tables when the program is initially defined. The "compiler" checks these reference tables at compile time to make sure the user does not return character data in a numeric field, compare a passed numeric field to a character literal, etc.

The returned field definitions can be tied to a group of values. In other words, if you allow the user to return back a field named SEX, you can actually specify that the only values the user can return in that field is 'M' or 'F'.

Sounds like what I would call a scripting language.

Good luck finding a programmer to try and implement that for $500 :D

I read this thread with quite a bit of interest; I've written some compilers and
interpreters for quite a few languages. A few remarks:

1) do you want that 'if else' syntactic sugar in your language? "if A then B else C"
can be written as "(A && B) || (!A && C)" where both A, B and Care boolean
expressions. Note that "if A then B" is not a valid boolean expression, i.e. what
would the value of the expression be if A == false?

2) the relational operator < implies that operands have a PTO (Partial Total
Ordering). Do you mean false < true or do both operands have a numerical
value? If so that complicates your interpreter quite a bit because type checking
has to be performed, either at compile time or runtime.

3) do you need assignments in your language or are all variables 'predefined'?
Either explicitly by some API or implicitly during runtime where the variable is
assumed to have some default value. On top of that, do you want your variables
to be declared before they can be assigned to? If so your semantic analyzer
needs to check for redefinitions.

4) what would the value of the entire 'program' be? The value of the last
expression or what?

5) do you want only first order Boolean logic or do you want predicate logic
as well?

I think a whole lot of these issues need to be properly defined first before you
can write an interpreter for your language.

kind regards,

Jos

I read this thread with quite a bit of interest; I've written some compilers and
interpreters for quite a few languages. A few remarks:

1) do you want that 'if else' syntactic sugar in your language? "if A then B else C"
can be written as "(A && B) || (!A && C)" where both A, B and Care boolean
expressions. Note that "if A then B" is not a valid boolean expression, i.e. what
would the value of the expression be if A == false?

2) the relational operator < implies that operands have a PTO (Partial Total
Ordering). Do you mean false < true or do both operands have a numerical
value? If so that complicates your interpreter quite a bit because type checking
has to be performed, either at compile time or runtime.

3) do you need assignments in your language or are all variables 'predefined'?
Either explicitly by some API or implicitly during runtime where the variable is
assumed to have some default value. On top of that, do you want your variables
to be declared before they can be assigned to? If so your semantic analyzer
needs to check for redefinitions.

4) what would the value of the entire 'program' be? The value of the last
expression or what?

5) do you want only first order Boolean logic or do you want predicate logic
as well?

I think a whole lot of these issues need to be properly defined first before you
can write an interpreter for your language.

kind regards,

Jos

I'll try and answer as best I can...

1. Don't think I understand the question here...

2. Field names types are predefined as either character or numeric.
An expression like:

IF X=1
Do Something
END-IF

would not compile if X is predefined as numeric and you coded:

IF X='CAT'
Do Something
END-IF

I tag the field name in the object as numeric and at runtime if X does not
contain a numeric value then I return a runtime error. Type checking occurs
at compile in that the compiler won't let you compare a numeric field to
a character literal or a numeric field to a character field. Type checking also
occurs at runtime when the processor finds character data in a field
tagged as numeric in the object code.

3. Think I answered this in #2.

4. When the processor executes a program in this language, the processor
can return back multiple values so there's no single result.

For example, if the processor executes the following program/script, the returned field named MYVAL can contain 0-3 values. Remember the
processor is a called program. You pass it field names and values
and it returns field names and values. All passed (and returned) fields are actually lists in that they can contain one or more values.

IF X=1 AND Z=1
RETURN MYVAL = 'AAA'
ELSE-IF Q=1
ESCAPE
END-IF

IF B=1
RETURN MYVAL = 'BBB'
END-IF

IF C=1
TRUE MYFLAG
END-IF

IF MYFLAG IS TRUE
RETURN MYVAL = 'CCC'
END-IF

5. Don't understand the question. Currently, the processor executes expressions as follows...

Expressions are evaluated left to right. Expressions are initially considered
to be FALSE.

If the processor is evaluating...

IF X=1 AND Y=1 AND Z=1

X=1 is evaluated 1st... Say the result is TRUE. The state of the expression
is now TRUE.

Processor now encounters AND Y=1. ANDs are only be evaluated if the
current state of the expression is TRUE. In other words, an AND can change
a TRUE expression to FALSE but it's not evaluated when the expression is already FALSE. In this case the expression is true so Y=1 is evaluated. Say the result is FALSE. Processor now encounters AND Z=1. This is not
evaluated because an AND can not turn a false expression TRUE.
The expression has now been fully evaluated and the state is FALSE.
Processor now branches to the next executable statement at the same
nest level (ELSE-IF, etc).

When the processor evaluates ORs it's the opposite of ANDs. OR's are only
evaluated when the expression is FALSE. In other words, and OR can
change a false expression to TRUE but is not evaluated when the expression
is already TRUE.

IF you were to code something like this...

IF X=1 OR Y=1 AND Z=1

and X=1 is TRUE, Y=1 is FALSE, Z=1 is FALSE then the expression will
be considered FALSE.

explanation...

Processor determines X=1 is TRUE
Y=1 is not evaluated because expression is already TRUE and OR's
are not evaluated when expression is TRUE.
Z=1 is evaluated because ANDs are evaluated when the expression is TRUE
and since Z=1 is false, this changes the expression to FALSE.
End result, expression is FALSE.

I think I've figured out what I really need is a routine that will
translate an expression containing parentheses into the same expression stated as IF/ELSE-IF/NESTED IF

For example:

IF (Z=1 AND (B=1 OR C=1)) OR Q=1
RETURN MYFLD = 'X'
END-IF

into:

IF Z=1
IF B=1 OR C=1
RETURN MYFLD = 'X'
END-IF
ELSE-IF Q=1
RETURN MYFLD = 'X'
END-IF

Actually, I would probably then translate this into:

INTERNAL-FLAG IS FALSE /* INSERTED BY COMPILER
IF Z=1
IF B=1 OR C=1
TRUE INTERNAL-FLAG
END-IF
ELSE-IF Q=1
TRUE INTERNAL-FLAG
END-IF
IF INTERNAL-FLAG IS TRUE /* INSERTED BY COMPILER
RETURN MYFLD='X'
END-IF

The logic above can be execute by the existing processor with no changes.

The processor keeps a table of TRUE/FALSE states per level
of nesting. Example... here you have 3 levels of indentation.
IF Y=1 IS FALSE then the 2 level is FALSE. When the processor
encounters X=1 at lvl 3 it is not evaluated because the previous level
is FALSE. Soon as the processor sees this it will branch to next
executable instruction. Note: These branch addresses/offsets are inserted
by the compiler at compile time.

IF X=1
IF Y=1
IF X=1
Do Something
END-IF
END-IF
END-IF

So I guess my real question is... Does anyone know where I can find a routine
that will translate an expression containing parentheses into equivalent
IF/ELSE logic?

However this turns out, I'm glad I broke it out of the VB forum - we seem to be attracting a fair bit of interest over here. I hope it helps.

@Railgunner: you don't just want a boolean expression evaluator, you want
most of a BASIC interpreter. Here are some more remarks:

1) the IF <expression> THEN <statement> END-IF construct is not a boolean
expression, it's a statement. It seems to me that you also want to evaluate
statements then.

2) if variables have a predefined type (string, numeric, boolean), does your
language define them itself, e.g. as in: If so, you need a type checking system in your interpreter (what you call:
"processor"). You can do that either statically (during the compilation phase)
or dynamically (during runtime). I'd suggest the static type checking because
it shows programming errors in an early stage.

3) You also need arithmetic evaluation if you allow for expressions and operators
such as: 4) Are assignments to considered expressions too (as in C, C++, Java)?
If you don't want any assignments at all you can't have variable declarations in
your language (see 2).

5) Do you want to do type-coercion, i.e. is the boolean value false/true to be
considered 0/1? If so, the following snippet will be semantically valid for a
numerical variable: What do you want to do if X happens to be a string? Is any non-zero value of X
considered to be equivalent to 'true'. If so you don't need a boolean type at all.

kind regards,

Jos

@Railgunner: you don't just want a boolean expression evaluator, you want most of a BASIC interpreter. Here are some more remarks:

1) the IF <expression> THEN <statement> END-IF construct is not a boolean
expression, it's a statement. It seems to me that you also want to evaluate
statements then.

>> This would be correct

2) if variables have a predefined type (string, numeric, boolean), does your
language define them itself, e.g. as in:

Expand|Select|Wrap|Line Numbers

1. String x, y;
2. Number z;
3. Boolean b;

If so, you need a type checking system in your interpreter (what you call:
"processor"). You can do that either statically (during the compilation phase)
or dynamically (during runtime). I'd suggest the static type checking because
it shows programming errors in an early stage.

>> The language does not define it's own variables except boolean variables
>> but these are defined when they are initially set TRUE/FALSE
>> Type checking is done during compile phase but not based on the language
>> defining the types. The types are predefined on a DB2 table and the
>> compiler uses this table to do type checking at compile time.

3) You also need arithmetic evaluation if you allow for expressions and operators
such as:

Expand|Select|Wrap|Line Numbers

1. IF (x+y) < (40+2) THEN
2. <do something>
3. END-IF

>> Don't have this currently. These kind of expressions would be
>> considered computations and the language does not support
>> computations. In the case above, the calling program would have
>> to do the x+y computation and pass the result in a variable z.
>> Would be nice to have but it's not currently supported.

4) Are assignments to considered expressions too (as in C, C++, Java)?
If you don't want any assignments at all you can't have variable declarations in
your language (see 2).

5) Do you want to do type-coercion, i.e. is the boolean value false/true to be
considered 0/1? If so, the following snippet will be semantically valid for a
numerical variable:

Expand|Select|Wrap|Line Numbers

1. IF X THEN
2. <do something>
3. END-IF

>> The statement above would not compile. References to true/false
>> boolean variables must be coded as:

>>IF X IS TRUE
>><do something>
>>END-IF

>>The keyword being 'IS' followed by TRUE/FALSE
>>If X has been defined (typed) as a true/false flag by a previous SET
>>statement e.g. SET X TRUE
>>Then script will compile else you'll get an undefined field name error on X
>>at compile time.

What do you want to do if X happens to be a string? Is any non-zero value of X is considered to be equivalent to 'true'. If so you don't need a boolean type at all.

kind regards,

Jos

See inserted >> comments.

more...

terminology is killing me here... I'm not a compiler expert and have no experience developing computer languages.

But that does not matter in the world I live in, so I developed a language, compiler, and interpreter/processor anyway:)

It works, it's fast, and it's very easy for end-users to learn but keep in mind it was developed by someone with absolutely no background in how something like this would traditionally be developed.

Anyway, I figured that since this language does have a compiler that does
type checking, syntax editing, and which produces "object" code separate from
the source code, that "processor" would be a better term than interpreter, since
the source code has already been "interpreted/translated" into object code
at compile time?

more...

terminology is killing me here... I'm not a compiler expert and have no experience developing computer languages.

But that does not matter in the world I live in, so I developed a language, compiler, and interpreter/processor anyway:)

It works, it's fast, and it's very easy for end-users to learn but keep in mind it was developed by someone with absolutely no background in how something like this would traditionally be developed.

Oh dear, I have to warn the compiler writer police then ;-) no seriously, it must've
been a nice experience to write such a thing and who am I (nor anyone else) to
criticize you on that? I was just wondering what you had in mind exactly (I didn't
know you already wrote such a thing) and that's why I asked all those questions.

Anyway, I figured that since this language does have a compiler that does
type checking, syntax editing, and which produces "object" code separate from
the source code, that "processor" would be a better term than interpreter, since
the source code has already been "interpreted/translated" into object code
at compile time?

A lot of interpreters compile the actual source text to some "intermediate" form
and interpret that. So most interpreters do have a compiler on board. It doesn't
compile to raw machine code instructions, that's all. Only the most primitive
Basic interpreters keep on interpreting the original source code (which is just
text) over and over again which is a waste of time if the source code happens
to be correct.

Have fun writing compilers and interpreters!

kind regards,

Jos

railgunner maybe i have the right solution for you:
written in python
i write a module named work.py
from the shell:

tell me if it is what you needed
best reguards
luke14free

railgunner maybe i have the right solution for you:
written in python
i write a module named work.py
from the shell:

Expand|Select|Wrap|Line Numbers

1. >>> from work import * #import everything from file work.py
2. >>> table={'p':2,'o':2} #table of values
3. >>> string=buildstring('p==o or((p+2)==o') #build a sentence from a string
4. >>> execexpr(a,table) #exe sentence from a string taking values in a table
5. True
6.  

tell me if it is what you needed
best reguards
luke14free

Don't know Python so I have no idea what that code does:)

Don't know Python so I have no idea what that code does:)

wow!
I had an idea; to take the string and then to convert it into a regular exspression...that would make things easier...otherwise i dont know which other system could help you because a string is not a regular expr.
for example:

you get the string "2==2" and you say True...but the var is not True because you got a string and everything inside a string is not executable...
instead if you get 2==2 or 3==3 you have an expr. but you can't work on it, because is not a string! and you can work just with strings...(e.g you cant split 2==2 or 3==3 into an array such as {2==2, or , 3==3}); and that's because i could not understand the tree of motoma!
so there is no possibility to work on expressions...--->use string but there are a lot of problem with string, for example the priority of the operations...you should codes very very long...

for the code, yes its written in python but i maybe i can traslate it in vbasic, however the code is very much commented(and it isnt even a page) and python is very easy!...
tell me what to do!

PS: motoma could you tell me hoe does the tree works with expressions or strings? thanks!

...for the code, yes its written in python but i maybe i can traslate it in vbasic, however the code is very much commented(and it isnt even a page) and python is very easy!...

Could you post the python code here? I'm sure we'd all be interested to see it.

The system is made of logical operators and operands. We construct a tree with this definition: a node must have one logical operator and two children; each child can be a node or an operand. You then take a string literal, and break it down into this tree structure, by using a simplified RPN algorithm. Once you have built a tree, an implementation of the recursive approach I posted earlier will traverse the tree and determine the truth of each node.

PS: motoma could you tell me hoe does the tree works with expressions or strings? thanks!

You then take a string literal, and break it down into this tree structure, by using a simplified RPN algorithm..

Hmm, only one thing, if you get something like this
a=2

if 'a = 2' is True etcetra...

then you take the string condition that is 'a = 2'...you can split it and you get:
'a','=','2'...for the = there is no problem, you can do a series of if cases and you say if sing= '=' elif sign='<'... and so on.
for the number is very easy because you get the int value from a string..
but now you have to get back from a letter or a word (that in our case is 'a') to a var that is really different from a (without quotes!)
so your expression becames:


and you'll get false... because we aren't talking about the var!

however thanks for the explanation!

Could you post the python code here? I'm sure we'd all be interested to see it.

I have almost finished to translate it in vbasic!! :D
when it will be ready (i think today or tomorrow) i'll post it because the python one is a disater, no one would understand the stupid way in which i code :-)

Hey railgunner code is finished...you wrote that you need to make it run on a 4gl language processor...because of a very difficult code in vb that uses undocumented functions, would you like me to translate it in a 4gl language too(vb code is ready but i think that you wont find anything that could translate a function undocumented!!) such as SheerPower 4GL(that would make things easier for you!)? or would you like to tell me in which language of 4gl and i'll try to do it in that language,,,
waiting for an answer
best regards
Luke14free

code written and tried...now you are able to do everything with it ;) there is a little note: for the vb code..because of i haven't any knowledge of vb5,6 and .net a friend helped me doing that..This is how it works: you write the instruction in the code in the string 'string_to_be_executed' and then when you run the function a msgbox tell you the value of the sentence
and this is the code written in python for python fans and for killer :D
should work on python 2.5!!...

re. luke14free

The language the routine is needed in is called APS. It's a mainframe COBOL
generator:)

Probably easier to just write it in COBOL.

I can't tell what that VB code is doing:)

Here's what I came up with last night... Don't have the code yet, just trying to
figure out what the routine should look like...

Take a statement like:

IF (X=1 AND (Y=1 OR Z=1)) AND (A=1 OR B=1)

parse from left to right...

anytime you find OR followed by a paren "split" the statement
with an ELSE-IF. The part before the paren goes on one side, and
the part in the paren goes on the other. Put any remainder on both sides.

anytime you find AND followed a paren move the part following down to nested
IF.

Ex.

IF (X=1 AND (Y=1 OR Z=1)) AND (A=1 OR B=1)
<Do something>
END-IF

| 1st pass
v

IF X=1
IF (Y=1 OR Z=1) AND (A=1 OR B=1)
<Do Something>
END-IF
END-IF

| 2nd pass
v

IF X=1
IF Y=1 OR Z=1
IF A=1 OR B=1
<Do something>
END-IF
END-IF
END-IF

This would end up getting translated to...

FALSE COMPILER-FLAG /* Inserted by compiler
IF X=1
IF Y=1 OR Z=1
IF A=1 OR B=1
TRUE COMPILER-FLAG
END-IF
END-IF
END-IF
IF COMPILER-FLAG IS TRUE
<Do something>
END-IF

Note... <do something> might be another IF statement containing
parens.

Thinking that AND NOT would get translated to do nothing if the condition
is true ELSE <do something>

This seems like a crazy solution...

Here's another example:

Ex.

IF (X=1 AND Y=1) OR ((A=1 AND B=1) OR C=1
<Do something>
END-IF

| 1st pass
v

IF X=1 AND Y=1
<Do something>
ELSE-IF (A=1 AND B=1) OR C=1
<Do something>
END-IF

| 2nd pass
v

IF X=1 AND Y=1
<Do something>
ELSE-IF A=1 AND B=1
<Do something>
ELSE-IF C=1
<Do something>
END-IF

Still pondering OR/AND trailing a paren...

This would be a cool routine in inself if it worked. Might be useful for
making sense of complex statements by translating them into a more
easy to read format.

...This would be a cool routine in inself if it worked. Might be useful for making sense of complex statements by translating them into a more easy to read format.

That sounds like a worthy goal. I've seen some mighty complex IF statements at times. (Probably guilty of writing some pretty nasty ones, too.)

@Railgunner: if you want to minimize boolean expressions, as in e.g.
(A and B) or ((not A) and B) ---> B have a look at the Quine McCluskey
simplification algorithm.

kind regards,

Jos

seriously i didn't undersstand why is my code wrong...:(
could you repeat it to me?
how ever couldn't you do something like that

IF (A=2 AND (B=3 OR C=4)) OR C=4

now lets split the condition(suppose that we have taken out the if yes so we just have (A=2 AND (B=3 OR C=4)) OR C=4 with the separator '(' and ')' and take out them(just the initual and fianl onem so we get A=2 AND (B=3 OR C=4)-->we take what is in the first ()
now lets do a while that say: continue this procedure until there are no other panens inside our code.in our case we get B=3 OR C=4...lets pass this condition and suppose that you get TRUE

so some it up...(A=2 AND (B=3 OR C=4)) OR C=4-->A=2 AND (B=3 OR C=4)-->B=3 OR C=4-->TRUE

now rewind... we know that the most internal condition is TRUE lets take out the condition and put TRUE in his place...we get
(A=2 AND TRUE) OR C=4

our while cicle sees another parens so(suppose that A is 2):
(A=2 AND TRUE) OR C=4-->A=2 AND TRUE-->TRUE

and so you have:

TRUE OR C=4

you exit from the while because there are no longer parens...

the you just need to pass the C=4 to an IF cicle..
suppose that returns TRUE

TRUE OR TRUE

pass into another IF

TRUE

so thats the routine that i am going to build...do you think that would be finally right?

best regards

Hmm, only one thing, if you get something like this
a=2

if 'a = 2' is True etcetra...

then you take the string condition that is 'a = 2'...you can split it and you get:
'a','=','2'...for the = there is no problem, you can do a series of if cases and you say if sing= '=' elif sign='<'... and so on.
for the number is very easy because you get the int value from a string..
but now you have to get back from a letter or a word (that in our case is 'a') to a var that is really different from a (without quotes!)
so your expression becames:

the word 'a' is equal to 2

and you'll get false... because we aren't talking about the var!

however thanks for the explanation!

This is only a problem if you don't account for it in the language. You would need to create a data structure for holding your variable assignments: a hash table should do quite well for mapping variable names to their values. The function which does the processing on a node wouldn't be a direct mapping of strings to logical operators, rather the booleanop() from my pseudo-code was merely a high level abstraction of the process.

This is only a problem if you don't account for it in the language. You would need to create a data structure for holding your variable assignments: a hash table should do quite well for mapping variable names to their values. The function which does the processing on a node wouldn't be a direct mapping of strings to logical operators, rather the booleanop() from my pseudo-code was merely a high level abstraction of the process.

and you think that this would be done in basic for just 500$? eheh,,,i am not helping railgunner for moneys...but its a quite difficult to do it...i could try to do it in another language such as c python or perl...but in basic is just for people who dont need to reach those levels...correct me if i am wrong, but i think its quite impossible...we should find another solution,isnt it motoba?
however i am valutating the possibility to create a code for hash datas...:)
one question for railgunner: do you sleep an night or you just code?eheh :P