#!/usr/bin/python3
#AST gist.

from time import sleep

def strip_parens(input_string):
    '''
    this function is causing problems-- I initially naively assumed
    that there would only be an outermost layer of parentheses
    when we strip off the outermost layer, sometimes there are ')('
    pairs inside.
    '''
    """
    If the string begins and ends with parens, remove them
    If they aren't there at all, just return the string
    """
    if input_string[0] == '(' and input_string[-1] == ')':
        return input_string[1:-1]
    else:
        return input_string

def find_paren_index_pairs(input_string):
    '''
    This actually works for arbitrary strings. I think this is
    #closer to how I should actually be writing the AST parser.
    '''
    """
    Takes a string and returns the open/close pairs of parentheses.
    ...Assumes a well formed string.
    """
    pairs = []
    open_state = 0
    seen_parens = 0
    for input_index, char in enumerate(input_string):
        if char == '(':
            seen_parens += 1
            pairs.insert(0, [input_index, None])
        elif char == ')':
            for pair_index, pair in enumerate(pairs):
                if pair[1] is None:
                    pairs[pair_index][1] = input_index
                    break
    return pairs

def split_along_parens(input_string):
    """
    splits a string into three strings:
    the text found before the first '('.
    the text inside and up to the last ')'.
    the text after the last '('

    'first (list 1 (+ 2 3) 9)' --> 'first', '(list 1 (+ 2 3) 9)', ''

    Breaks right now if there are multiple pairs of parentheses on the same
    level of the tree.
    """
    l_index, r_index = input_string.find('('), input_string.rfind(')') + 1
    #check for parens inside that range:
    inner_range = input_string[l_index + 1:r_index - 1]
    if '(' in inner_range and ')' in inner_range:
        print("INNER RANGE: {}".format(inner_range))
        inner_l_index, inner_r_index = input_string.find('('), input_string.rfind(')')
        '''
        I thought I could fix the problem by checking whether the pair was crossed
        i.e. there exists a ')' before the first '(' in the middle of the checked
        string.
        '''
        if inner_l_index > inner_r_index:
            r_index = inner_r_index + 1
    left, middle, right = (input_string[:l_index],
                           input_string[l_index:r_index],
                           input_string[r_index:])
    return left, middle, right

def parser(input_string, debug=False):
    """
    Takes a string as input, returns a nested array of strings and ints.

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

    ... assumes a well formed string with matched pairs of parentheses
        and spaces as separators between elements.
    """
    if input_string == '':
        return ''
    #input_string = input_string.strip()
    input_string = strip_parens(input_string).strip()
    if '(' in input_string and ')' in input_string:
        left, middle, right = split_along_parens(input_string)
        left_output, middle_output, right_output =  (parser(left),
                                                     parser(middle),
                                                     parser(right))
        l_is_list, r_is_list = (type(left_output) not in (str, int),
                                type(right_output) not in (str, int))
        if l_is_list and not r_is_list:
            output = (*left_output, middle_output, right_output)
        elif not l_is_list and r_is_list:
            output = (left_output, middle_output, *right_output)
        elif l_is_list and r_is_list:
            output = (*left_output, middle_output, *right_output)
        else:
            output = (left_output, middle_output, right_output)
        output = [string for string in output if string != '']
        return output
    elif ' ' in input_string:
        output = input_string.split(' ')
        output = [int(string) if string.isdigit()
                              else string
                              for string in output]
        return output
    else:
        if input_string.isdigit():
            return int(input_string)
        else:
            return input_string

def interpreter(input_string):


def main():
    tests = ("(1 1 1)",
             "(1 (1 1))",
             "(first (list 1 (+ 2 3) 9))",
             "(0 1 ((a b c) d) e f)",
             "(0 1 ((a b c) (1 2 3) d) e f)") #breaks on this case

    for test in tests:
        print("input: {}".format(test))
        output = parser(test)
        print("output : {}".format(output))

    plus_tests = ("(+ 1 1)",
                  "(+ (+ 1 1) 4)",
                  "(+ (+ 2 2) (+ 2 2))")

main()