Сложность: medium
Дана строка s, представляющая выражение. Вычислите это выражение и верните его значение.
Целочисленное деление должно округляться к нулю.
Вы можете предположить, что данное выражение всегда является допустимым. Все промежуточные результаты будут находиться в диапазоне [-2^31, 2^31 - 1].
Примечание: Запрещено использовать какие-либо встроенные функции, которые вычисляют строки как математические выражения, такие как eval().
Пример:
Input: s = "3+2*2"
Output: 7
👨💻 Алгоритм:
1⃣Вместо использования стека, используем переменную lastNumber для отслеживания значения последнего вычисленного выражения.
2⃣Если операция сложения (+) или вычитания (-), добавляем lastNumber к результату вместо того, чтобы помещать его в стек. Текущее значение currentNumber будет обновлено на lastNumber для следующей итерации.
3⃣Если операция умножения (*) или деления (/), вычисляем выражение lastNumber * currentNumber и обновляем lastNumber с результатом выражения. Это значение будет добавлено к результату после сканирования всей строки.
😎 Решение:
class Solution:
def calculate(self, s: str) -> int:
length = len(s)
if length == 0:
return 0
currentNumber = 0
lastNumber = 0
result = 0
sign = '+'
for i in range(length):
currentChar = s[i]
if currentChar.isdigit():
currentNumber = (currentNumber * 10) + int(currentChar)
if not currentChar.isdigit() and not currentChar.isspace() or i == length - 1:
if sign == '+' or sign == '-':
result += lastNumber
lastNumber = currentNumber if sign == '+' else -currentNumber
elif sign == '*':
lastNumber *= currentNumber
elif sign == '/':
lastNumber //= currentNumber
sign = currentChar
currentNumber = 0
result += lastNumber
return result
Ставь 👍 и забирай 📚 Базу знаний