Python | LeetCode

Задача: 736. Parse Lisp Expression
Сложность: hard

Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.

Пример:

Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
Output: 14

👨‍💻

Алгоритм:

1⃣Определите функцию для оценки выражений.

2⃣Используйте рекурсивный подход для обработки различных типов выражений (let, add, mult, и переменных).

3⃣Используйте словарь для отслеживания значений переменных с учетом области видимости.

😎

Решение:

class Solution:
    def evaluate(self, expression: str) -> int:
        def evaluate(expression, env):
            if expression[0] != '(':
                if expression[0].isalpha():
                    return env[expression]
                return int(expression)
            
            tokens = tokenize(expression)
            if tokens[0] == 'let':
                for i in range(1, len(tokens) - 2, 2):
                    env[tokens[i]] = evaluate(tokens[i + 1], env)
                return evaluate(tokens[-1], env)
            elif tokens[0] == 'add':
                return evaluate(tokens[1], env) + evaluate(tokens[2], env)
            elif tokens[0] == 'mult':
                return evaluate(tokens[1], env) * evaluate(tokens[2], env)
        
        def tokenize(expression):
            tokens, token, parens = [], '', 0
            for char in expression:
                if char == '(':
                    parens += 1
                    if parens == 1:
                        continue
                elif char == ')':
                    parens -= 1
                    if parens == 0:
                        tokens.append(tokenize(token))
                        token = ''
                        continue
                elif char == ' ' and parens == 1:
                    if token:
                        tokens.append(token)
                        token = ''
                    continue
                token += char
            if token:
                tokens.append(token)
            return tokens
        
        return evaluate(expression, {})

Ставь 👍 и забирай 📚 Базу знаний

Please open Telegram to view this post