Basic Calculator

Сложная№224вычисление

Дано правильное выражение строкой: неотрицательные целые числа, + и −, скобки и пробелы; минус может стоять и сам по себе перед числом или скобкой. Нужно вычислить его, не пользуясь встроенным eval. Наш пример: "12-(3-(4+1))+2" — ответ 16.

224 Basic CalculatorРазбор · 1×

Пример: "12-(3-(4+1))+2". Под строкой — result, знак следующего числа и num — число, которое читаем; под ними стек, куда каждая "(" сохраняет result и знак перед ней.

12-(3-(4+1))+2result0sign1num0stack—
ещё не прочитанch, читаем сейчас; что изменил этот шагуже прочитансохранено в стеке"(", которая закрывается; снято на ")"

Начало: result 0, следующее число пойдёт со знаком +1, цифр нет, ничего не сохранено

01/40
сначала · назад · пуск · шаг
Скорость
1function calculate(s):
2 result = 0, sign = 1, num = 0, stack = empty stack
3 for each ch in s:
4 if ch is a digit:
5 num = num * 10 + digit(ch)
6 else if ch is "+" or ch is "-":
7 result = result + sign * num, num = 0
8 sign = 1 if ch is "+" else -1
9 else if ch is "(":
10 push result, then sign onto stack
11 result = 0, sign = 1
12 else if ch is ")":
13 result = result + sign * num, num = 0
14 result = result * pop from stack
15 result = result + pop from stack
16 return result + sign * num
состояние
s
"12-(3-(4+1))+2"
ch
–
num
0
sign
1
result
0
stack
[]
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Когда есть только + и −, значение — это сумма чисел, каждое со своим знаком. Число прибавляем, как только оно кончилось: на следующем знаке, на ")" или в конце строки.
  2. Скобка — отдельная сумма, поэтому на "(" сохраняем внешний result и знак перед скобкой, а внутри считаем с 0. На ")" умножаем внутреннюю сумму на этот знак и прибавляем обратно: последняя "(" закрывается первой, поэтому нужная пара сверху.
  3. Минус в самом начале или сразу после "(" не требует особого случая: он прибавляет num = 0 и ставит знак −1.

Сложность

Время O(n): каждый символ читаем один раз. Память O(n): по два числа в стеке на каждую одновременно открытую скобку, не больше n.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.