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 Vucenic:
#
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/26081/fid/585
#
# 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 Vucenic:
Hi Timo,
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
)