Парсер многократной польской нотации с операциями сложения и умножения

Условие

Требуется реализовать парсер для польской нотации, где операции могут принимать произвольное количество аргументов. Поддерживаются только два арифметических действия: сложение и умножение.

Пример записи в польской нотации: (+ 2 4) → 2 + 4 → 6 (* (+ 3 6) (* 1 2 3)) → (3 + 6) * (1 * 2 * 3) → 9 * 1 * 2 * 3 → 54

Ответ

Разберите выражение рекурсивно: число возвращает своё значение, а скобочная форма содержит оператор и список вложенных выражений. После разбора нужно проверить закрывающие скобки и отсутствие лишних токенов.

Ниже поддерживаются целые числа и хотя бы один аргумент у каждой операции:

import re

def evaluate(text):
    tokens = re.findall(r'\(|\)|[^\s()]+', text)
    index = 0
    def parse():
        nonlocal index
        if index >= len(tokens):
            raise ValueError('Неожиданный конец')
        token = tokens[index]
        index += 1
        if token != '(':
            return int(token)
        if index >= len(tokens) or tokens[index] not in ('+', '*'):
            raise ValueError('Ожидался оператор')
        operation = tokens[index]
        index += 1
        result, count = (0 if operation == '+' else 1), 0
        while index < len(tokens) and tokens[index] != ')':
            value = parse()
            result = result + value if operation == '+' else result * value
            count += 1
        if index >= len(tokens) or count == 0:
            raise ValueError('Незакрытая или пустая операция')
        index += 1
        return result
    result = parse()
    if index != len(tokens):
        raise ValueError('Лишние токены')
    return result

Примеры дают 6 и 54. Внешний ввод следует ограничить по длине и глубине вложенности. Разбор линейный по токенам, не считая стоимости арифметики больших целых; eval не используется.