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