Leetcode224 -- 基本计算器及其拓展

题目分析：

其实这个计算器的实现并不难，因为除了括号就剩下加减法嘛，括号肯定比加减法先执行，但是加减法是同级的，只是会改变数字的正负号而已，所以实现的逻辑并不是很难，我们只需要一个栈，来保存当前的符号sign即可.
遇到 '(' 就将当前符号入栈
遇到 ')' 就将当前符号弹出
遇到 '+' 就获取栈顶的符号（注意不是弹出），因为+不改变方向，所以从栈中取出来什么就是什么

遇到 '-'  也获取栈顶的符号（注意不是弹出），但是 - 会改变方向，所以给取出来的符号取反即可
遇到数字 就一直向下计算，直到下一个符号不是数字
最后把每个阶段算出来的结果相加就是答案

代码实现：

class Solution {public int calculate(String s) {Deque<Integer> stack = new ArrayDeque<>();stack.push(1);//这个栈中保存的是  符号int sign = 1; // 整数  -1   +1 代表当前的符号int res = 0,i = 0, n = s.length();while(i < n) {char c = s.charAt(i);switch(c) {case ' ':{i++;break;}case '+':{i++;sign = stack.peek();break;}case '-':{i++;sign = -stack.peek();break;}case '(':{i++;stack.push(sign);break;}case ')':{i++;stack.pop();break;}default:{long sum = 0;while(i < n && Character.isDigit(s.charAt(i))) {sum = sum * 10 + s.charAt(i) - '0';i++;}res += sum * sign;}}}return res;}
}

题目拓展：

这个拓展是来自于Ks的一道面试题，也没有明确说明，但默认能猜出来是考什么

区别及实现思路：

先说一下和Leetcode224的区别，就是多了*/这两个符号，并且*/个加减不属于一个级别，*/优先于+-，所以这里扯到了优先级的概念，并且还有（），为了保证括号内的表达式先被计算，我们定义( 的优先级是最低的，这样定义了优先级之后，就很清晰了
实现思路如下：
1.遇到数字直接加到操作数列表
2.遇到优先级，与最近加入的优先级做对比，
        2.1 如果大于最近的优先级，则将操作符直接加入到操作符列表，
        2.2 否则从操作列表里拿一个操作符和两个操作数进行计算，将计算的结果加到原来的列表  

        重复上面的操作直到找到一个比当前操作符优先级更低的操作符(在列表中)或者列表为空，再将当前的操作符加入到列表。

        由于括号的优先级最高，我们要让括号里面的操作符最先被计算，所以可以将'('的优先级设为最低
 

代码实现：

 public double calculateKs(String expression) {Deque<Double> numbers = new LinkedList<>();Deque<Character> operators = new LinkedList<>();int index = 0,len = expression.length();while(index < len) {char c = expression.charAt(index);if(c == '(') {operators.push(c);index++;}else if(c == ')') {//计算括号内的表达式while(operators.peek() != '(') {//单点操作，不是连点操作，所以得循环一直算，直到不符合条件为止compute(numbers,operators);}operators.pop();index++;}else if(isOperator(c)) {//处理操作符，考虑优先级while(!operators.isEmpty() && precedence(operators.peek())  >= precedence(c)) {//单点操作，不是连点操作，所以得循环一直算，直到不符合条件为止compute(numbers,operators);}operators.push(c);index++;}else if(Character.isDigit(c)) {//解析数字 -- 因为可能不只是一位数，所以要进行拼接StringBuilder sb = new StringBuilder();while(index < len && Character.isDigit(expression.charAt(index))) {sb.append(expression.charAt(index++));}numbers.push(Double.parseDouble(sb.toString()));}}//计算剩余的操作while(!operators.isEmpty()) {//单点操作，不是连点操作，所以得循环一直算compute(numbers,operators);}return numbers.pop();}public boolean isOperator(char c) {return c =='+' || c == '-' || c == '*' || c == '/';}//定义操作符的优先级public int precedence(char c) {if(c == '+' || c == '-') {return 1;}else if(c == '*' || c == '/') {return 2;}return 0;}//单点操作，不是连点操作，所以就算一次public void compute(Deque<Double> numbers,Deque<Character> operators) {if(numbers.size() < 2) {return;}double b = numbers.pop();double a = numbers.pop();char operator = operators.pop();double res = 0.0;switch(operator) {case '+':{res = a + b;break;}case '-':{res = a - b;break;}case '*':{res = a * b;break;}case '/':{res = a / b;break;}default:break;}numbers. Push(res);}