- 算法:栈
- 1.用栈保存各部分计算的和
- 2.遍历表达式,使用 sign 变量记录运算符,初始化是 '+';使用 number 变量记录字符串中的数字部分的数字值是多少
- 2.0 遇到空格时跳过
- 2.1 遇到数字时继续遍历求这个完整的数字的值,保存到 number 中
- 2.2 遇到左括号时递归求这个括号里面的表达式的值
- 先遍历找到对应的右括号,因为可能里面还嵌有多对括号,使用一个变量 counterPartition 统计括号对数直到变量为 0
- 2.3 遇到运算符时或者到表达式末尾时,就去计算上一个运算符并把计算结果 push 进栈,然后保存新的运算符到 sign
- 如果是 + ,不要计算,push 进去
- 如果是 - ,push 进去负的当前数
- 如果是 ×、÷ ,pop 出一个运算数和当前数作计算
- 3.最后把栈中的结果求和即可
public int calculate(String s) { s = s.trim(); Deque<Integer> stack = new ArrayDeque<>(); int number = 0; char sign = '+'; char[] charArray = s.toCharArray(); for (int i = 0, n = charArray.length; i < n; i++) { char c = charArray[i]; if (c == ' ') { continue; } if (Character.isDigit(c)) { number = number * 10 + c - '0'; } if (c == '(') { int j = i + 1; int counterPartition = 1; while (counterPartition > 0) { if (charArray[j] == '(') { counterPartition++; } if (charArray[j] == ')') { counterPartition--; } j++; } number = calculate(s.substring(i + 1, j - 1)); i = j - 1; } if (!Character.isDigit(c) || i == n - 1) { if (sign == '+') { stack.push(number); } else if (sign == '-') { stack.push(-1 * number); } else if (sign == '*') { stack.push(stack.pop() * number); } else if (sign == '/') { stack.push(stack.pop() / number); } number = 0; sign = c; } } int ans = 0; while (!stack.isEmpty()) { ans += stack.pop(); } return ans; }