Задача: 772. Basic Calculator III
Сложность: medium

Реализуйте базовый калькулятор для вычисления простого строкового выражения.
Строка выражения содержит только неотрицательные целые числа, операторы '+', '-', '*', '/' и открывающие '(' и закрывающие скобки ')'. Целочисленное деление должно округляться к нулю.
Предполагается, что данное выражение всегда корректно. Все промежуточные результаты будут находиться в диапазоне [-2^31, 2^31 - 1].
Примечание: нельзя использовать встроенные функции для вычисления строк как математических выражений, такие как eval().

Пример:

Input: s = "1+1"
Output: 2

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

1⃣Определите вспомогательную функцию evaluate, которая принимает оператор и числовые аргументы. Заметьте, что эта функция идентична той, что представлена в подходе "Basic Calculator II". Инициализируйте несколько переменных: стек для хранения промежуточных результатов, curr для отслеживания текущего числа, которое мы строим, и previousOperator для отслеживания предыдущего оператора. Добавьте в строку s случайный символ, который не будет появляться во входных данных, например "@".

2⃣Итерация по входным данным. Для каждого символа c: если c является цифрой, добавьте его к curr. В противном случае, если c == '(', мы начинаем вычисление нового изолированного выражения. В этом случае сохраните previousOperator в стек и установите previousOperator = "+".

3⃣Если c является оператором, то необходимо вычислить значение curr. Используйте функцию evaluate, чтобы применить previousOperator к curr, и добавьте результат в стек. Затем сбросьте curr до нуля и обновите previousOperator = c. Если c == ')', это означает, что мы находимся в конце изолированного выражения и должны полностью его вычислить. Извлекайте из стека до тех пор, пока не достигнете оператора, суммируя все извлеченные числа в curr. Как только достигнете оператора, обновите previousOperator = stack.pop(). Верните сумму всех чисел в стеке.

😎 Решение:

class Solution {
    evaluate(operator, first, second) {
        const x = parseInt(first)
        const y = parseInt(second)
        let res = 0

        if (operator === '+') {
            res = x
        } else if (operator === '-') {
            res = -x
        } else if (operator === '*') {
            res = x * y
        } else {
            res = Math.trunc(x / y)
        }

        return res.toString()
    }

    calculate(s) {
        const stack = []
        let curr = ""
        let previousOperator = '+'
        s += "@"
        const operators = new Set(["+", "-", "*", "/"])

        for (const c of s) {
            if (/\d/.test(c)) {
                curr += c
            } else if (c === '(') {
                stack.push(previousOperator)
                previousOperator = '+'
            } else {
                if (previousOperator === '*' || previousOperator === '/') {
                    stack.push(this.evaluate(previousOperator, stack.pop(), curr))
                } else {
                    stack.push(this.evaluate(previousOperator, curr, "0"))
                }

                curr = ""
                previousOperator = c
                if (c === ')') {
                    let currentTerm = 0
                    while (!operators.has(stack[stack.length - 1])) {
                        currentTerm += parseInt(stack.pop())
                    }

                    curr = currentTerm.toString()
                    previousOperator = stack.pop()
                }
            }
        }

        let ans = 0
        for (const num of stack) {
            ans += parseInt(num)
        }

        return ans
    }
}

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