marchdown/indirect

## indirect
################################################################################
# Programs must be written for people to read, and only incidentally for machines to execute.
#         -- Abelson & Sussman, SICP
#         http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-7.html
#
# Особенно это важно для кода, который хочется обсудить, понять и поправить — т.е. практически для любого.
# Так что я буду оставлять комментарии по мере чтения, так читать проще.
# Комментарии будут _под_ соответствующими строками кода.
def function(s):
    st='#'
    i=0
    old_st=''
    arr=[]

    while(s[i]!='#') or (old_st!=st):
    # главный цикл прервывается только если попадается '#' или если за весь цикл буфер не поменялся.
    # если до конца буфера не доходим или если он меняется при каждом проходе, цикл не прерывается.
        old_st=st
        if ( ( (st[-1]=='#') or (st[-1]=='*') or (st[-1]=='+') or (st[-1]=='(') ) and ( (s[i]=='1') or (s[i]=='(') ) ):
            # N.B. Это сложное условие можно написать короче и понятнее:
            #  if ((st[-1] in '#*+(' ) and\ # <-- бэкслеш аннулирует перенос строки, получается читаемей.
            #      (s[i]   in '1('   ) ):
            # последовательно проверяем все знаки входной строки от _начала_ к концу, пытаемся их перенести на стек, если соблюдено следующее условие:
            # В таблице предшествования (которая здесь представлена в виде отдельных столбцов) указано, что текущий (i-тый) символ входа
            # может предшествовать символу на верхушке стека в корретном выражении данного языка.

            # перенос: входной символ может предшествовать символу на верхушке стека, надо переносить и двигать указатель.
            st=st+s[i]
            i=i+1
        elif ((st[-1]=='E')and ((s[i]=='+')or(s[i]=='(')))or((st[-1]=='T')and(s[i]=='*')):
            # перенос: входной символ '+' или '('  или '*' может предшествовать такому-то символу на верхушке стека, надо переносить и двигать указатель.
            st=st+s[i]
            i=i+1
        elif (st[-1]=='N') and ((s[i]=='0') or (s[i]=='1')):
            # перенос: входной символ может предшествовать символу на верхушке стека, надо переносить и двигать указатель.
            st=st+s[i]
            i=i+1
        elif (st[-1]=='1') and ((s[i]=='1') or (s[i]=='0') or (s[i]==')') or (s[i]=='+') or (s[i]=='*') or (s[i]=='#')):
            # свертка и операция над "числом"
            # цифра: входной символ — цифра в допустимой позиции, её можно положить на стек и добавить к нашему "числу" arr.
            if st[-2:]=='N1':
            # 'N' — это такой флажок, означает, что за ним идет число в двоичной записи. Нашему обработчику нужно это число скушать.
            # если последние два символа стека имеют вид 'N1', ...
                st=st[i-1]
                # оставь от всего стека только st[i-1].
                # ! скорее всего, здесь ошибка. Мы лишаемся стека, а в переменную st кладем одиночный символ. Зачем нам выбрасывать весь стек?
                arr[-1]=arr[-1]*2+1
                # предпоследний элемент нашего числа — единица или ноль — удваивается и увеличивается на 1.
                # Скорее всего, здесь тоже ошибка.
            else:
                st=st[i-1]+'N'
                # если стек не кончается на 'N1', выброси все, кроме st[i-1] (не s[i-1] ли здесь должно быть?) и добей 'N' на конце
                arr=arr+[1]
                # приклей к нашему "числу" единицу. arr.append(1).
                # N.B. В питоне есть стандартные операции на списках: arr.append(foo) и arr.extend([foo bar])
        elif ((st[-1]=='0') and (s[i]=='1') or (s[i]=='0') or (s[i]==')') or (s[i]=='+') or (s[i]=='*') or (s[i]=='#')):
            # если во входной строке — цифра, а в стеке — знак, допустимый после цифры, то
            # должен быть перенос, но вместо этого
              if st[-2:]=='N0':
                  st=st[i-1]
                  # если стек кончается на 'N0', похерить стек, запомнить какой-то эл-т стека — кто нам гарантирует, что в стеке к этому моменту вообще есть i-1-ый элемент?
                  arr[-1]=arr[-1]*2
                  # Удвой последний элемент "числа"
        elif (st[-1]=='N') and ((s[i]==')') or (s[i]=='+') or (s[i]=='*') or (s[i]=='#')):
            st=st[i-1]+'F'
            # Ошибка, опять теряем стек
            # Это должна была быть свертка "N" -> "F"
        elif (st[-1]=='F') and ((s[i]==')') or (s[i]=='+') or (s[i]=='*') or (s[i]=='#')):
            if st[-2:]=='T*F':
                st=st[i-2]
                # Выбрасываем весь стек, сохраняем в st какой-то элемент.
                # Это должна была быть свертка "T*F" -> "F"
                arr[-2]=arr[-2]*arr[-1]
                # Один шаг свёртки умножением справа. Красиво :)
                arr.pop()
                # Выкинуть последний эл-т "числа", он уже учтен.
            else:
                st=st[i-1]+'T'
                # Если не получается свертка "T*F" -> "F", ... Что здесь должно быть? Свёртка "F" -> "T"?
        elif (st[-1]=='T') and ((s[i]==')') or (s[i]=='+') or (s[i]=='*') or (s[i]=='#')):
            if st[-2:]=='E+T':
                # Это должна была быть свертка "E+T" -> "E"
                st=st[i-2] # Здесь, как и везде, видимо имеется в виду st=st[:-2]
                arr[-2]=arr[-2]*arr[-1]
                arr.pop()
                # Избавились от последнией цифры "числа". Можно ли так? А если arr[-1] — это ноль? Умножить предыдущую цифру на ноль?
            else:
                st=st[i-1]+'E' # Здесь, как и везде, видимо имеется в виду st=st[:-1], а не [i-1]
        elif (st[-1]==')') and ((s[i]==')') or (s[i]=='+') or (s[i]=='*') or (s[i]=='#')):
            if st[-2:]=='N0':
                st=st[:-2]+'N'
                ## У нас было число в двоичной записи. Встретив его (первую цифру после скольких-то скобок), мы свернули цифирьки на стеке в N (Каждая N появляется либо из единицы верхнего разряда, либо из N0 или N1, то есть образуются цепочечки типа N101101110, и эта N сворачивается поочередно как N1->N и как N0->N, "скушивая" очередную цифру в цепочке), а пока на стеке лежал N, мы производили некоторые манипуляции над arr. Каждый раз, сворачивая число до N1 мы оставляли в arr новую единицу. Это аналог "переноса в уме". Сворачивая до N0 мы считали, что ничего переносить не нужно.
            else:
                i=1
    return [st, arr[0]]
    # Верни стек (зачем?) и довычисленное число.
	################################################################################
	# Programs must be written for people to read, and only incidentally for machines to execute.
	# -- Abelson & Sussman, SICP
	# http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-7.html
	#
	# Особенно это важно для кода, который хочется обсудить, понять и поправить — т.е. практически для любого.
	# Так что я буду оставлять комментарии по мере чтения, так читать проще.
	# Комментарии будут _под_ соответствующими строками кода.
	def function(s):
	st='#'
	i=0
	old_st=''
	arr=[]

	while(s[i]!='#') or (old_st!=st):
	# главный цикл прервывается только если попадается '#' или если за весь цикл буфер не поменялся.
	# если до конца буфера не доходим или если он меняется при каждом проходе, цикл не прерывается.
	old_st=st
	if ( ( (st[-1]=='#') or (st[-1]=='*') or (st[-1]=='+') or (st[-1]=='(') ) and ( (s[i]=='1') or (s[i]=='(') ) ):
	# N.B. Это сложное условие можно написать короче и понятнее:
	# if ((st[-1] in '#*+(' ) and\ # <-- бэкслеш аннулирует перенос строки, получается читаемей.
	# (s[i] in '1(' ) ):
	# последовательно проверяем все знаки входной строки от _начала_ к концу, пытаемся их перенести на стек, если соблюдено следующее условие:
	# В таблице предшествования (которая здесь представлена в виде отдельных столбцов) указано, что текущий (i-тый) символ входа
	# может предшествовать символу на верхушке стека в корретном выражении данного языка.

	# перенос: входной символ может предшествовать символу на верхушке стека, надо переносить и двигать указатель.
	st=st+s[i]
	i=i+1
	elif ((st[-1]=='E')and ((s[i]=='+')or(s[i]=='(')))or((st[-1]=='T')and(s[i]=='*')):
	# перенос: входной символ '+' или '(' или '*' может предшествовать такому-то символу на верхушке стека, надо переносить и двигать указатель.
	st=st+s[i]
	i=i+1
	elif (st[-1]=='N') and ((s[i]=='0') or (s[i]=='1')):
	# перенос: входной символ может предшествовать символу на верхушке стека, надо переносить и двигать указатель.
	st=st+s[i]
	i=i+1
	elif (st[-1]=='1') and ((s[i]=='1') or (s[i]=='0') or (s[i]==')') or (s[i]=='+') or (s[i]=='*') or (s[i]=='#')):
	# свертка и операция над "числом"
	# цифра: входной символ — цифра в допустимой позиции, её можно положить на стек и добавить к нашему "числу" arr.
	if st[-2:]=='N1':
	# 'N' — это такой флажок, означает, что за ним идет число в двоичной записи. Нашему обработчику нужно это число скушать.
	# если последние два символа стека имеют вид 'N1', ...
	st=st[i-1]
	# оставь от всего стека только st[i-1].
	# ! скорее всего, здесь ошибка. Мы лишаемся стека, а в переменную st кладем одиночный символ. Зачем нам выбрасывать весь стек?
	arr[-1]=arr[-1]*2+1
	# предпоследний элемент нашего числа — единица или ноль — удваивается и увеличивается на 1.
	# Скорее всего, здесь тоже ошибка.
	else:
	st=st[i-1]+'N'
	# если стек не кончается на 'N1', выброси все, кроме st[i-1] (не s[i-1] ли здесь должно быть?) и добей 'N' на конце
	arr=arr+[1]
	# приклей к нашему "числу" единицу. arr.append(1).
	# N.B. В питоне есть стандартные операции на списках: arr.append(foo) и arr.extend([foo bar])
	elif ((st[-1]=='0') and (s[i]=='1') or (s[i]=='0') or (s[i]==')') or (s[i]=='+') or (s[i]=='*') or (s[i]=='#')):
	# если во входной строке — цифра, а в стеке — знак, допустимый после цифры, то
	# должен быть перенос, но вместо этого
	if st[-2:]=='N0':
	st=st[i-1]
	# если стек кончается на 'N0', похерить стек, запомнить какой-то эл-т стека — кто нам гарантирует, что в стеке к этому моменту вообще есть i-1-ый элемент?
	arr[-1]=arr[-1]*2
	# Удвой последний элемент "числа"
	elif (st[-1]=='N') and ((s[i]==')') or (s[i]=='+') or (s[i]=='*') or (s[i]=='#')):
	st=st[i-1]+'F'
	# Ошибка, опять теряем стек
	# Это должна была быть свертка "N" -> "F"
	elif (st[-1]=='F') and ((s[i]==')') or (s[i]=='+') or (s[i]=='*') or (s[i]=='#')):
	if st[-2:]=='T*F':
	st=st[i-2]
	# Выбрасываем весь стек, сохраняем в st какой-то элемент.
	# Это должна была быть свертка "T*F" -> "F"
	arr[-2]=arr[-2]*arr[-1]
	# Один шаг свёртки умножением справа. Красиво :)
	arr.pop()
	# Выкинуть последний эл-т "числа", он уже учтен.
	else:
	st=st[i-1]+'T'
	# Если не получается свертка "T*F" -> "F", ... Что здесь должно быть? Свёртка "F" -> "T"?
	elif (st[-1]=='T') and ((s[i]==')') or (s[i]=='+') or (s[i]=='*') or (s[i]=='#')):
	if st[-2:]=='E+T':
	# Это должна была быть свертка "E+T" -> "E"
	st=st[i-2] # Здесь, как и везде, видимо имеется в виду st=st[:-2]
	arr[-2]=arr[-2]*arr[-1]
	arr.pop()
	# Избавились от последнией цифры "числа". Можно ли так? А если arr[-1] — это ноль? Умножить предыдущую цифру на ноль?
	else:
	st=st[i-1]+'E' # Здесь, как и везде, видимо имеется в виду st=st[:-1], а не [i-1]
	elif (st[-1]==')') and ((s[i]==')') or (s[i]=='+') or (s[i]=='*') or (s[i]=='#')):
	if st[-2:]=='N0':
	st=st[:-2]+'N'
	## У нас было число в двоичной записи. Встретив его (первую цифру после скольких-то скобок), мы свернули цифирьки на стеке в N (Каждая N появляется либо из единицы верхнего разряда, либо из N0 или N1, то есть образуются цепочечки типа N101101110, и эта N сворачивается поочередно как N1->N и как N0->N, "скушивая" очередную цифру в цепочке), а пока на стеке лежал N, мы производили некоторые манипуляции над arr. Каждый раз, сворачивая число до N1 мы оставляли в arr новую единицу. Это аналог "переноса в уме". Сворачивая до N0 мы считали, что ничего переносить не нужно.
	else:
	i=1
	return [st, arr[0]]
	# Верни стек (зачем?) и довычисленное число.