```Hi Timo,

On 12/7/05, Timo Hoepfner <th-dev / onlinehome.de> wrote:
> I'm looking for an easy way to convert a string representing a
> boolean expression like
>
> "(a and (b or c) ) or d"
>
> to an Array of Arrays (representing sets) representing all possible
> valid combinations like:
>
> [["a","b"],["a","c"],["d"]]

First, we write a method that converts the input string from infix to
prefix notation and that also puts [[ ]] around all the arguments (to
simplify later processing).  I didn't actually do this step, but it shouldn't be
too hard.  So this method will convert "(a and (b or c) ) or d" into

orx(andx([['a']],
orx([['b']], [['c']])),
[['d']]))

I find it's best to use Test Driven Development to solve problems like
defining orx and andx.  The resulting solution below converts the above
expression into [["a", "b"], ["a", "c"], ["d"]]

Thanks for the interesting problem!

Wayne

---
Wayne Vucenic
No Bugs Software
"Ruby and C++ Contract Programming in Silicon Valley"

def andx(a,b)
ret = []
a.each do |some_a|
b.each do |some_b|
ret << some_a + some_b
end
end
ret
end

def orx(a,b)
a.collect {|some_a| some_a } + b.collect {|some_b| some_b}
end

require 'test/unit'

class TestArrayOfCombinations < Test::Unit::TestCase
def test_one
assert_equal([[:a,:b]], andx([[:a]], [[:b]]))
assert_equal([[:a,:b,:c]], andx([[:a]], [[:b, :c]]))
assert_equal([[:a,:b], [:a,:c]], andx([[:a]], [[:b], [:c]]))

assert_equal([[:a], [:b]], orx([[:a]], [[:b]]))
assert_equal([[:a],[:b,:c]], orx([[:a]], [[:b, :c]]))

# Try the test case from the RubyTalk posting
assert_equal([["a", "b"], ["a", "c"], ["d"]],
orx(andx([['a']],
orx([['b']], [['c']])),
[['d']]))
end
end

```