Сложность: hard
Дана строка s, представляющая собой допустимое выражение, реализуйте базовый калькулятор для его вычисления и верните результат вычисления.
Примечание: нельзя использовать встроенные функции, которые оценивают строки как математические выражения, такие как eval().
Пример:
Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23
👨💻 Алгоритм:
1⃣Итерация строки выражения в обратном порядке:
Читаем выражение символ за символом, формируя операнды из нескольких цифр, если символ - цифра.
Сохраняем операнды в стек, как только встречаем нецифровой символ.
2⃣Обработка выражения внутри скобок:
Когда встречаем открывающую скобку '(', оцениваем выражение, удаляя операнды и операторы из стека до соответствующей закрывающей скобки.
Результат выражения помещаем обратно в стек.
3⃣Финальная оценка выражения:
Продолжаем процесс до получения финального результата.
Если стек не пуст после обработки всех символов, оцениваем оставшиеся элементы как одно финальное выражение.
😎 Решение:
class Solution {
public int evaluateExpr(Stack<Object> stack) {
if (stack.empty() || !(stack.peek() instanceof Integer)) {
stack.push(0);
}
int res = (int) stack.pop();
while (!stack.empty() && !((char) stack.peek() == ')')) {
char sign = (char) stack.pop();
if (sign == '+') {
res += (int) stack.pop();
} else {
res -= (int) stack.pop();
}
}
return res;
}
public int calculate(String s) {
int operand = 0;
int n = 0;
Stack<Object> stack = new Stack<Object>();
for (int i = s.length() - 1; i >= 0; i--) {
char ch = s.charAt(i);
if (Character.isDigit(ch)) {
operand = (int) Math.pow(10, n) * (int) (ch - '0') + operand;
n += 1;
} else if (ch != ' ') {
if (n != 0) {
stack.push(operand);
n = 0;
operand = 0;
}
if (ch == '(') {
int res = evaluateExpr(stack);
stack.pop();
stack.push(res);
} else {
stack.push(ch);
}
}
}
if (n != 0) {
stack.push(operand);
}
return evaluateExpr(stack);
}
}Ставь 👍 и забирай 📚 Базу знаний