Implement a basic calculator to evaluate a simple expression string.

    The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces ``.

    Example 1:

    1. Input: "1 + 1"
    2. Output: 2

    Example 2:

    1. Input: " 2-1 + 2 "
    2. Output: 3

    Example 3:

    1. Input: "(1+(4+5+2)-3)+(6+8)"
    2. Output: 23

    Note:

    • You may assume that the given expression is always valid.
    • Do not use the eval built-in library function.

    题意

    计算只包含”+”、”-“、”(“、”)”和非负整数的字符串的值。

    思路

    正向遍历：从前向后遍历字符串，如果是数字则将其加入到结果res中；如果是操作符则对应变更sign的值；如果是’(‘则将当且结果res和sign依次压入栈中，重置res为0、sign为1；如果是’)’，说明当前括号中所有值已经计算完毕，将其与栈中元素相加(减)。

    反向遍历：从后向前遍历字符串，如果是数字则压入操作数栈；如果是’)’、’+’、’-‘则压入操作符栈；如果是’(‘则从操作数栈(注意前后顺序，先出栈的就是在前面的操作数)和操作符栈出栈，计算结果后重新压入操作数栈，直到将对应的’)’出栈。

    代码实现 - 正向遍历

    1. class Solution {
    2.     public int calculate(String s) {
    3.         int res = 0, sign = 1;
    4.         Deque<Integer> stack = new ArrayDeque<>();
    5.         for (int i = 0; i < s.length(); i++) {
    6.             char c = s.charAt(i);
    7.             if (c == ' ') {
    8.                 continue;
    9.             } else if (c == '+' || c == '-') {
    10.                 sign = c == '+' ? 1 : -1;
    11.             } else if (c == '(') {
    12.                 stack.push(res);
    13.                 stack.push(sign);
    14.                 res = 0;
    15.                 sign = 1;
    16.             } else if (c == ')') {
    17.                 res *= stack.pop();
    18.                 res += stack.pop();
    19.             } else {
    20.                 int num = c - '0';
    21.                   // 计算出完整的数字
    22.                 while (i + 1 < s.length() && s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9') {
    23.                     num = num * 10 + s.charAt(i + 1) - '0';
    24.                     i++;
    25.                 }
    26.                 res += sign * num;
    27.             }
    28.         }
    29.         return res;
    30.     }
    31. }

    代码实现 - 反向遍历

    1. class Solution {
    2.     public int calculate(String s) {
    3.         Deque<Character> ops = new ArrayDeque<>();                    // 操作符栈
    4.         Deque<Integer> nums = new ArrayDeque<>();                    // 操作数栈
    6.         for (int i = s.length() - 1; i >= 0; i--) {
    7.             char c = s.charAt(i);
    8.             if (c == ' ') {
    9.                 continue;
    10.             } else if (c == ')') {
    11.                 ops.push(c);
    12.             } else if (c == '(') {
    13.                 char op = ops.pop();
    14.                 while (op != ')') {
    15.                     int a = nums.pop(), b = nums.pop();
    16.                     nums.push(a + (op == '+' ? b : -b));
    17.                     op = ops.pop();
    18.                 }
    19.             } else if (c == '+' || c == '-') {
    20.                 ops.push(c);
    21.             } else {
    22.                   // 需要先将连带的数字全部找出，组合成对应的整数
    23.                 int num = c - '0';
    24.                 int tens = 10;
    25.                 while (i - 1 >= 0 && s.charAt(i - 1) >= '0' && s.charAt(i - 1) <= '9') {
    26.                     num = (s.charAt(i - 1) - '0') * tens + num;
    27.                     i--;
    28.                     tens *= 10;
    29.                 }
    30.                 nums.push(num);
    31.             }
    32.         }
    34.         while (nums.size() != 1) {
    35.             int a = nums.pop(), b = nums.pop();
    36.             char op = ops.pop();
    37.             nums.push(a + (op == '+' ? b : -b));
    38.         }
    40.         return nums.pop();
    41.     }
    42. }