Cấu trúc đệ quy

Bài học 9 trên 29 trong khóa học Dự án máy tính bằng Python của Coddy.

Sức mạnh thực sự của cấu trúc mà chúng ta đã tìm hiểu ở bài học trước nằm ở đệ quy.

Hãy xem xét phép tính có nhiều hơn một toán tử, ví dụ:

2 + 3 * 4 + 5

Theo quy tắc toán học, các phép tính có thứ tự: trước tiên, chúng ta cần tính 3 * 4, sau đó tính phần còn lại.

Phép tính sau đây có thể được biểu diễn thành cấu trúc đệ quy theo những cách sau:

['+', ['+', 2, ['*', 3, 4]], 5]
['+', 2, ['+', 5, ['*', 3, 4]]]
['+', 5, ['+', ['*', 3, 4], 2]]

Lưu ý rằng cấu trúc đơn giản sâu nhất luôn là ['*', 3, 4], đây là phép tính được thực hiện trước tiên. Cũng cần lưu ý rằng mọi thứ đều tuân theo cấu trúc cơ bản [op, num1, num2].

Một vài ví dụ khác về cách biểu diễn phép tính thành cấu trúc đệ quy:

2 - 3 -> ['-', 2, 3]
1 - 2 + 3 -> ['+', ['-', 1, 2], 3]
1 * 2 - 3 -> ['-', ['*', 1, 2], 3]
2.3 + 3 / 4.2 - 2 -> ['-', ['+', 2.3, ['/', 3, 4.2]], 2]

Thử thách

Trung bình

Nâng cấp hàm eval để hỗ trợ cấu trúc đệ quy như mô tả ở trên.

Lưu ý:

gọi hàm calc khi cấu trúc là cấu trúc đơn giản, toán tử có hai số .
gọi đệ quy hàm eval nếu một trong các đối số là một cấu trúc khác (danh sách).

Tự làm thử

def calc(op, n1, n2=None):
    if not isinstance(n1, int) and not isinstance(n1, float):
        raise Exception('Invalid number "' + str(n1) + '"')

    if n2 is None:
        if op == '+' or op == 'add':
            return n1
        if op == '-' or op == 'sub':
            return -n1

        raise Exception('Invalid operator "' + op + '"')

    if not isinstance(n2, int) and not isinstance(n2, float):
        raise Exception('Invalid number "' + str(n2) + '"')

    if op == '+' or op == 'add':
        return n1 + n2
    if op == '-' or op == 'sub':
        return n1 - n2
    if op == '*' or op == 'mul':
        return n1 * n2
    if op == '/' or op == 'div':
        if n2 == 0:
            raise Exception("Division by zero")
        return n1 / n2
    if op == '%' or op == 'mod':
        if n2 == 0:
            raise Exception("Division by zero")
        return n1 % n2
    if op == '^' or op == 'pow':
        return n1 ** n2

    raise Exception('Invalid operator "' + op + '"')


def eval(lst):
    op = lst[0]
    n1 = lst[1]
    n2 = lst[2]
    return calc(op, n1, n2)