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);
	 }