Hi Wayne & Harpo,

thanks a lot for your suggestions. This is really an interesting

solution. It took me some time to get the conversion from infix

going. I ended up converting infix->postfix->binary tree. Code of my

findings is below. There’s certainly a lot to be improved there. Any

obvious mistakes of a ruby-newbie in there?

While working on the code, I came across some strange behaviour of

the Set class of the ruby standard library:

class TestSet < Test::Unit::TestCase

def test_set

array=[[“a”, “b”], [“a”, “c”], [“d”]]

array_of_sets=array.map{|an_array| an_array.to_set}

set_of_sets=array_of_sets.to_set

contained_set=[“a”,“b”].to_set

# OK

assert_equal(true, array_of_sets.include?(contained_set))

# fails

assert_equal(true, set_of_sets.include?(contained_set))

end

end

The second assertion fails. Is this intended behaviour?

Thanks again fpr your great suggestions!

Timo

#
andx and orx implementation by Wayne V.:

#
Helpful docs for infix/prefix/postfix/binary tree conversions

#
Known Limitations:

#
infix_to_*fix: code doesn’t handle operator priorities

#
postfix_to_tree: code doesn’t handle unary operators

#
no error handling

require ‘set’

class ArrayOfCombinations

OPERATORS=[“and”,“or”]

SPLIT_REGEX=/((|)|and|or)/

attr_reader :combinations

def initialize(infix_str)

@combinations = ArrayOfCombinations.expand infix_str

@all_sets = @combinations.map{|an_array| an_array.to_set}

end

def remaining_choices_for(choices)

choices = choices.to_set if choices.is_a?(Array)

remaining_sets = @all_sets.find_all{|a_set|

choices.proper_subset?(a_set)}

remaining_sets.to_set.flatten-choices

end

def complete_for?(choices)

choices = choices.to_set if choices.is_a?(Array)

@all_sets.include? choices

end

def self.andx(a,b)

ret = []

a.each do |some_a|

b.each do |some_b|

ret << some_a + some_b

end

end

ret

end

def self.orx(a,b)

a.collect {|some_a| some_a } + b.collect {|some_b| some_b}

end

private

def self.split_input(input)

elements=input.gsub(" “,”").split(SPLIT_REGEX)

elements.delete “”

elements

end

#
infix_to_prefix currently not used

def self.infix_to_prefix(infix_str)

stack, output = [], []

elements=split_input(infix_str)

elements.reverse!

elements.each do |element|

if element==“)”

stack.push element

elsif OPERATORS.include?(element)

stack.push element

elsif element==“(”

while (operator=stack.pop) != “)”

output << operator

end

else

output << element

end

end

while not stack.empty?

output << stack.pop

end

output.reverse!

end

def self.infix_to_postfix(infix_str)

stack, output = [], []

elements=split_input(infix_str)

elements.each do |element|

if element==“(”

stack.push element

elsif OPERATORS.include?(element)

stack.push element

elsif element==“)”

while (operator=stack.pop) != “(”

output << operator

end

else

output << element

end

end

while not stack.empty?

output << stack.pop

end

output

end

class BinTreeNode

attr_accessor :value, :left, :right

```
def initialize(value=nil, left=nil, right=nil)
@value, @left, @right = value, left, right
end
def inspect
return value+"x("+left.inspect+","+right.inspect+")" if left !
```

= nil and right != nil

return “[['”+value+“']]”

end

end

def self.postfix_to_tree(postfix_array)

stack = []

postfix_array.each do |element|

if OPERATORS.include?(element)

right, left = stack.pop, stack.pop

stack.push BinTreeNode.new(element,left,right)

else

stack.push BinTreeNode.new(element,nil,nil)

end

end

stack.first

end

def self.expand(infix_str)

postfix=infix_to_postfix(infix_str)

tree=postfix_to_tree(postfix)

eval tree.inspect

end

end

require ‘test/unit’

class TestArrayOfCombinations < Test::Unit::TestCase

def test_andx_orx

assert_equal([[:a,:b]], ArrayOfCombinations.andx([[:a]], [[:b]]))

assert_equal([[:a,:b,:c]], ArrayOfCombinations.andx([[:a]],

[[:b, :c]]))

assert_equal([[:a,:b], [:a,:c]], ArrayOfCombinations.andx

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

```
assert_equal([[:a], [:b]], ArrayOfCombinations.orx([[:a]], [[:b]]))
assert_equal([[:a],[:b,:c]], ArrayOfCombinations.orx([[:a]],
```

[[:b, :c]]))

```
# Try the test case from the RubyTalk posting
assert_equal([["a", "b"], ["a", "c"], ["d"]],
ArrayOfCombinations.orx(ArrayOfCombinations.andx
```

([[‘a’]],

ArrayOfCombinations.orx([[‘b’]], [[‘c’]])),

[[‘d’]]))

end

def test_expand

output = ArrayOfCombinations.new(“(a and (b or c) ) or

d”).combinations

assert_equal([[“a”, “b”], [“a”, “c”], [“d”]],output)

end

def test_complete_for

aoc = ArrayOfCombinations.new(“(a and (b or c) ) or d”)

assert_equal(false, aoc.complete_for?([]))

assert_equal(false, aoc.complete_for?([“a”]))

assert_equal(true, aoc.complete_for?([“a”,“b”]))

assert_equal(true, aoc.complete_for?([“d”]))

end

def test_remaining_choices

input = “(a and (b or c) ) or d”

aoc = ArrayOfCombinations.new(input)

assert_equal([“a”,“b”,“c”,“d”].to_set, aoc.remaining_choices_for

([]))

assert_equal([“d”,“b”,“c”,“a”].to_set, aoc.remaining_choices_for

([]))

assert_equal([“b”,“c”].to_set, aoc.remaining_choices_for([“a”]))

assert_equal([].to_set, aoc.remaining_choices_for([“d”]))

end

end

Am 07.12.2005 um 23:50 schrieb Wayne V.: