def assert_equal(x, y)
  raise "Expected #{x.inspect}, Got #{y.inspect}" unless x == y
end

=begin

stack:

---
|[|
---
|{|
---
|(|
---

       x
|(|{|[|)|]|
=end


class Solution
  MATCHES = {
    '(' => ')',
    '[' => ']',
    '{' => '}'
  }.freeze

  # space: O(n)
  # time: O(n)
  def self.run(input)
    stack = []

    for current in input.chars
      if MATCHES[current]
        stack.push(current)
      elsif current == MATCHES[stack[-1]]
        stack.pop
      else
        break
      end
    end

    stack.empty?
  end
end

assert_equal true, Solution.run("((()))")
assert_equal true, Solution.run("[()]{}")
assert_equal false, Solution.run("({[)]")
assert_equal false, Solution.run("()(){(())")
assert_equal true, Solution.run("")
assert_equal true, Solution.run("([{}])()")
puts "Yay!"