1def assert_equal(x, y)
 2  raise "Expected #{x.inspect}, Got #{y.inspect}" unless x == y
 3end
 4
 5=begin
 6
 7stack:
 8
 9---
10|[|
11---
12|{|
13---
14|(|
15---
16
17       x
18|(|{|[|)|]|
19=end
20
21
22class Solution
23  MATCHES = {
24    '(' => ')',
25    '[' => ']',
26    '{' => '}'
27  }.freeze
28
29  # space: O(n)
30  # time: O(n)
31  def self.run(input)
32    stack = []
33
34    for current in input.chars
35      if MATCHES[current]
36        stack.push(current)
37      elsif current == MATCHES[stack[-1]]
38        stack.pop
39      else
40        break
41      end
42    end
43
44    stack.empty?
45  end
46end
47
48assert_equal true, Solution.run("((()))")
49assert_equal true, Solution.run("[()]{}")
50assert_equal false, Solution.run("({[)]")
51assert_equal false, Solution.run("()(){(())")
52assert_equal true, Solution.run("")
53assert_equal true, Solution.run("([{}])()")
54puts "Yay!"