Boolean string processing

[Kdev]

I am working on making a program less specific and more generic. This program loads pictures based on configuration options in a database for each order. These pictures are chosen by a whole series of boolean control statements (if, then, and, or, not) and is currently hard-coded to the application to specific configuration names and pictures.

I have extracted all of the information to a local database for the options and which pictures to load. However to save on time and space I am sticking with the method of picking and choosing the pictures rather than just select every possible combination (3000+). What I have devised is a database that matches field names with field names in the source database. However each of these fields are boolean strings instead of just single options.

For Example:

MDL SHC File
91,98 (V,W);(X,Y) 98 Picture Left.bmp



How this database entry should be read is equivalent to the following:

if (MDL = "91" OR MDL = "98") AND (SHC = "V" OR SHC = "W") AND (SHC = "X" OR SHC = "Y") then
DrawPicture 98 Picture Left.bmp



What I am attempting to do then is write some sort of function to process the boolean algebra as I have shown. I would appreciate any suggestions and or sample code on how to go about processing such boolean statements since I cannot (as far as I know) "build" the exact boolean statement for VB to process.

I was thinking about setting up flags to check if it should be AND vs. OR which I think is the easy part but handling the parentheses may be a bit more difficult.

Thanks in advance for any help.

-K

[shree]

>but handling the parentheses may be a bit more difficult.

Evaluating expressions becomes much simple when they are in postfix notation. For example,
(V,W);(X,Y) is written as V W , X Y , ;

If the database cannot be modified to contain the options in postfix, you can write a subroutine to convert infix to postfix.

[coolbiz]

This is a good logic puzzle to be playing with. If you already have some code written, maybe you can email it to me or post it up and then we can give you some idea from there. Anyway, it is complicated to do so but 2 heads (more than 1 at least) is better than 1 right?

-Cool Bizs

[Kdev]

Temporary solution for now:

I process the strings by iterating over the text and changing the ',' to OR and the ';' to AND and the '!' to NOT as well as evaluate if an item say '91' is a match = to 1.

In sum, I process the string so that something like this:

(91,93,98);(LH,LB);(F5);(L)

looks like this:

(True OR False OR False) AND (False OR False) AND (False) AND (True)

Then I write out a small vbscript file to the extent:

If (true OR false OR false) AND (false OR false) AND (false) AND (true) then
...write out 1 to a text file
else
...write out 0 to a text file
End If



So my program is just replacing the variables in the boolean string with True,False and then executing a script so that I can test the statement and writing the result to a text file that I then read with my program.

This is only a temporary solution until I can write an algorithm to process the boolean strings. I am having 1 problem with this program: speed. I know that this ought to be slower but I was wondering if I am running this script in the fastest method possible.

I am executing the script like this:

Dim wshShell
set wshShell = CreateObject("WScript.Shell")
wshShell.Run "wscript tmp001.vbs", 0, true



This will run the script and wait until finished before continuing.

The script file looks like this:

Dim objFS
Dim objFile
Dim objTS


If ( true OR false) AND ( false OR false OR false) AND ( false OR false) AND ( true) then
set objFS = CreateObject("Scripting.FileSystemObject")
set objFile = objFS.GetFile("c:\temp\output.txt")
set objTS = objFile.OpenAsTextStream(2)
objTS.WriteLine ("1")
objTS.Close
set objFS = nothing
else
set objFS = CreateObject("Scripting.FileSystemObject")
set objFile = objFS.GetFile("c:\temp\output.txt")
set objTS = objFile.OpenAsTextStream(2)
objTS.WriteLine ("0")
objTS.Close
set objFS = nothing
End If



Is there anyway I can clean this up to make it run a bit faster for now?

-K

[Kdev]

Ok I finally came up with an algorithm to process boolean strings. Thought of this on my commute home

'======================================================================
'This function takes a string of the form (1,0);(0,0,0),!(1,0)
'Where 1 means true, 0 means false, "," means OR, ";" means AND, "!"
'means NOT; parentheses are acceptible and if any parens do not match
'up this function will add the appropriate amount to either the
'beginning or the end of the string; it will evaluate the string and
'return true or false.
'======================================================================
private Function EvalBoolString(InString as string) as Boolean
Dim nLparens as Integer, nRparens as Integer
Dim sBool as string, sSub as string, sOper as string
Dim nLValue as Integer, nRValue as Integer
Dim nRpos as Integer, nLpos as Integer, nNpos as Integer

sBool = InString

nLpos = InStr(sBool, "(")
While nLpos <> 0
nLparens = nLparens + 1
nLpos = InStr(nLpos + 1, sBool, "(")
Wend

nRpos = InStr(sBool, ")")
While nRpos <> 0
nRparens = nRparens + 1
nRpos = InStr(nRpos + 1, sBool, ")")
Wend

If nLparens < nRparens then
While nLparens < nRparens
nLparens = nLparens + 1
sBool = "(" & sBool
Wend
ElseIf nRparens < nLparens then
While nRparens < nLparens
nRparens = nRparens + 1
sBool = sBool & ")"
Wend
End If

sBool = "(" & sBool & ")"

nRpos = InStr(sBool, ")")
While nRpos <> 0
nLpos = InStrRev(sBool, "(")
While nLpos > nRpos
nLpos = InStrRev(sBool, "(", nLpos - 1)
Wend

sSub = mid(sBool, nLpos + 1, nRpos - nLpos - 1)

nNpos = InStr(sSub, "!")
While nNpos <> 0
sSub = IIf(mid(sSub, nNpos + 1, 1) = "1", _
Left(sSub, nNpos - 1) & "0" & mid(sSub, nNpos + 2), _
Left(sSub, nNpos - 1) & "1" & mid(sSub, nNpos + 2))
nNpos = InStr(sSub, "!")
Wend

While len(sSub) > 1
nLValue = Left(sSub, 1)
sOper = mid(sSub, 2, 1)
nRValue = mid(sSub, 3, 1)

If sOper = "," then
sSub = IIf(nLValue = "1" Or nRValue = "1", "1" & mid(sSub, 4), "0" & mid(sSub, 4))
ElseIf sOper = ";" then
sSub = IIf(nLValue = "1" And nRValue = "1", "1" & mid(sSub, 4), "0" & mid(sSub, 4))
else
sSub = "0" & mid(sSub, 4)
End If
Wend

sBool = Left(sBool, nLpos - 1) & sSub & Right(sBool, len(sBool) - nRpos)
nRpos = InStr(sBool, ")")
Wend

If Left(sBool, 1) = "1" then
EvalBoolString = true
else
EvalBoolString = false
End If
End Function



-K

[nolanvenhola]

postfix has it's flaws though...
try doing something like this in postfix:
(1 AND (true OR false) OR true)

causes problems...

I had to write an algebra equation (containing regular arithmatic expressions, as well as boolean expressions) evaluator, and I came up with several rather complicated recursive sub routines. All I'm saying is that it's not a quick task.