Задача: 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 {
    evaluate(expression) {
        const evaluate = (expression, env) => {
            if (!expression.startsWith('(')) {
                if (isNaN(expression)) {
                    return env[expression];
                }
                return parseInt(expression);
            }
            
            const tokens = tokenize(expression);
            if (tokens[0] === 'let') {
                for (let i = 1; i < tokens.length - 2; i += 2) {
                    env[tokens[i]] = evaluate(tokens[i + 1], env);
                }
                return evaluate(tokens[tokens.length - 1], env);
            } else if (tokens[0] === 'add') {
                return evaluate(tokens[1], env) + evaluate(tokens[2], env);
            } else if (tokens[0] === 'mult') {
                return evaluate(tokens[1], env) * evaluate(tokens[2], env);
            }
        };
        
        const tokenize = (expression) => {
            let tokens = [];
            let token = '';
            let parens = 0;
            for (let char of expression) {
                if (char === '(') {
                    parens++;
                    if (parens === 1) {
                        continue;
                    }
                } else if (char === ')') {
                    parens--;
                    if (parens === 0) {
                        tokens.push(tokenize(token));
                        token = '';
                        continue;
                    }
                } else if (char === ' ' && parens === 1) {
                    if (token) {
                        tokens.push(token);
                        token = '';
                    }
                    continue;
                }
                token += char;
            }
            if (token) {
                tokens.push(token);
            }
            return tokens;
        };
        
        return evaluate(expression, {});
    }
}

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