DjangoBB LoFi version

Полная версия: Нужна помощь по задачке - вычислить глубину математического выражения

Начало » Python для новичков » Нужна помощь по задачке - вычислить глубину математического выражения

1 2

laf17c0dx

Сен. 17, 2010 06:41:21

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

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

•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

Проблема:
Проверяется только первый элемент списка. Нужно как-то пройтись по всем элементам, для каждого вложенного списка накапливая значение глубины выражения. Препод предложил использовать функции map() и max().

Zubchick

Сен. 17, 2010 10:33:16

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))))

laf17c0dx

Сен. 17, 2010 17:25:49

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

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

laf17c0dx

Сен. 17, 2010 19:34:54

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

Zubchick

Сен. 17, 2010 21:12:29

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

оно вам надо?

laf17c0dx

Сен. 17, 2010 23:08:45

Zubchick

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

оно вам надо?

согласен, некрасиво получается

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

Спасибо!

Сен. 18, 2010 18:04:44

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])

Zubchick

Сен. 18, 2010 20:13:43

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

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

Сен. 18, 2010 21:47:26

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

laf17c0dx

Сен. 26, 2010 20:51:28

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