Преобразование AST арифметического выражения в строковое представление кода

Условие

Дано: арифметическое выражение задано в виде AST (Abstract Syntax Tree) в префиксной нотации.

AST может быть либо вещественным числом, либо массивом, где первый элемент всегда строка, обозначающая арифметическую операцию, а все последующие элементы – её аргументы (тоже в виде AST):

AST = float | ['operation', operand1, operand2, ..., operandN], где operand1, operand2, … – AST.

Поддерживаются следующие операции:

• унарный минус (-)
• унарный плюс (+)
• сложение (+)
• вычитание (-)
• умножение (*)
• деление (/).

Можно считать, что входные данные всегда корректны.

Необходимо реализовать функцию astToCode, принимающую AST и возвращающую строку с эквивалентным кодом.

function astToCode(array|float $node): string
{
    // реализация преобразования
}

function test(array|float $node, string $expected): void
{
    $actual = astToCode($node);
    echo $actual === $expected ? 'OK' : "FAIL ";
    echo ": $expected" . PHP_EOL;
}

test(5, '5');
test(, , 3]]], '-(+3)');
test(, 1]], '+(-1)');
test(, ], '(1 * 2) * (3 - 1)');
test(]], '2 * 5 * 7 / (8 - (5 + 6))');
test(, , ], '1 + 2 - (3 - 4) - (5 + 6)');

Ответ

AST преобразуется рекурсивно: число становится литералом, унарная операция оборачивает аргумент, многоместная соединяет аргументы оператором. Скобки сохраняют структуру вычисления.

В тестовых вызовах условия потеряны части массивов, поэтому точное совпадение их форматирования проверить нельзя. Корректный вариант с избыточными скобками:

function astToCode(array|float $node): string
{
    if (!is_array($node)) {
        return json_encode($node, JSON_THROW_ON_ERROR);
    }
    $operator = $node[0];
    $parts = array_map('astToCode', array_slice($node, 1));
    if (count($parts) === 1) {
        return '(' . $operator . $parts[0] . ')';
    }
    return '(' . implode(' ' . $operator . ' ', $parts) . ')';
}

Предполагаются конечные числа и левосторонняя последовательность для многоместных - и /. Минимальные скобки требуют отдельного учёта приоритета, ассоциативности и позиции дочернего выражения.