P178 支持括号与加减法的计算器

描述#

这个题目说的是，给你一个字符串表达式，你要实现一个简易计算器，对它进行求值。

表达式中只包含非负整数、(、)、+、- 运算符以及空格。

注意，给出的表达式总是有效的，并且不允许使用内置的字符串求值函数。

比如说，给你的表达式为：
"2-(1 -(2 + 1)) "
这个表达式求值结果等于 4，因此你要返回 4。

相关视频：简易计算器

代码#

public class AlgoCasts {

  // Time: O(n), Space: O(n)
  public int calculateTwoStack(String s) {
    int n = s.length();
    Stack<Integer> nums = new Stack<>();
    Stack<Character> ops = new Stack<>();
    ops.push('(');

    for (int i = 0; i <= n; ++i) {
      if (i == n || s.charAt(i) == ')') {
        int sum = 0, num = nums.pop();
        while (ops.peek() != '(') {
          if (ops.pop() == '-') num = -num;
          sum += num;
          num = nums.pop();
        }
        sum += num;
        nums.push(sum);
        ops.pop();
      } else if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
        int num = s.charAt(i) - '0';
        while (i+1 < n && s.charAt(i+1) >= '0' && s.charAt(i+1) <= '9') {
          num = num * 10 + s.charAt(i+1) - '0';
          ++i;
        }
        nums.push(num);
      } else if (s.charAt(i) == '+' || s.charAt(i) == '-' || s.charAt(i) == '(') {
        ops.push(s.charAt(i));
      }
    }
    return nums.peek();
  }

  // Time: O(n), Space: O(n)
  public int calculateOneStack(String s) {
    int sum = 0, op = 1, n = s.length();
    Stack<Integer> ops = new Stack<>();
    ops.push(1);

    for (int i = 0; i < n; ++i) {
      if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
        int num = s.charAt(i) - '0';
        while (i+1 < n && s.charAt(i+1) >= '0' && s.charAt(i+1) <= '9') {
          num = num * 10 + s.charAt(i+1) - '0';
          ++i;
        }
        sum += ops.peek() * op * num;
      } else if (s.charAt(i) == '(') {
        ops.push(ops.peek() * op);
        op = 1;
      } else if (s.charAt(i) == ')') ops.pop();
      else if (s.charAt(i) == '+') op = 1;
      else if (s.charAt(i) == '-') op = -1;
    }
    return sum;
  }

}