Python-сообщество

Здравствуйте, уважаемые! В Питоне я новичок, в алгоритмах, считайте, тоже.
В задаче нужно реализовать функцию, соответствующую определенному алгоритму.

Условие задачи:
Написать функцию, вычисляющую “глубину” математического выражения.
Например:

•depth('x') => 0
•depth(('expt', ‘x’, 2)) => 1
•depth(('+', ('expt', ‘x’, 2), ('expt', ‘y’, 2))) => 2
•depth(('/', ('expt', ‘x’, 5), ('expt', ('-', ('expt', ‘x’, 2), 1), ('/', 5, 2)))) => 4

Само выражение задано списком, как единственный аргумент функции.

Набросок решения:
Додумался набросать рекурсию. Ноль возвращает, если элемент – не список. Прибавляет 1 и вызывает саму себя, если элемент – список.

# Problem 2.2: Expression depth
def depth(expr):
    #how to apply the function to all list members?
    if not isinstance(expr, (list, tuple)):
        return 0
    if isinstance(expr, (list, tuple)):
        return 1 + depth(expr)
    #raise NotImplementedError

def depth(expr, count=0):
    if not isinstance(expr, (list, tuple)):
        return count
    else:
        return max(map(lambda x: depth(x, count + 1), expr))

if __name__ == '__main__':
    print depth('x')
    print depth(('expt', 'x', 2))
    print depth(('+', ('expt', 'x', 2), ('expt', 'y', 2)))
    print depth(('/', ('expt', 'x', 5), ('expt', ('-', ('expt', 'x', 2), 1), ('/', 5, 2))))

Отредактировано (Сен. 17, 2010 10:33:39)

Согласен, но только нужно, чтобы depth(expr) только сам список передавался. Т.е. функция жестко задана, нельзя счетчик передавать.

UPD: Хотя нет, все можно. Важно было только, что в тестовых примерах ей передается только список.
Большое спасибо!

Отредактировано (Сен. 17, 2010 17:41:08)

Вопрос из интереса– как сделать то же самое с помощью reduce()?

else:
    return reduce(lambda x, y: (x, y)[y > x], map(lambda x: depth(x, count + 1), expr))

Отредактировано (Сен. 17, 2010 21:14:07)

Zubchick

else:
    return reduce(lambda x, y: (x, y)[y > x], map(lambda x: depth(x, count + 1), expr))

оно вам надо?

Отредактировано (Сен. 18, 2010 07:55:11)

laf17c0dx
..а без count можно обойтись, если сказать depth(x) + 1 в рекурсии, и просто return 0 в базовом условии.

def depth(expr):
    return int(isinstance(expr, (list, tuple))) and max([depth(x)+1 for x in expr])

Можно даже не приводить к int

Ed
def depth(expr):
return isinstance(expr, (list, tuple)) and max()

Нельзя. Тогда depth('x') вернет False, а не 0.

даа..в одну строчку еще более красиво и просто!)