Сложность: 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:
def evaluate(self, operator, first, second):
x = int(first)
y = int(second)
if operator == '+':
return str(x)
elif operator == '-':
return str(-x)
elif operator == '*':
return str(x * y)
else:
return str(x // y)
def calculate(self, s: str) -> int:
stack = []
curr = ""
previousOperator = '+'
s += "@"
operators = set("+-*/")
for c in s:
if c.isdigit():
curr += c
elif c == '(':
stack.append(previousOperator)
previousOperator = '+'
else:
if previousOperator in "*/":
stack.append(self.evaluate(previousOperator, stack.pop(), curr))
else:
stack.append(self.evaluate(previousOperator, curr, "0"))
curr = ""
previousOperator = c
if c == ')':
currentTerm = 0
while stack[-1] not in operators:
currentTerm += int(stack.pop())
curr = str(currentTerm)
previousOperator = stack.pop()
return sum(int(num) for num in stack)
Ставь 👍 и забирай 📚 Базу знаний