单栈

链接 labuladong

设计要点

  1. 新的符号会触发入栈，当i走到了算式的尽头（i == s.size()），也应该将前面的数字入栈，方便后续计算最终结果。
  2. 乘除法优先于加减法体现在，乘除法可以和栈顶的数结合，而加减法只能把自己放入栈。

  3. 因为括号具有递归性质，无论多少层括号嵌套，通过 calculate 函数递归调用自己。

    1. int index = 0;
    2. public int calculateCore(String s) {
    3.  Stack<Integer> stack = new Stack<>();
    5.  int num = 0;
    6.  char sign = '+';
    7.  while (index < s.length()) {
    8.      char c = s.charAt(index++);
    9.      if (isDigit(c)) {
    10.          num = 10 * num + (c - '0');
    11.      }
    12.      if (c == '(') {  //递归处理括号
    13.          num = calculateCore(s);
    14.      }
    15.      if ((!isDigit(c) && c != ' ') || index == s.length()) {
    16.          switch (sign) {
    17.              case '+':
    18.                  stack.push(num);
    19.                  break;
    20.              case '-':
    21.                  stack.push(-num);
    22.                  break;
    23.              case '*':  // 拿出前一个数字做对应运算
    24.                  stack.push(stack.pop() * num);
    25.                  break;
    26.              case '/':
    27.                  stack.push(stack.pop() / num);
    28.                  break;
    29.          }
    30.          sign = c; // 更新符号为当前符号，数字清零
    31.          num = 0;
    32.      }
    33.      if (c == ')') break; //退出递归
    34.  }
    36.  int res = 0;
    37.  while (!stack.isEmpty()) {
    38.      res += stack.pop();
    39.  }
    40.  return res;
    41. }
    42. private boolean isDigit(char c) {
    43.  return c >= '0' && c <= '9';
    44. }

    双栈

设计要点：

  1. 使用两个栈 nums 和 ops ：
    • nums ： 存放所有的数字
    • ops ：存放所有的数字以外的操作，+/- 也看做是一种操作
  2. 从前往后做，对遍历到的字符做分情况讨论：
    • 空格 : 跳过
    • ( : 直接加入 ops 中，等待与之匹配的 )
    • ) : 使用现有的 nums 和 ops 进行计算，直到遇到左边最近的一个左括号为止，计算结果放到 nums
    • 数字 : 从当前位置开始继续往后取，将整一个连续数字整体取出，加入 nums
    • +/- : 需要将操作放入 ops 中。在放入之前先把栈内可以算的都算掉，使用现有的 nums 和 ops 进行计算，直到没有操作或者遇到左括号，计算结果放到 nums
  3. 使用字典维护一个符号优先级
  1. class Solution {
  2.     Map<Character, Integer> map = new HashMap<>(){{
  3.         put('-', 1);
  4.         put('+', 1);
  5.         put('*', 2);
  6.         put('/', 2);
  7.         put('%', 2);
  8.         put('^', 3);
  9.     }};
  10.     public int calculate(String s) {
  11.         s = s.replaceAll(" ", ""); // 将所有的空格去掉
  12.         char[] cs = s.toCharArray();
  13.         int n = s.length();
  14.         Deque<Integer> nums = new ArrayDeque<>();
  15.         nums.addLast(0);  // 为了防止第一个数为负数，先往 nums 加个 0
  16.         Deque<Character> ops = new ArrayDeque<>();
  18.         for (int i = 0; i < n; i++) {
  19.             char c = cs[i];
  20.             if (c == '(') {       // 左括号直接入ops栈
  21.                 ops.addLast(c);
  22.             } else if (c == ')') { // 计算到最近一个左括号为止
  23.                 while (!ops.isEmpty()) {
  24.                     if (ops.peekLast() != '(') {
  25.                         calc(nums, ops);
  26.                     } else {
  27.                         ops.pollLast();
  28.                         break;
  29.                     }
  30.                 }
  31.             } else {
  32.                 if (isNumber(c)) {
  33.                     int u = 0;
  34.                     int j = i;
  35.                      // 将从 i 位置开始后面的连续数字整体取出，加入 nums
  36.                     while (j < n && isNumber(cs[j])) u = u * 10 + (cs[j++] - '0');
  37.                     nums.addLast(u);
  38.                     i = j - 1;
  39.                 } else {
  40.                     //为防止 () 内出现的首个字符为运算符,将 (- 替换为 (0-，(+ 替换为 (0+
  41.                     if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {
  42.                         nums.addLast(0);
  43.                     }
  44.                     while (!ops.isEmpty() && ops.peekLast() != '(') {
  45.                         char prev = ops.peekLast();
  46.                         if (map.get(prev) >= map.get(c)) {
  47.                             calc(nums, ops);
  48.                         } else {
  49.                             break;
  50.                         }
  51.                     }
  52.                     ops.addLast(c);
  53.                 }
  54.             }
  55.         }
  56.         // 有一个新操作要入栈时，先把栈内可以算的都算了
  57.         while (!ops.isEmpty() && ops.peekLast() != '(') calc(nums, ops);
  58.         return nums.peekLast();
  59.     }
  60.     void calc(Deque<Integer> nums, Deque<Character> ops) {
  61.         if (nums.isEmpty() || nums.size() < 2) return;
  62.         if (ops.isEmpty()) return;
  63.         int b = nums.pollLast(), a = nums.pollLast();
  64.         char op = ops.pollLast();
  65.         int ans = 0;
  66.         if (op == '+') {
  67.             ans = a + b;
  68.         } else if (op == '-') {
  69.             ans = a - b;
  70.         } else if (op == '*') {
  71.             ans = a * b;
  72.         } else if (op == '/') {
  73.             ans = a / b;
  74.         } else if (op == '^') {
  75.             ans = (int)Math.pow(a, b);
  76.         } else if (op == '%') {
  77.             ans = a % b;
  78.         }
  79.         nums.addLast(ans);
  80.     }
  81.     boolean isNumber(char c) {
  82.         return Character.isDigit(c);
  83.     }
  84. }