Задача: 224. Basic Calculator
Сложность: hard

Дана строка s, представляющая собой допустимое выражение, реализуйте базовый калькулятор для его вычисления и верните результат вычисления.
Примечание: нельзя использовать встроенные функции, которые оценивают строки как математические выражения, такие как eval().

Пример:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

👨‍💻 Алгоритм:

1⃣Итерация строки выражения в обратном порядке:
Читаем выражение символ за символом, формируя операнды из нескольких цифр, если символ - цифра.
Сохраняем операнды в стек, как только встречаем нецифровой символ.

2⃣Обработка выражения внутри скобок:
Когда встречаем открывающую скобку '(', оцениваем выражение, удаляя операнды и операторы из стека до соответствующей закрывающей скобки.
Результат выражения помещаем обратно в стек.

3⃣Финальная оценка выражения:
Продолжаем процесс до получения финального результата.
Если стек не пуст после обработки всех символов, оцениваем оставшиеся элементы как одно финальное выражение.

😎 Решение:

class Solution {
    private function evaluateExpr(&$stack) {
        if (empty($stack) || !is_int(end($stack))) {
            array_push($stack, 0);
        }

        $res = array_pop($stack);

        while (!empty($stack) && end($stack) !== ')') {
            $sign = array_pop($stack);

            if ($sign === '+') {
                $res += array_pop($stack);
            } else {
                $res -= array_pop($stack);
            }
        }
        return $res;
    }

    public function calculate($s) {
        $operand = 0;
        $n = 0;
        $stack = array();

        for ($i = strlen($s) - 1; $i >= 0; $i--) {
            $ch = $s[$i];

            if (ctype_digit($ch)) {
                $operand = pow(10, $n) * ((int) $ch) + $operand;
                $n += 1;
            } else if ($ch !== ' ') {
                if ($n !== 0) {
                    array_push($stack, $operand);
                    $n = 0;
                    $operand = 0;
                }
                if ($ch === '(') {
                    $res = $this->evaluateExpr($stack);
                    array_pop($stack);
                    array_push($stack, $res);
                } else {
                    array_push($stack, $ch);
                }
            }
        }

        if ($n !== 0) {
            array_push($stack, $operand);
        }

        return $this->evaluateExpr($stack);
    }
}

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