Задача: 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 {
    public function evaluate($expression) {
        return $this->evaluateExpression($expression, []);
    }

    private function evaluateExpression($expression, $env) {
        if ($expression[0] !== '(') {
            if (is_numeric($expression) || $expression[0] === '-') {
                return intval($expression);
            }
            return $env[$expression] ?? 0;
        }

        $tokens = $this->tokenize($expression);
        if ($tokens[0] === "let") {
            for ($i = 1; $i < count($tokens) - 2; $i += 2) {
                $env[$tokens[$i]] = $this->evaluateExpression($tokens[$i + 1], $env);
            }
            return $this->evaluateExpression($tokens[count($tokens) - 1], $env);
        } elseif ($tokens[0] === "add") {
            return $this->evaluateExpression($tokens[1], $env) + $this->evaluateExpression($tokens[2], $env);
        } elseif ($tokens[0] === "mult") {
            return $this->evaluateExpression($tokens[1], $env) * $this->evaluateExpression($tokens[2], $env);
        }
        return 0;
    }

    private function tokenize($expression) {
        $tokens = [];
        $token = '';
        $parens = 0;

        for ($i = 0; $i < strlen($expression); $i++) {
            $c = $expression[$i];
            if ($c === '(') {
                $parens++;
                if ($parens === 1) continue;
            } elseif ($c === ')') {
                $parens--;
                if ($parens === 0) {
                    $tokens = array_merge($tokens, $this->tokenize($token));
                    $token = '';
                    continue;
                }
            } elseif ($c === ' ' && $parens === 1) {
                if ($token !== '') {
                    $tokens[] = $token;
                    $token = '';
                }
                continue;
            }
            $token .= $c;
        }
        if ($token !== '') {
            $tokens[] = $token;
        }
        return $tokens;
    }
}

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