Wayne Vucenic
12/7/2005 10:51:00 PM
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