basic calculator系列题目：(可以作为模板题，记住)
224. 基本计算器 - 力扣（LeetCode） [hard]
想法：
-
中缀表达式求值。数据结构中栈的应用
- 中缀转后缀。后缀能去掉括号。a + (b + c)*d ==》
abc+d*+ - 后缀表达式求值:
abc+d*+ - 要考虑表达式的优先级，怎么处理括号。 括号的优先级，不知道怎么处理。
- 处理特殊情况： 1 + (-2)这种情况
- 中缀转后缀。后缀能去掉括号。a + (b + c)*d ==》
-
总结1：这题处理特例
1-( -2)太恶心了。 -
总结2：对于运算符和符号，分两类，运算符有优先级，左右括号特殊处理一下。
-
代码技巧1：evaluate函数，直接传入两个stack，然后计算一次。不加返回值。这种写法比传入numStack和opCode，然后返回计算结果好。因为后者还需要在调用处，把结果push到栈里。
-
代码技巧2：parse 数字时，使用循环直接解析，而不要重用外层的循环。这样更清晰一点。
class Solution {
public int calculate(String s) {
Deque<Integer> numStack = new ArrayDeque<>(); // 存操作数的栈
Deque<Character> opStack = new ArrayDeque<>(); // 存运算符的栈
// 原则：能算就算
// 将运算符+-*/ 和 ()分成两类。运算符定义优先级，括号特殊处理
int prev = -1;
for(int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == ' ') continue;
else if (Character.isDigit(ch)) {
// parse the number use a loop
int j = i, num = 0;
for (; j < s.length() && Character.isDigit(s.charAt(j)); j++) {
num = num * 10 + (s.charAt(j) - '0');
}
numStack.push(num);
i = j - 1;
} else { // operation code
if (ch == '(') { //压栈
opStack.push(ch);
} else if (ch == ')') {
while (opStack.peek() != '(') {
// evaluate the stack
evaluate(numStack, opStack);
}
opStack.pop();
} else {
if (prev == -1 || s.charAt(prev) == '+' || s.charAt(prev) == '-' || s.charAt(prev) == '(') {
numStack.push(0);
}
// 因为只有+-，优先级一样，不需要比较优先级了
while (!opStack.isEmpty() && opStack.peek() != '(') {
evaluate(numStack, opStack);
}
opStack.push(ch);
}
}
prev = i;
}
while (!opStack.isEmpty()) {
evaluate(numStack, opStack);
}
return numStack.pop();
}
void evaluate(Deque<Integer> numStack, Deque<Character> opStack) {
int b = numStack.pop();
int a = 0;
if (!numStack.isEmpty())
a = numStack.pop();
char opCode = opStack.pop();
if (opCode == '+') {
numStack.push(a + b);
} else if (opCode == '-') {
numStack.push(a - b);
}
}
}
复杂度分析：
- 时间：O(n), 字符串遍历一遍，最多有n个元素入栈和出栈， 空间O(n)
官方答案的解法：
- 由于字符串除了数字与括号外，只有加号和减号两种运算符。因此，如果展开表达式中所有的括号，则得到的新表达式中，数字本身不会发生变化，只是每个数字前面的符号会发生变化。
链接：https://leetcode.cn/problems/basic-calculator/solution/ji-ben-ji-suan-qi-by-leetcode-solution-jvir/
227. 基本计算器 II - 力扣（LeetCode） 【mid】
直接套用上面的模板，修改下优先级即可。这题没有括号，也没有单目运算符，所以是mid级别，不是很难。
class Solution {
public int calculate(String s) {
Deque<Integer> numStack = new ArrayDeque<>();
Deque<Character> opStack = new ArrayDeque<>();
for(int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == ' ') continue;
if (Character.isDigit(ch)) {
int num = 0, j = i;
for(; j < s.length() && Character.isDigit(s.charAt(j)); j++) {
num = num * 10 + (s.charAt(j) - '0');
}
numStack.push(num);
i = j - 1;
} else {
while (!opStack.isEmpty() && getPriority(ch) <= getPriority(opStack.peek())) {
evaluate(numStack, opStack);
}
opStack.push(ch);
}
}
while (!opStack.isEmpty()) {
evaluate(numStack, opStack);
}
return numStack.peek();
}
void evaluate(Deque<Integer> numStack, Deque<Character> opStack) {
int a = numStack.pop(), b = numStack.pop();
char op = opStack.pop();
int res = 0;
if (op == '+') res = b + a;
else if (op == '-') res = b - a;
else if (op == '*') res = b * a;
else if (op == '/') res = b / a;
numStack.push(res);
}
int getPriority(char ch) {
if (ch == '+' || ch == '-') return 1;
if (ch == '*' || ch == '/') return 2;
return 0;
}
}
/*
思路：
1. 中缀表达式求值，使用两个stack，一个numStack, 一个opStack
2. 原则，能算则算。 a + b + c --》 先计算a+b, 然后入栈
a+b*c 不能先算a+b 因此，当后面*优先级高于栈顶时，直接入栈。
操作数直接入栈。
操作符： 如果当前操作符比栈顶高，入栈。否则，先计算栈顶。
当表达式遍历完成，再处理opStack，每次取出一个op，然后从numStack取出两个数计算，将结果压到numStack中
最后结果是numStack的栈顶元素
*/
772. 基本计算器 III - 力扣（LeetCode） 【hard】
- 使用上面的模板。同样这题没有空格，也没有恶心的单目运算符，所以还好。
class Solution {
public int calculate(String s) {
Deque<Integer> numStack = new ArrayDeque<>();
Deque<Character> opStack = new ArrayDeque<>();
for(int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == ' ') continue;
if (Character.isDigit(ch)) {
int num = 0, j = i;
for(; j < s.length() && Character.isDigit(s.charAt(j)); j++) {
num = num * 10 + (s.charAt(j) - '0');
}
numStack.push(num);
i = j - 1;
} else {
if (ch == '(') {
opStack.push(ch);
} else if (ch == ')') {
while (opStack.peek() != '(') {
evaluate(numStack, opStack);
}
opStack.pop();
} else {
while (!opStack.isEmpty() && opStack.peek() != '(' && getPriority(ch) <= getPriority(opStack.peek())) {
evaluate(numStack, opStack);
}
opStack.push(ch);
}
}
}
while (!opStack.isEmpty()) {
evaluate(numStack, opStack);
}
return numStack.peek();
}
void evaluate(Deque<Integer> numStack, Deque<Character> opStack) {
int a = numStack.pop(), b = numStack.pop();
char op = opStack.pop();
int res = 0;
if (op == '+') res = b + a;
else if (op == '-') res = b - a;
else if (op == '*') res = b * a;
else if (op == '/') res = b / a;
numStack.push(res);
}
int getPriority(char ch) {
if (ch == '+' || ch == '-') return 1;
if (ch == '*' || ch == '/') return 2;
return 0;
}
}
770. 基本计算器 IV - 力扣（LeetCode） [hard]
这个有变量，似乎跟前面不太一样，很难。TODO。
标签：numStack,26,ch,opStack,中缀,int,else,num,求值 From： https://www.cnblogs.com/xianzhon/p/17435606.html