VBA to convert a logical text string into a list of permutations

[gchilde1]

I am a reasonably experienced VBA Excel programmer, but this has got me stumped.
A text file contains strings of code such as the following:-
(Code#1/Code#2)+(Code#3/Code#4)

Where + = AND, / = OR

I am trying to write a piece of VBA code that can convert this into possible permutations of the logic in the statement.
The example above would need to return 4 possible lines.
Code#1 Code#3
Code#1 Code#4
Code#2 Code#3
Code#2 Code#4

The text string can come many configurations, including with nested brackets.

Code#1+((Code#2+Code#3)/Code#4)

Which would return 2 possible permutations...
Code#1 Code#2 Code#3
Code#1 Code#4

Any ideas?

 

[wideboydixon]

Hmm. Complex problem indeed. Are you looking for a minimal set of conditions and is this boolean logic or something else? Does Code#1/Code#2 mean "either but not both"?

I think the parentheses are going to necessitate some kind of recursive function. Definitely tricky!

WBD

 

[gchilde1]

I would be looking for the minimal set of conditions. The individual lines that I see as the output will be used as a boolean logic check.
Code#1/Code#2 means either but not both.
It's that parentheses that makes it difficult. I cant quite work out the rule set that a recursive algorithm would perform based on (, ), + and /.
Thanks for you reply, any ideas gratefully received.

GC

 

[wideboydixon]

Trying to visualise this, I keep thinking about creating then traversing a tree. An "AND" condition would add a new node underneath the existing one and an "OR" condition would branch into two. Having constructed the tree you could then find all the possible ways of traversing it.

Like this:

--+CODE#1--+CODE#3
  |        |
  |        +CODE#4
  |
  +CODE#2--+CODE#3
           |
           +CODE#4

Or this:

---CODE#1--+CODE#2---CODE#3
           |
           +CODE#4

WBD

 

[gchilde1]

I agree that looks like a good way to visualise the problem. It's just how to deal with the parentheses.

 

[pgc01]

Hi

Just to see if I understand, what would you say that are the permutations for

a/b+c/d

 

[oldbrewer]

I am a reasonably experienced VBA Excel programmer, but this has got me stumped.
A text file contains strings of code such as the following:-
(Code#1/Code#2)+(Code#3/Code#4)
Where + = AND, / = OR
I am trying to write a piece of VBA code that can convert this into possible permutations of the logic in the statement.
The example above would need to return 4 possible lines.
Code#1 Code#3
Code#1 Code#4
Code#2 Code#3
Code#2 Code#4
The text string can come many configurations, including with nested brackets.
Code#1+((Code#2+Code#3)/Code#4)
Which would return 2 possible permutations...
Code#1 Code#2 Code#3
Code#1 Code#4
Any ideas?
Code#1+((Code#2+Code#3)/Code#4)	if starts with (( strip off ( from front and ) from end
Code#1+(Code#2+Code#3)/Code#4
look for the / and separate
Code#1+(Code#2+Code#3)
Code#4
remove brackets
Code#1+Code#2+Code#3
Code#4
change "+" to " "
Code#1 Code#2 Code#3
Code#4
if it gets ever more cpmplicated I too am stumped

<colgroup><col><col span="7"></colgroup><tbody>
</tbody>

 

[mikerickson]

I would appoch it this way

You have a set of Values. (True, False)
You have a set of "variables" (a, b, c, ....) (note lower case), each of which is a string
You have a set of "operators" (+, *) (for this discussion), each of which is a string
You also have the two characters ( and )

You have a function that will return the Value associated with each variable.
And you have a function that will return the Value associated with each combination (operator, variable, variable) Note that this function takes booleans as arguments, not variables.

You have rules that define a "well formed formula" (wff)

1) if a is a variable, then the string "a" (no quote marks) is a wff
2) If X and Y are wff's and ~ is an operator then "(X~Y)" (no quote marks) is a wff

Given a wff, return the value represented.
In this code, the operators are single characters, but the variables can be any length.
Note that if a wff is not a single variable, it must be enclosed in parenthesis.

Dim myVariables As Variant
Dim VariableValues As Variant
Dim myOperators As Variant

Sub test()
    myOperators = "+*"
    myVariables = Array("a", "b", "c", "d", "ax")
    VariableValues = Array(True, True, False, False, False)
    
    MsgBox EvaluateWFF("((b+a)*a)")
End Sub

Function EvaluateWFF(ByVal aWFF As String)
    Dim innerFormula As String
    Dim ParenCount As Long
    Dim SubWFF1 As String, PrimaryOperator As String, SubWFF2 As String
    Dim i As Long
    
    If Not aWFF Like "(*)" Then
        Rem single variable
        EvaluateWFF = EvaluateVariable(aWFF)
    Else
        innerFormula = Mid(Left(aWFF, Len(aWFF) - 1), 2): Rem remove outer paren

        For i = 1 To Len(innerFormula)
            If ParenCount = 0 Then

                If InStr(1, myOperators, Mid(innerFormula, i, 1)) <> 0 Then
                    Rem primary operator is found
                    SubWFF1 = Left(innerFormula, i - 1)
                    PrimaryOperator = Mid(innerFormula, i, 1)
                    SubWFF2 = Mid(Replace(innerFormula, SubWFF1, vbNullString, 1, 1), 2)
                    
                    'MsgBox SubWFF1 & ":" & PrimaryOperator & ":" & SubWFF2
                    
                    EvaluateWFF = EvaluateOperation(PrimaryOperator, EvaluateWFF(SubWFF1), EvaluateWFF(SubWFF2))
                    Exit For
                End If
            End If

            ParenCount = ParenCount + (Mid(innerFormula, i, 1) = ")")
            ParenCount = ParenCount - (Mid(innerFormula, i, 1) = "(")
        Next i
    
    End If
End Function

Function EvaluateVariable(aVar As String) As Boolean
    Dim i As Long
    For i = LBound(myVariables) To UBound(myVariables)
        If myVariables(i) = aVar Then
            EvaluateVariable = VariableValues(i)
            Exit For
        End If
    Next i
End Function

Function EvaluateOperation(Operator As String, aVal As Boolean, bVal As Boolean) As Boolean
    Select Case Operator
        Case "+"
            EvaluateOperation = aVal Or bVal
        Case "*"
            EvaluateOperation = aVal And bVal
    End Select
End Function

 

[gchilde1]

a/b+c/d in this case would give the permutations:-

a c
a d
b c
b d

 

[pgc01]

Hi

Just some ideas, trying to help thinking about the problem

First, I must say that I found very strange this

Where + = AND, / = OR

I've always see the boolean operations in algebric notation with:

* (or x) = AND, + = OR

AND-Multiplication, OR-Sum

This means that you can use the usual properties of the operations (comutative, associative, distributive) when manipulating it as an algebraic expression


In fact, using this notation your 2 equations:

(a+b)*(c+d)
a*((b*c)+d)

Using the usual properties and getting rid of the parenthesis you get:

a*c + a*d + b*c + b*d

a*b*c + a*d

What you seem to want is simply each of the summands.

Is this correct?


If this is correct, the way I'd do it is to

1- Convert your expression to the usual algebraic expression equivalent
2- get rid of parentheses using the known properties (associative, distributive)
3- get the summands


This is very simple to understand, we are used to manipulating polynomial like expressions.
The part that is more work to code is the getting rid of the parentheses.

I started thinking about this (just for fun, it's an interesting problem).
If you think this makes sense I can try to do some more work on this.

Does this make sense to you?