Java | LeetCode
Задача: 772. Basic Calculator III
Сложность: 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 {
private String evaluate(char operator, String first, String second) {
int x = Integer.parseInt(first);
int y = Integer.parseInt(second);
int res = 0;
if (operator == '+') {
res = x;
} else if (operator == '-') {
res = -x;
} else if (operator == '*') {
res = x * y;
} else {
res = x / y;
}
return Integer.toString(res);
}
public int calculate(String s) {
Stack<String> stack = new Stack<>();
String curr = "";
char previousOperator = '+';
s += "@";
Set<String> operators = new HashSet<>(Arrays.asList("+", "-", "*", "/"));
for (char c: s.toCharArray()) {
if (Character.isDigit(c)) {
curr += c;
} else if (c == '(') {
stack.push("" + previousOperator);
previousOperator = '+';
} else {
if (previousOperator == '*' || previousOperator == '/') {
stack.push(evaluate(previousOperator, stack.pop(), curr));
} else {
stack.push(evaluate(previousOperator, curr, "0"));
}
curr = "";
previousOperator = c;
if (c == ')') {
int currentTerm = 0;
while (!operators.contains(stack.peek())) {
currentTerm += Integer.parseInt(stack.pop());
}
curr = Integer.toString(currentTerm);
previousOperator = stack.pop().charAt(0);
}
}
}
int ans = 0;
for (String num: stack) {
ans += Integer.parseInt(num);
}
return ans;
}
}
Ставь 👍 и забирай 📚 Базу знаний
1 · 332 ·