class Atom
  def initialize(content = nil)
    @content = content
  end

  attr_reader :content

  def to_s
    content
  end

  def self.from_token(token)
    new(token.content)
  end
end

class SExp
  def initialize(addr = nil, decr = nil)
    @addr = addr
    @decr = decr
  end

  def car
    @addr
  end
  def car=(addr)
    @addr = addr
  end

  def cdr
    @decr
  end
  def cdr=(decr)
    @decr = decr
  end

  def nil?
    car.nil? && cdr.nil?
  end

  def to_s
    if car.nil?
      "()"
    elsif cdr.nil?
      "(#{car} . ())"
    else
      "(#{car} . #{cdr})"
    end
  end

  def to_a
    res = []
    at = self

    until at.nil?
      res << at.car
      at = at.cdr
    end

    res
  end

  def self.from_a(list)
    if list.empty?
      SExp.new
    else
      SExp.new(list[0], SExp.from_a(list[1..-1]))
    end
  end
end

def peek_token(tokens)
  tokens.first
end

def get_token(tokens)
  tokens.shift
end

def num_members(tokens)
  members = 0
  level = 1
  at = 1

  until level == 0
    case tokens.at(at)
    when T_LParen
      members += 1 if level == 1
      level += 1
    when T_RParen
      level -= 1
    when T_Atom
      members += 1 if level == 1
    end
    at += 1
  end

  members
end

def parse_sexp(tokens)
  need = num_members(tokens)
  get_token(tokens)
  
  members = []

  need.times do
    case peek_token(tokens)
    when T_Atom
      members << Atom.from_token(get_token(tokens))
    when T_LParen
      members << parse_sexp(tokens)
    end
  end

  get_token(tokens)

  SExp.from_a(members)
end

def parse_sexps(tokens)
  sexps = []

  until tokens.empty?
    sexps << parse_sexp(tokens)
  end

  sexps
end