# Lisp parser
#
# Write code that takes some Lisp code and returns an abstract syntax tree. The
# AST should represent the structure of the code and the meaning of each token.
# For example, if your code is given "(first (list 1 (+ 2 3) 9))", it could
# return a nested array like ["first", ["list", 1, ["+", 2, 3], 9]].
#
# During your interview, you will pair on writing an interpreter to run the AST.
class LispParser

  attr_reader :tokens

  def initialize(expression)
    @tokens = tokenize(expression)
  end

  def read
    case token = pop_next_token
    when /\(/          then read_list
    when /['"].*/      then token[1..-2]
    when /[[:digit:]]/ then token.to_i
    else token.to_sym
    end
  end

  private

  def read_list
    list = []
    list << read until end_of_list?
    pop_next_token
    list
  end

  def tokenize(expression)
    expression.gsub(/([()])/, ' \1 ').strip.split(' ')
  end

  def peek
    tokens.first
  end

  def end_of_list?
    peek == ')'
  end

  def pop_next_token
    tokens.shift
  end

end

def solution(expr)
  lisp_expression = LispParser.new(expr)
  lisp_expression.read
end

def assert_equal(a, b)
  puts a == b ? 'Passed.' : "Failed. Expected #{a} to equal #{b}"
end

input = '(first (list 1 (+ 2 3) 9))'
output = [:first, [:list, 1, [:+, 2, 3], 9]]
assert_equal solution(input), output

input = '(first (list 1 (+ 2 3) "9"))'
output = [:first, [:list, 1, [:+, 2, 3], '9']]
assert_equal solution(input), output

input = '(first (list 1 (+ 2 (- 5 (\ 10 5))) 9))'
output = [:first, [:list, 1, [:+, 2, [:-, 5, [:'\\', 10, 5]]], 9]]
assert_equal solution(input), output