Сложность: 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, {})
Ставь 👍 и забирай 📚 Базу знаний