Задача: 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 {
    private func evaluate(_ operator: Character, _ first: String, _ second: String) -> String {
        let x = Int(first)!
        let y = Int(second)!
        var res = 0
        
        switch operator {
        case "+":
            res = x
        case "-":
            res = -x
        case "*":
            res = x * y
        default:
            res = x / y
        }
        
        return String(res)
    }
    
    func calculate(_ s: String) -> Int {
        var stack = [String]()
        var curr = ""
        var previousOperator: Character = "+"
        let s = s + "@"
        let operators: Set<Character> = ["+", "-", "*", "/"]
        
        for c in s {
            if c.isNumber {
                curr += String(c)
            } else if c == "(" {
                stack.append(String(previousOperator))
                previousOperator = "+"
            } else {
                if previousOperator == "*" || previousOperator == "/" {
                    stack.append(evaluate(previousOperator, stack.removeLast(), curr))
                } else {
                    stack.append(evaluate(previousOperator, curr, "0"))
                }
                
                curr = ""
                previousOperator = c
                if c == ")" {
                    var currentTerm = 0
                    while !operators.contains(stack.last!) {
                        currentTerm += Int(stack.removeLast())!
                    }
                    
                    curr = String(currentTerm)
                    previousOperator = stack.removeLast().first!
                }
            }
        }
        
        var ans = 0
        for num in stack {
            ans += Int(num)!
        }

        return ans
    }
}

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