1require 'bundler/inline'
 2
 3gemfile do
 4  source 'https://rubygems.org'
 5
 6  gem 'minitest'
 7end
 8
 9require 'minitest/autorun'
10
11=begin
12A matched string is a sequence of {, }, (, ), [, and ] characters that are properly matched.
13For example, “{{()[]}}” is a matched string, but this “{{()]}” is not, since the second { is matched with a ].
14Show how to use a stack so that, given a string of length n, you can determine if it is a matched string in O(n) time.
15=end
16
17class Example < Minitest::Test
18  def matches?(open, close)
19    case open
20    when '('
21      return close == ')'
22    when '{'
23      return close == '}'
24    when '['
25      return close == ']'
26    else
27      raise [open, close].inspect
28    end
29  end
30
31  def matched_string?(string)
32    stack = []
33    string.chars.each do |char|
34      case char
35      when '{', '[', '('
36        stack.push(char)
37      else
38        return unless matches?(stack.pop, char)
39      end
40    end
41    stack.size.zero?
42  end
43
44  def test_valid
45    assert matched_string?("{{()[]}}")
46  end
47
48  def test_invalid
49    refute matched_string?("{{()]}")
50  end
51end