Сложность: hard
Дана строка s, представляющая собой допустимое выражение, реализуйте базовый калькулятор для его вычисления и верните результат вычисления.
Примечание: нельзя использовать встроенные функции, которые оценивают строки как математические выражения, такие как eval().
Пример:
Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23
👨💻 Алгоритм:
1⃣Итерация строки выражения в обратном порядке:
Читаем выражение символ за символом, формируя операнды из нескольких цифр, если символ - цифра.
Сохраняем операнды в стек, как только встречаем нецифровой символ.
2⃣Обработка выражения внутри скобок:
Когда встречаем открывающую скобку '(', оцениваем выражение, удаляя операнды и операторы из стека до соответствующей закрывающей скобки.
Результат выражения помещаем обратно в стек.
3⃣Финальная оценка выражения:
Продолжаем процесс до получения финального результата.
Если стек не пуст после обработки всех символов, оцениваем оставшиеся элементы как одно финальное выражение.
😎 Решение:
class Solution {
func evaluateExpr(_ stack: inout [Any]) -> Int {
if stack.isEmpty || !(stack.last is Int) {
stack.append(0)
}
var res = stack.removeLast() as! Int
while !stack.isEmpty && !(stack.last as! Character == ")") {
let sign = stack.removeLast() as! Character
if sign == "+" {
res += stack.removeLast() as! Int
} else {
res -= stack.removeLast() as! Int
}
}
return res
}
func calculate(_ s: String) -> Int {
var operand = 0
var n = 0
var stack: [Any] = []
for ch in s.reversed() {
if ch.isWholeNumber {
operand = Int(pow(10.0, Double(n))) * (ch.wholeNumberValue!) + operand
n += 1
} else if ch != " " {
if n != 0 {
stack.append(operand)
n = 0
operand = 0
}
if ch == "(" {
let res = evaluateExpr(&stack)
stack.removeLast()
stack.append(res)
} else {
stack.append(ch)
}
}
}
if n != 0 {
stack.append(operand)
}
return evaluateExpr(&stack)
}
}Ставь 👍 и забирай 📚 Базу знаний