JavaScript | LeetCode

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

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

Пример:

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

👨‍💻

Алгоритм:

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

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

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

😎

Решение:

class Solution {
    evaluateExpr(stack) {
        if (stack.length === 0 || typeof stack[stack.length - 1] !== 'number') {
            stack.push(0);
        }

        let res = stack.pop();

        while (stack.length !== 0 && stack[stack.length - 1] !== ')') {
            let sign = stack.pop();

            if (sign === '+') {
                res += stack.pop();
            } else {
                res -= stack.pop();
            }
        }
        return res;
    }

    calculate(s) {
        let operand = 0;
        let n = 0;
        let stack = [];

        for (let i = s.length - 1; i >= 0; i--) {
            let ch = s[i];

            if (/\d/.test(ch)) {
                operand = Math.pow(10, n) * (parseInt(ch)) + operand;
                n += 1;
            } else if (ch !== ' ') {
                if (n !== 0) {
                    stack.push(operand);
                    n = 0;
                    operand = 0;
                }
                if (ch === '(') {
                    let res = this.evaluateExpr(stack);
                    stack.pop();
                    stack.push(res);
                } else {
                    stack.push(ch);
                }
            }
        }

        if (n !== 0) {
            stack.push(operand);
        }

        return this.evaluateExpr(stack);
    }
}

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

Please open Telegram to view this post