# Re: Bracket Packing (#78)

**URL:** <https://www.ruby-forum.com/t/re-bracket-packing-78/59964>\
**Category:** Ruby\
**Created:** [May 9, 2006, 1:24am UTC](https://www.ruby-forum.com/t/re-bracket-packing-78/59964 "2006-05-09T01:24:03Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![stuart\_holden](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/7993a0/32.png) [@stuart\_holden](https://www.ruby-forum.com/u/stuart_holden)\
**Post date:** [May 9, 2006, 1:24am UTC](https://www.ruby-forum.com/t/re-bracket-packing-78/59964/1 "2006-05-09T01:24:03Z")

</div>

Here is my attempt. Go easy… my first quiz entry, and my first Ruby  
script.

Regards,  
Stu

* * *

class Packaging  
attr\_accessor :opening, :closing, :description

def initialize (o,c,desc)  
@opening = o  
@closing = c  
@description = desc  
end

def opp(v)  
(v==@opening) ? @closing: @opening  
end

def opening?(v)  
@opening==v  
end

def closing?(v)  
@closing==v  
end

def consistsOf?(v)  
opening?(v) || closing?(v)  
end  
end

class PackagingPreProcessor  
attr\_accessor :packagingTypes

def initialize()  
@types=[]  
end

def addPackaging(p)  
@types \<\< p  
end

def opening?(c)  
@types.detect { |p| p.opening?(c) }  
end

def closing?(c)  
@types.detect { |p| p.closing?(c) }  
end

def getPackagingType(c)  
@types.detect { |p| p.consistsOf?(c) }  
end

def processMessage(msg)  
msg.final = msg.original  
openStack=[]

```
aMsg=msg.original.split(//)

#Scan character by character for unbalanced brackets
aMsg.each_with_index do |c,i|

  # Push opening packaging type onto the stack
  if opening?(c)
    type=getPackagingType(c)
    openStack.push(type)
  end

  # Ensure closing brackets match the last opening bracket
  if closing?(c)

    currentPackagingTag=getPackagingType(c)

    expectedPackaging=openStack.pop

    if (expectedPackaging==nil)
      # We weren't expecting a close tag here.
      #
      # Eg, {(B)(B)}]
      # ^---- We a missing an opener for this
      #

      msg.final=currentPackagingTag.opening + msg.original
      return
    end

    if (currentPackagingTag != expectedPackaging)
      #
      # We have run into the wrong closing position,
      #
      # Two cases:
      # We failed to open this position, eg : [B)], in which

```

case we will have a mismatch of ‘current’ brackets  
# or  
# There had been a subsequent position opened that needs  
to be closed first - eg, [{B] - mismatch of expected brackets  
#

```
      if (aMsg.select { |c| expectedPackaging.consistsOf?(c)

```

}.length % 2 != 0)  
# need to insert the end braket of the expected packaging  
msg.final=msg.original[0…(i-1)] + expectedPackaging.closing

- msg.original[i…-1]  
return  
else  
# Insert an opening bracket to match the current closing  
bracket.  
msg.final = msg.original[0…(i-1)] +  
currentPackagingTag.opening + msg.original[i…-1]  
return  
end  
end  
end  
end

class Message  
attr\_reader :original  
attr\_accessor :final

def initialize(msg)  
@original = msg  
end

def valid?  
@original==@final  
end  
end

#--------------------------

ppp=PackagingPreProcessor.new()

ppp.addPackaging(Packaging.new(“(”,“)”,“Soft Wrapping”))  
ppp.addPackaging(Packaging.new(“[”,“]”,“Cardboard Box”))  
ppp.addPackaging(Packaging.new(“{”,“}”,“Wooden Box”))

ARGF.each do |line|  
msg=Message.new(line.chomp)  
ppp.processMessage(msg)  
print “\n”  
print(msg.final)  
print “\n”  
end

> This Email may contain confidential and privileged information and is intended for the use of the addressee(s) only. If you are not the intended recipient please notify the sender and delete the Email from your system. It should not be transmitted to any other person without the consent of the sender. Additional important notifications regarding Email transmissions from and to members of Baring Asset Management can be accessed at [http://www.barings.com/email/index.hcst](http://www.barings.com/email/index.hcst)

&nbsp;

---

<div class="post-metadata">

**Author:** ![stuart\_holden](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/7993a0/32.png) [@stuart\_holden](https://www.ruby-forum.com/u/stuart_holden)\
**Post date:** [May 9, 2006, 1:26pm UTC](https://www.ruby-forum.com/t/re-bracket-packing-78/59964/2 "2006-05-09T13:26:40Z")

</div>

🙂 This is great 🙂 I enjoyed doing the quiz, and tried out a couple of  
approaches: the stack based one (which seemed much more complex, and  
even then didn’t cover all the cases), and this substitution on. Solving  
the quiz was fun, but I picked up a lot of little things I didn’t know  
along the way (either by bumping in to them, or looking at other  
people’s solutions):

The pattern match variables $` and $’.  
That you can use any start and end charater to deliminate a %w array  
literal (or any of the related literals).  
Having a test case in a script.  
That the ruby command can be given params for the script itself.

Thank you community 🙂

Cheers,  
Benjohn

module SubValidator  
module\_function

def is\_valid(s)  
validate(s) rescue nil  
end

def validate(s)  
# Replace basic brackets in (valid) packaging, with packages.  
s = s.gsub(/(B)|{B}|[B]/, ‘P’)

```
# Until the string is reduced to a single package...
while(s!='P')
  # Replace one of more packages in (valid) packing, with a single

```

package.  
s, old\_s = s.gsub(/(P+)|{P+}|[P+]/, ‘P’), s

```
  raise "Couldn't find any packages to package in '#{s}'." if 

```

s==old\_s  
end  
true  
end  
end

require ‘test/unit’

class BracketTest \< Test::Unit::TestCase  
def test\_validators  
[SubValidator].each {|v| check\_validator(v)}  
end

def check\_validator( validator )  
# Simple cases that should pass.  
valid\_strings = %w\<(B) {B} [B] ((B)) {(B)} ([{B}]) ((B)(B))  
((((B)(B))(B))(B))\>  
valid\_strings.each do |s|  
assert\_nothing\_raised { validator.validate(s) }  
end

```
# Simple cases that should fail.
invalid_strings = %w<() (b) [B [B [} [B} } {{{{[B]}}} {{{{[B}}}

```

((B)B)\> \<\< ‘’  
invalid\_strings.each do |s|  
assert\_raises(RuntimeError) { validator.validate(s) }  
end

```
# Try out a complex string - it should validate.
ok = "[({B}[B](B)[(B){[B][(B)]}]{B}{B})((B))]"
assert_nothing_raised{ validator.validate ok }

# Try dropping any of the chars - it should fail to vaildate.
ok.scan(/./) { assert_raises(RuntimeError) { validator.validate( $`

```

- $’ ) } }

validate.  
%w\<B ( ) { } []\>.each do |c|  
ok.scan(//) { assert\_raises(RuntimeError) { validator.validate( $`

- c + $’ ) } }  
end  
end

if **FILE** == $0  
if( ARGV[0] != ‘-t’ )  
Test::Unit.run = false  
exit( SubValidator::is\_valid( ARGV[0] ) ? 0 : 1 )  
else  
ARGV.pop  
end  
end

---

<div class="post-metadata">

**Author:** ![stuart\_holden](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/7993a0/32.png) [@stuart\_holden](https://www.ruby-forum.com/u/stuart_holden)\
**Post date:** [May 9, 2006, 2:20pm UTC](https://www.ruby-forum.com/t/re-bracket-packing-78/59964/3 "2006-05-09T14:20:16Z")

</div>

I’ve done a little refactor because I didn’t like the inline regular  
expressions.

🙂 Which makes me think that it’d be nice to have some extra methods in  
Regexp that let you customise the special characters that it uses,  
perhaps.

module SubValidator  
module\_function

def is\_valid(s)  
validate(s) rescue nil  
end

def validate(s)  
# Replace basic brackets in (valid) packaging, with packages.  
s = s.gsub( packages\_containing(‘B’), ‘P’ )

```
# Until the string is reduced to a single package...
while(s!='P')
  # Replace one of more packages in (valid) packing, with a single

```

package.  
s, old\_s = s.gsub( packages\_containing(‘P+’), ‘P’ ), s

```
  raise "Couldn't find any packages to package in '#{s}'." if 

```

s==old\_s  
end  
true  
end

def packages\_containing(filler\_pattern)  
Regexp.new( packings.map {|p| Regexp.escape§.gsub(‘x’,  
filler\_pattern)}.join(’|’) )  
end

def packings  
%w\<(x) {x} [x]\>  
end  
end

require ‘test/unit’

class BracketTest \< Test::Unit::TestCase  
def test\_validators  
[SubValidator].each {|v| check\_validator(v)}  
end

def check\_validator( validator )  
# Simple cases that should pass.  
valid\_strings = %w\<(B) {B} [B] ((B)) {(B)} ([{B}]) ((B)(B))  
((((B)(B))(B))(B))\>  
valid\_strings.each do |s|  
assert\_nothing\_raised { validator.validate(s) }  
end

```
# Simple cases that should fail.
invalid_strings = %w<() (b) [B [B [} [B} } {{{{[B]}}} {{{{[B}}}

```

((B)B)\> \<\< ‘’  
invalid\_strings.each do |s|  
assert\_raises(RuntimeError) { validator.validate(s) }  
end

```
# Try out a complex string - it should validate.
ok = "[({B}[B](B)[(B){[B][(B)]}]{B}{B})((B))]"
assert_nothing_raised{ validator.validate ok }

# Try dropping any of the chars - it should fail to vaildate.
ok.scan(/./) { assert_raises(RuntimeError) { validator.validate( $`

```

- $’ ) } }

validate.  
%w\<B ( ) { } []\>.each do |c|  
ok.scan(//) { assert\_raises(RuntimeError) { validator.validate( $`

- c + $’ ) } }  
end  
end

if **FILE** == $0  
if( ARGV[0] != ‘-t’ )  
Test::Unit.run = false  
exit( SubValidator::is\_valid( ARGV[0] ) ? 0 : 1 )  
else  
ARGV.pop  
end  
end