题目：
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
示例 1：
输入：s = "3+2*2"
输出：7
示例 2：
输入：s = " 3/2 "
输出：1
示例 3：
输入：s = " 3+5 / 2 "
输出：5
提示：
- 1 <= s.length <= 3 * 105
- s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
- s 表示一个 有效表达式
- 表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
- 题目数据保证答案是一个 32-bit 整数
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/basic-calculator-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
这道题和224.基本计算器思路一致，利用栈的特点来解决
建立双栈：
- 使用栈nums：来存放操作数；
- 使用栈ops：来存放操作符。
与224题不同的是多了几个操作符，且上一题中操作符的优先级一样，这一题有优先级的差别，就利用哈希表来存储优先级，键为操作符，值为优先级，优先级按照数学运算中操作符的优先级来限定。
将字符串s中的所有空格去掉，并转换成字符数组，从前往后进行遍历，根据当前遇到的字符进行分情况讨论：
- 遇到左括号 (：就将其加入ops中,等待与之匹配的右括号 );
- 遇到右括号 )：当ops中不为空时，还没遇到与之匹配的左括号时，就将已有的nums和ops进行计算，将结果放入nums中，当遇到与之匹配的左括号时，就将左括号弹出；
- 遇到数字时：就将当前连续的整数取出，放入nums中；
- 有新的操作符入栈时，如果ops栈顶操作符优先级 >= 新的操作符的优先级 ，就计算栈内元素，直到操作符为空或者左括号就继续将操作符入栈，后续遍历完s,再进行计算剩下的。
注意点（有一点改变）：
1.第一个数可能为负数（-6）：这样第一个操作符可能被认为 '减号',计算时没有前面的数与之计算，可以再最开始就加入一个0，变成 0-6这样结果也正好为-6;
2.为了防止括号内出现的首个字符为运算符，当遇到左括号 ( 时，就添加一个0，使之变为 ( 0，其实与224题效果一样，但是我觉得这个更好利于我理解一点。
代码：
1 class Solution {
2 public int calculate(String s) {
3 Deque<Integer> nums = new ArrayDeque<>();
4 Deque<Character> ops = new ArrayDeque<>();
5 Map<Character, Integer> map = new HashMap<>(){{
6 put('+', 1);
7 put('-', 1);
8 put('*', 2);
9 put('/', 2);
10 put('%', 2);
11 put('^', 3);
12 }};
13 s = s.replaceAll(" ", "");
14 char[] cs = s.toCharArray();
15 int n = cs.length;
16 for(int i = 0; i < n; i++){
17 char c = cs[i];
18 //当前遇到左括号，就加入操作符栈
19 if(c == '('){
20 ops.addLast(c);
21 }else if(c == ')'){
22 //遇到右括号，就计算括号内的数
23 while(!ops.isEmpty()){
24 if(ops.pollLast() != '('){
25 calc(nums, ops);
26 }else{
27 //计算完括号内的数就弹出左括号
28 ops.pollLast();
29 }
30 }
31 }else{
32 if(isNum(c)){
33 int num = 0;
34 int j = i;
35 //取出当前整数
36 while(j < n && isNum(cs[j])){
37 num = num * 10 + (cs[j++] - '0');
38 }
39 nums.addLast(num);
40 i = j -1;
41 }else{
42 //处理遇到左括号时，应该变成(0
43 if(i > 0 && cs[i - 1] == '('){
44 nums.addLast(0);
45 }
46 //如果当前c是操作符就看当前操作符的优先级是否小于等于栈内的优先级
47 //如果是，才计算栈内的
48 while(!ops.isEmpty() && ops.peekLast() != '('){
49 char preop = ops.peekLast();
50 if(map.get(preop) >= map.get(c)){
51 calc(nums, ops);
52 }else{
53 break;
54 }
55 }
56 ops.addLast(c);
57 }
58 }
59 }
60 //遍历完后算剩下的所有
61 while(!ops.isEmpty()){
62 calc(nums, ops);
63 }
64 return nums.peekLast();
65 }
66 //计算方法
67 void calc(Deque<Integer> nums, Deque<Character> ops){
68 //如果操作数为空或者长度小于2
69 if(nums.isEmpty() || nums.size() < 2) return;
70 //如果操作符为空
71 if(ops.isEmpty()) return;
72 int b = nums.pollLast(), a = nums.pollLast();
73 char c = ops.pollLast();
74 int res = 0;
75 switch (c){
76 case '+':
77 res = a + b;
78 break;
79 case '-':
80 res = a - b;
81 break;
82 case '*':
83 res = a * b;
84 break;
85 case '/':
86 res = a / b;
87 break;
88 case '%':
89 res = a % b;
90 break;
91 case '^':
92 res = (int) Math.pow(a, b);
93 break;
94 }
95 nums.addLast(res);
96 }
97 //判断是否为数字
98 boolean isNum(char num){
99 return Character.isDigit(num);
100 }
101 }
小知识：
1.在数学中优先级：与+、-、*、/相比，幂(^)的优先级最高，最先算。
2.java中运算符的优先级：
