Hi, 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"]] Background: I want to build a tree structure, where constraints like the one above are attached to the nodes. They describe, which combinations of children are allowed and what valid combinations are left once one or more children are already selected. I'm already doing something like that in Java, but supply the list of possible combinations by hand, which quickly gets annoying... The rest is done via set operations. The actual business logic is similar to (pseude code which looks like Ruby from a Ruby-Newbie's POV...): set=MySet.new [["a","b"],["a","c"],["d"]] set.remaining_choices_for [] --> ["a","b","c","d"] set.remaining_choices_for ["a"] --> ["b","c"] set.remaining_choices_for ["d"] --> [] set.complete_for? ["a"] --> false set.complete_for? ["a","b"] --> true set.complete_for? ["d"] --> true If you can think of a better approach, please tell... Thanks for your help, Timo

on 2005-12-07 14:55

on 2005-12-07 22:45

Timo H. wrote: > Hi, > > I'm looking for an easy way to convert a string representing a > boolean expression like > > "(a and (b or c) or d" Unpaired parentheses ! (I was a compiler in a previous life, I just can't help ;)) > > to an Array of Arrays (representing sets) representing all possible > valid combinations like: > > [["a","b"],["a","c"],["d"]] The question is interesting, my answer is probably a bad hack. Say you use a regular expression to transform the string in "exp([a.xand([b,c]),d]) Maybe it is possible. I think it is. It seems to be a well formed Ruby expression and can be parsed by Ruby using eval, you just have to write the xand mathod ('and' is likely to be a reserved word in a language) end the exp method, maybe the same as xand. This methods can build the array you need. Well, It is just a direction. I thank you for this problem.

on 2005-12-08 00:53

Hi Timo, On 12/7/05, Timo H. <removed_email_address@domain.invalid> 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 V. 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

on 2005-12-09 16:43

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.: # http://article.gmane.org/gmane.comp.lang.ruby.general/126925 # # Helpful docs for infix/prefix/postfix/binary tree conversions # http://www.codepedia.com/1/Art_Expressions_p1 # http://www.faqts.com/knowledge_base/view.phtml/aid... # # 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.:

on 2005-12-09 20:39

```
Timo H.:
> assert_equal(true, set_of_sets.include?(contained_set))
Interesting:
irb> [ 'a', 'b' ].to_set.eql? [ 'a', 'b' ].to_set
=> false
irb> [ 'a', 'b' ].to_set == [ 'a', 'b' ].to_set
=> true
So Set#== and Set#eql? behave differently.
Malte
```