Сложность: hard
Дана строка s, представляющая собой допустимое выражение, реализуйте базовый калькулятор для его вычисления и верните результат вычисления.
Примечание: нельзя использовать встроенные функции, которые оценивают строки как математические выражения, такие как eval().
Пример:
Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23
👨💻 Алгоритм:
1⃣Итерация строки выражения в обратном порядке:
Читаем выражение символ за символом, формируя операнды из нескольких цифр, если символ - цифра.
Сохраняем операнды в стек, как только встречаем нецифровой символ.
2⃣Обработка выражения внутри скобок:
Когда встречаем открывающую скобку '(', оцениваем выражение, удаляя операнды и операторы из стека до соответствующей закрывающей скобки.
Результат выражения помещаем обратно в стек.
3⃣Финальная оценка выражения:
Продолжаем процесс до получения финального результата.
Если стек не пуст после обработки всех символов, оцениваем оставшиеся элементы как одно финальное выражение.
😎 Решение:
class Solution:
def evaluate_expr(self, stack):
if not stack or type(stack[-1]) == str:
stack.append(0)
res = stack.pop()
while stack and stack[-1] != ')':
sign = stack.pop()
if sign == '+':
res += stack.pop()
else:
res -= stack.pop()
return res
def calculate(self, s: str) -> int:
stack = []
n, operand = 0, 0
for i in range(len(s) - 1, -1, -1):
ch = s[i]
if ch.isdigit():
operand = (10**n * int(ch)) + operand
n += 1
elif ch != " ":
if n:
stack.append(operand)
n, operand = 0, 0
if ch == '(':
res = self.evaluate_expr(stack)
stack.pop()
stack.append(res)
else:
stack.append(ch)
if n:
stack.append(operand)
return self.evaluate_expr(stack)
Ставь 👍 и забирай 📚 Базу знаний