boolean logic parser - need help

  • Thread starter Thread starter Mad Scientist Jr
  • Start date Start date
M

Mad Scientist Jr

Has anyone worked on code that that can parse evaluation expressions
(could be numbers or strings) like

( ( "dog" = "dog" ) or "foo" = "bar" ) and ("cow" = "bat" and "bye" =
"hi") or ("math" = "fun")

or

( ( 1 = 5 ) or ( 2 < 3 ) ) and (1 <= 6)

or (here it gets a little complicated with math expressions)

( ( 1 = ((5*2)+1) ) or ( 2 < 3 ) ) and (1 <= 6)

?

I have a compare functions to evaluate <, <=, =, !=, >=, > for strings
and numbers, and a math parser, and all the values would be literal. I
am looking either to figure out how to do it, or find existing code
that would work.

I am not sure recursion is correct to do this, or how to put it all
together, parsing out the "AND"s and "OR"s, and keeping track of the
parenthesis hierarchy (while ignoring math expressions which also have
parenthesis) in the correct order of precedence, and ultimately
returning a single boolean value for the entire thing.

Here is some pseudocode I put together to work it out - any help would
be appreciated.

EVALUATE A BOOLEAN EXPRESSION IN A STRING
AND RETURN TRUE OR FALSE:
if odd # of parens (not part of quoted string) return error
if quotes, string mode, else math mode
has parens?
yes: analyze further
iPosNextEnd = next closing parens
find closing parens by adding +1 evertime an open paren
(not part of quoted text) found, -1 every time a closed
paren found. when parencount back to 0 we know we have
reached the end of the current paren block.
between iStart and iPosNextEnd
look inside (outside of quotes)
for comparison operator
yes? break down further
no? found value.
if math mode
send contents to math parser to evaluate
use string value as is
no: evaluate
look inside (outside of quotes)
for AND/OR
if 1 AND/OR
evaluate left side vs right side
else MULTIPLE AND/ORs (see below):
look for all ANDs, all ORs, store position in list (OPERATOR, VAL
1, VAL 2, RESULT)
traverse list and evaluate
evaluate ANDs, store result
evaluate ORs, store result

MULTIPLE AND/OR WITHOUT PARENS:
it seems expressions with "and" are evaluated first.
take a statement like:
If T1 = 1 And T2 = 2 Or T3 = 3 Then

T1 T2 T3 Evaluates to
-- -- -- ------------
1 2 3 true
1 2 4 true
1 5 4 false
1 5 3 true

PS I found some Java code on a Deutch site that looks like it might be
similar to what I need to do. I know vb.net not Java, and the comments
aren't in English, so I don't really understand all it is doing, but I
see it is using some kind of lists or tokens (what's a token?) to keep
track of things. Can anyone convert this to .NET without too much
trouble?

http://www.brian-schroeder.de/parser/
 
You can try http://babelfish.altavista.com to translate the German to
English (or whatever other language you'd prefer), try it, it's quite good.

As for what tokens are, in java speak, a token is a part of something. If
for instance you have a string "abc,def,ghi" (comma-seperated), you can use
what Java calls a StringTokenizer to break the string up into it's parts (or
tokens). It is similar to string.Split, which returns an array, the
StringTokenizer however returns a collection which you can iterate through
using methods like NextToken().
 
No, sorry, I don't.

What I can suggest is write psuedo code for the java and then try to write
VB from that. If you have problems understanding any of the java logic,
please feel free to ask! (I know this isn't a java newsgroup, but I'm sure
nobody would mind...)
 
Found it !

The Microsoft Script Control has an Eval function.
http://www.devx.com/vb2themax/Tip/18773

It works like a charm ... it even compares string expressions. All you
have to do is parse your expression for your variable names and drop in
the values (if strings drop in quoted values).

Does anyone know of a native .NET version?
 
Back
Top