# 括号与数学表达式的计算

### 往上加运算符也好，加括号也好，删除括号也好，最稳妥的方式都是 带 StringBuilder 从头扫的 DFS + Backtracking.

### 在没有任何优先级后顾之忧的情况下，可以以操作符为分界线，Divide & Conquer. 否则得存每个 subproblem 的前后缀用于做 join.

### 有乘法优先级顾虑时，需要在 dfs 参数里传上一次操作的值，用于恢复和重新计算；连续多个乘法可以自动叠加。

### 在只有一种括号的情况下，维护 left / right count 就可以 one-pass 知道到底有几个 left / right 括号没正确匹配

### Dijkstra 的 Shunting-Yard 算法是生成 RPN 的大杀器，也是 calculator 类问题的通解。

## [Different Ways to Add Parentheses](https://leetcode.com/problems/different-ways-to-add-parentheses/)

先说一个自己的做法，写的是搜索，对于每一个 input string ，我们扫描并建立两个 list; 一个是 operands，一个是 operators. 每次 dfs 的时候挑一对数字和一个操作符，计算，修改 list 做 dfs，返回之后再把 list 改回来。

过了 15/25 个 test case 之后卡在了 "2\*3-4\*5" 上面，原因是多了一个额外的 -14，因为两个 subproblem 加括号的方式是一样的，顺序不同而已。

所以暴力搜索的问题在于，如果前面和后面加括号的方式是一样的，需要额外手段来判断 “重复” 。

### 而DFS 中想 cache 一个 List<>，远远不如 String 方便。

如果实在追求暴力到底，就干脆对每一个状态都搞序列化，记录当前的 operands & operators ，遇到重复的状态就直接返回了。

![](https://2030049235-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MUt7Y8-dUQcwNZkL6dz%2Fsync%2F40cfb6fadcf5cfb35981a666ec98f16327cd6689.jpg?generation=1614792531215022\&alt=media)

因此为了避免 dfs + backtracking 可能遇到的 overlap subproblem 返回多个结果的问题，可以先直接 divide & conquer，因为这个搜索结构是树状的，天生的 disjoint.

根据这个思想，我们可以以“操作符”为分隔，借鉴编译器和 reverse polish notation 中的 "expression tree" 来进行计算，结构如下：

![](https://2030049235-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MUt7Y8-dUQcwNZkL6dz%2Fsync%2Fee1c37b54c071db9863419b4913623d804be365f.jpg?generation=1614792531290468\&alt=media)

这样左右子树都进行的完美的分隔，而且应为 input 为 string ，也非常容易对子问题进行记忆化搜索。

Divide & Conquer, 8ms，超过 41.50%.

```java
public class Solution {
    public List<Integer> diffWaysToCompute(String input) {

        List<Integer> rst = new ArrayList<>();

        for(int i = 0; i < input.length(); i++){
            if(!Character.isDigit(input.charAt(i))){
                char operator = input.charAt(i);

                List<Integer> left = diffWaysToCompute(input.substring(0, i));
                List<Integer> right = diffWaysToCompute(input.substring(i + 1));

                for(int num1 : left){
                    for(int num2 : right){
                        if(operator == '+') rst.add(num1 + num2);
                        if(operator == '-') rst.add(num1 - num2);
                        if(operator == '*') rst.add(num1 * num2);
                    }
                }
            }
        }

        if(rst.size() == 0) rst.add(Integer.parseInt(input));

        return rst;
    }
}
```

### 带记忆化搜索，3ms，超过 91.61%

```java
public class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        return helper(input, new HashMap<String, List<Integer>>());
    }

    private List<Integer> helper(String str, HashMap<String, List<Integer>> map){
        if(map.containsKey(str)) return map.get(str);

        List<Integer> list = new ArrayList<>();

        for(int i = 0; i < str.length(); i++){
            char chr = str.charAt(i);
            if(!Character.isDigit(chr)){
                List<Integer> leftList = helper(str.substring(0, i), map);
                List<Integer> rightList = helper(str.substring(i + 1), map);

                for(int leftNum : leftList){
                    for(int rightNum : rightList){
                        if(chr == '+') list.add(leftNum + rightNum);
                        if(chr == '-') list.add(leftNum - rightNum);
                        if(chr == '*') list.add(leftNum * rightNum);
                    }
                }
            }
        }

        if(list.size() == 0) list.add(Integer.parseInt(str));

        map.put(str, list);
        return list;
    }
}
```

## [Longest Valid Parentheses](https://leetcode.com/problems/longest-valid-parentheses/)

首先最容易想到的是 naive 的 O(n^2) 解法，即以每一个 '(' 为起点向右扫，看到 '(' count ++，看到 ')' count -- ，什么时候 count = 0 代表当前 substring 是有效的，count 为负则直接 break.

### 注意这招只在只有一种括号的时候有效，不能用来做 "Valid Parentheses"，会在 "(\[)]" 这种 test case 上挂掉。

显然，因为时间复杂度过高这么写不能 AC，因为重复扫描实在太多了。

```java
public class Solution {
    public int longestValidParentheses(String s) {
        if(s == null || s.length() == 0) return 0;

        int n = s.length();
        int max = 0;
        for(int i = 0; i < n; i++){
            char chr = s.charAt(i);
            if(chr == '('){
                int count = 1;
                int ptr = i + 1;
                while(ptr < n){
                    if(s.charAt(ptr) == '(') count ++;
                    if(s.charAt(ptr) == ')') count --;

                    if(count == 0) max = Math.max(max, ptr - i + 1);
                    if(count < 0) break;

                    ptr ++;
                }
            }
        }

        return max;
    }
}
```

仔细思考一下我们如何定义 "Valid Parenthese"，还有他们都长什么样。

### Valid Parenthese 只有可能是这两种情况；

* **以一对括号为 "kernel" ，向外扩散的，如 ((()))**
* **多个 "kernel" 扩张出现，相互连续的，如 (())()(())**

参考了 LC 论坛的一种解法，非常巧妙，利用了这样的一个隐藏性质：

* **用 Stack 做常规括号匹配，字符串扫描完毕之后，还存留在 Stack 中的 index 都是无法匹配的字符。**
* **如果字符串正常从左向右扫的话，这个 Stack 中的元素 index 还是排好序的，元素 index 之间的 gap，就代表着可以匹配的括号。**
* **同时要注意考虑字符串最两端作为起点和终点的可能性，用最右端做初始化，用最左端做收尾。**

于是就有了下面这个 O(n) 的代码，空间复杂度为 O(n / 2);

```java
public class Solution {
    public int longestValidParentheses(String s) {
        if(s == null || s.length() == 0) return 0;
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '(') stack.push(i);
            else if(!stack.isEmpty() && s.charAt(stack.peek()) == '(') stack.pop();
            else stack.push(i);
        }
        // Whole string is matched
        //if(stack.isEmpty()) return s.length();

        int rightEnd = s.length();
        int max = 0;
        while(!stack.isEmpty()){
            int cur = stack.pop();
            max = Math.max(max, rightEnd - cur - 1);
            rightEnd = cur;
        }
        max = Math.max(max, rightEnd);

        return max;
    }
}
```

另一种解法是用 DP，空间占用大一倍，但是速度快，思路上非常接近于 Palindrome Partitioning.

* **dp\[i] = 以 i 结尾的括号的最长 valid parenthese 长度**
  * **对于 '(' 显然 dp\[i] = 0;**
  * **对于 ')' ，就需要计算一下了。**
* **先读 dp\[i - 1] 的长度，然后根据长度找到最左面的目标位置 leftPos，看看是不是 '('，如果是，就可以 dp\[i] = dp\[i - 1] + 2 了，代表可以连续构造；**
* **另一种情况是多个独立的括号序列相邻，所以每次如果当前位置可以构造括号，要再找一下 dp\[leftPos - 1] 的长度，把相邻序列串起来。**

速度超过85.05% \~

```java
  public class Solution {
    public int longestValidParentheses(String s) {
        if(s == null || s.length() == 0) return 0;
        int n = s.length();
        int[] dp = new int[n]; // dp[i] = Maximum valid parentheses length ends with i
        dp[0] = 0;
        int max = 0;

        for(int i = 1; i < s.length(); i++){
            if(s.charAt(i) == ')'){
                int len = dp[i - 1];
                int leftPos = i - len - 1;

                if(leftPos >= 0 && s.charAt(leftPos) == '(') {
                    dp[i] = dp[i - 1] + 2;
                    if(leftPos - 1 >= 0) dp[i] += dp[leftPos - 1];
                } else {
                    dp[i] = 0;
                }

                max = Math.max(max, dp[i]);
            }
        }

        return max;
    }
}
```

## (FB) 简化版，Remove Invalid Parenthese

<http://www.1point3acres.com/bbs/thread-192179-1-1.html>

"(a)()" -> "(a)()"

"((bc)" -> "(bc)"

")))a((" -> "a"

"(a(b)" ->"(ab)" or "a(b)"

简单说，就是在尽量保留有效括号的情况下，返回任意一种正确结果。

### 在只有一种括号的时候，是可以扫一遍通过 +/- 来找出非法括号的，不过以一个方向定义的 +/- 只能找出一种，需要两个方向都扫一遍。

* **"(" 为正 , ")" 为负 ，从左向右可以找到非法的 ')'**
* **")" 为正，"(" 为负，从右向左可以找到非法的 '('**

后面的就非常 trivial 了。

```java
    private static String removeInvalid(String str){
        char[] chrArr = str.toCharArray();
        int val = 0;
        for(int i = 0; i < chrArr.length; i++){
            if(chrArr[i] == '(') val ++;
            else if(chrArr[i] == ')') val --;

            if(val < 0) {
                chrArr[i] = '#';
                val = 0;
            }
        }
        val = 0;
        for(int i = chrArr.length - 1; i >= 0; i--){
            if(chrArr[i] == ')') val ++;
            else if(chrArr[i] == '(') val --;

            if(val < 0){
                chrArr[i] = '#';
                val = 0;
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < chrArr.length; i++){
            if(chrArr[i] != '#') sb.append(chrArr[i]);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        String[] testcases = new String[]{"()()()()((()()())()(",
                                           "()AD(S)A()W)(S))()ASD()",
                                           "))ASDAS()()()Q(((())QWE)()",
                                           "S()((A)()D))W)Q())(EQ())()W(",
                                           "))ASD)QW(()S(Q)(WE)(Q()(AS)D("};
        for(int i = 0; i < testcases.length; i++){
            System.out.println("Input  : " + testcases[i]);
            System.out.println("Output : " + removeInvalid(testcases[i]));
            System.out.println();
        }
    }
```

## [Remove Invalid Parentheses](https://leetcode.com/problems/remove-invalid-parentheses/)

### 这题的结构就和 Different ways to add parenthese 不一样，括号之间的相对位置是非常重要的，而且有连续性，不能像那题一样直接在操作符上建一个 expression tree 出来，divide & conquer.

首先继承上一题 Stack 的经验，我们很容易可以知道需要的最少 edit 次数，以及 invalid 字符位置：跑一遍算法，看 Stack 里剩几个元素，分别在哪就行了。

> ### 只有一个非法括号的情况：
>
> * **( ( ) ) ( ) '(' ( ( ) ) ( )**
>   * **可以发现对于 '(' ，只能向右删下一个 '('，相邻的 '(' 是重复解**
>     * **( ) ( ( ) ) ')' ( ) ( ( ) )**
>   * **同理，')' 只能往左边找')'，相邻 ')' 为重复解。**
>
> ### 有两个非法括号的情况：
>
> * **( ) ( ( ) ) ')' ( ) '(' ( ( ) ) ( )**
>   * **( ) ( ( ) ) ( ) ( ( ) ) ( )**
>   * **( ) ( ( ) ) ')' ( ) '(' ( ( ) ) ( )**
>   * **可以发现 ')' 有两个可能的位置，'(' 有两个可能的位置，于是是 4 种组合。**

于是这题就变成了一个搜索问题\~

> * **问题1：既然在反复在字符串上进行修改，如何还能保证 List<> 里面的非法字符位置还是正确的？**
>   * **问题2：动态修改的 string ，动态变化的 index，要处理很多细节保证他们的 match.**

### 觉得顺着这个思路越想细节越多。。于是参考了下论坛的 DFS 思路，在所有 DFS 解法中，我最喜欢这个，非常简洁易懂，而且不依赖什么 trick，便于和面试官交流。

* **先扫一遍原 string ，记录下需要移除的左括号数量和右括号数量，保证最后的解最优；**
* **于是开始 DFS，对于每一个新的字符，我们都有两个选择：'留' 或者 '不留'，就像二叉树的分叉一样，留下了 dfs + backtracking 的空间。**
* **于是当我们针对各种情况进行 dfs 的时候，我们一定可以考虑到所有可能的有效 path，接下来需要定义什么是 “有效 path”**
* **base case 是左右括号和开括号数量都为零，并且 index 读取完了所有字符，则把结果添加进去；**
* **如果在任何时刻，左右括号和开括号的数量为负，我们都可以直接剪枝返回。**

### 这种解法的主要优点是好理解，空间上因为只用了一个 StringBuilder 非常经济，相比 BFS 速度和空间上都优异很多。如果说进一步优化的空间在哪，那就是对于 “重复状态” 的缓存与记忆化搜素还有提高的空间。

### 于是很 naive 的尝试了下加入 Set<> 来记录已经访问过的 StringBuilder 状态试图剪枝，然而很容易就出了 “没有任何返回结果” 的 bug ，其原因是，这个 dfs + backtracking 的代码本来就是在一个神似 binary tree 的结构上做一个 dfs 穷举而已，并不是 top-down recursion 那种子问题覆盖的结构，所以不适合用记忆化搜索解决。非要用的话至少 dfs 的返回类型就不能是 void ，至少也得是个 List<> 或者 Set<> 之类的 “子问题结果” 嘛。

```java
public class Solution {
    public List<String> removeInvalidParentheses(String s) {
        Set<String> set = new HashSet<>();

        int leftCount = 0;
        int rightCount = 0;
        int openCount = 0;

        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '(') leftCount++;
            if(s.charAt(i) == ')'){
                if(leftCount > 0) leftCount--;
                else rightCount ++;
            }
        }

        dfs(set, s, 0, leftCount, rightCount, openCount, new StringBuilder());

        return new ArrayList<String>(set);
    }

    private void dfs(Set<String> set, String str, int index, int leftCount, 
                     int rightCount, int openCount, StringBuilder sb){
        if(index == str.length() && leftCount == 0 && rightCount == 0 && openCount == 0){
            set.add(sb.toString());
            return;
        }

        if(index == str.length() || leftCount < 0 || rightCount < 0 || openCount < 0) return;

        char chr = str.charAt(index);
        int len = sb.length();

        if(chr == '('){
            // Remove current '('
            dfs(set, str, index + 1, leftCount - 1, rightCount, openCount, sb);
            // Keep current '('
            dfs(set, str, index + 1, leftCount, rightCount, openCount + 1, sb.append(chr));
        } else if(chr == ')'){
            // Remove current ')' 
            dfs(set, str, index + 1, leftCount, rightCount - 1, openCount, sb);
            // Keep current ')'
            dfs(set, str, index + 1, leftCount, rightCount, openCount - 1, sb.append(chr));
        } else {
            // Just keep the character
            dfs(set, str, index + 1, leftCount, rightCount, openCount, sb.append(chr));
        }

        // Back-tracking
        sb.setLength(len);
    }
}
```

### 参考论坛思路的一个 BFS 写法，速度很慢只能超过 14%，搞的有点像 word ladder 了。。。 不过另一个好处是，既然这么高的时间复杂度都能过，我那个 dfs 的解法也不用太追求完美，这样 index offset 的问题更好解决，遇到个新 string 直接重扫就好了。

```java
public List<String> removeInvalidParentheses(String s) {
        List<String> rst = new ArrayList<>();
        if(isValid(s)){
            rst.add(s);
            return rst;
        }
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();

        boolean isFound = false;
        visited.add(s);
        queue.offer(s);
        while(!queue.isEmpty() && !isFound ){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                String str = queue.poll();
                for(int pos = 0; pos < str.length(); pos++){
                    StringBuilder sb = new StringBuilder(str);
                    sb.deleteCharAt(pos);
                    String next = sb.toString();

                    if(visited.contains(next)) continue;

                    if(isValid(next)){
                        isFound = true;
                        rst.add(next);
                    } else {
                        queue.offer(next);
                    }

                    visited.add(next);
                }
            }
        }

        return rst;
    }

    private boolean isValid(String s){
        if(s == null || s.length() == 0) return true;
        int count = 0;
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '(') count++;
            if(s.charAt(i) == ')') count--;

            if(count < 0) return false;
        }

        return (count == 0);
    }
```

## [Expression Add Operators](https://leetcode.com/problems/expression-add-operators/)

num = "105", target = 5;

返回 \["10-5", "1x0+5", "1+0x5", "1x05", "1-0x5"] 是错的

* 不应该直接把 "05" 当成数字；
* 乘法符号有优先级问题。

在 Different ways to add parentheses 里，这么干没有任何问题，因为默认是加括号的，左右子树可以完全分离，单独求值。

### 而这题里，用 divide & conquer 无可避免地遇到符号优先级问题。于是看了一圈 LC 论坛，大家的做法其实都是 DFS + backtracking ..

这题非要用 divide & conquer 也不是不行，但是极其麻烦，如图所示：

![](https://2030049235-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MUt7Y8-dUQcwNZkL6dz%2Fsync%2Faba462f214c550b33d19e6f1ee16856ec801487a.jpg?generation=1614792531512729\&alt=media)

对于每一个节点，我们需要考虑其左子树的 String, value，还有抹去最后一步运算的 String 与 value .. 对于右子树，我们还需要其抹去第一步运算的 String 与 value 才能正确做 join.

## 所以说，珍爱生命，有乘法就远离 divide & conquer 吧。

### [一个思路不错的帖子](https://discuss.leetcode.com/topic/32068/java-simple-solution-beats-96-56/2)，这种做法就不用考虑 join了，只要做乘法的时候看它的前一个元素就行；

### 流程：

* **dfs + backtracking 思路**
* **dfs 函数中存 "左面表达式的当前值" 和 "上一步操作的结果" (用于处理优先级)**
* **参数都用 Long，防止溢出，毕竟 String 可能是个大数**
* **如果 start 位置是 0 而且当前循环的 index 还是 0，直接 return，因为一轮循环只能取一次 0；**
* **start == 0 的时候，直接考虑所有可能的起始数字扔进去，同时更新 cumuVal 和 prevVal;**
* **除此之外，依次遍历所有可能的 curVal parse，按三种不同的可能操作做 dfs + backtracking;**
  * **加法：直接算，prevVal 参数传 curVal，代表上一步是加法；**
  * **减法：直接算，prevVal 参数传 -curVal，代表上一步是减法；**
  * **乘法：要先减去 prevVal 抹去上一步的计算，然后加上 prevVal &#x20;*****curVal 代表当前值；同时传的 preVal 参数也等于 prevVal*****&#x20; curVal.**
  * **乘法操作这种处理方式，在遇到连续乘法的时候可以看到是叠加的；但是前一步操作如果不是乘法，则可以优先计算乘法操作。**
* **10-5-2x6 ，遇到乘法之前是 cumuVal = 3, preVal = -2; 新一轮 dfs 时 curVal = 6, 先退回前一步操作 - prevVal，得到 5，其实就是之前 (10 - 5) 的结果，然后加上当前结果 (-2 x 5)，prevVal 设成 -10 传递过去即可。**

```java
public class Solution {
    public List<String> addOperators(String num, int target) {
         List<String> rst = new ArrayList<>();
         dfs(rst, new StringBuilder(), num, target, 0, 0, 0);
         return rst;
    }

    private void dfs(List<String> rst, StringBuilder sb, String num, int target, int startPos, long cumuVal, long prevVal){
        if(startPos == num.length() && cumuVal == target){
            rst.add(sb.toString());
            return;
        }

        for(int i = startPos; i < num.length(); i++){   
            // We can pick one zero to start with; but not multiple
            if(num.charAt(startPos) == '0' && i != startPos) return;
            int len = sb.length();
            String curStr = num.substring(startPos, i + 1);
            long curVal = Long.parseLong(curStr);

            if(startPos == 0){     
                dfs(rst, sb.append(curVal), num, target, i + 1, curVal, curVal);
                sb.setLength(len);
            } else {
                dfs(rst, sb.append("+" + curStr), num, target, i + 1, cumuVal + curVal, curVal);
                sb.setLength(len);
                dfs(rst, sb.append("-" + curStr), num, target, i + 1, cumuVal - curVal, -curVal);
                sb.setLength(len);
                dfs(rst, sb.append("*" + curStr), num, target, i + 1, cumuVal - prevVal + prevVal * curVal, prevVal * curVal);
                sb.setLength(len);
            }
        }
    }
}
```

## [Basic Calculator](https://leetcode.com/problems/basic-calculator/)

### 计算器类问题，离不开 Dijkstra 的 [Shunting-yard algorithm](https://en.wikipedia.org/wiki/Shunting-yard_algorithm) 和 reverse polish notation.

### Input: 3 + 4 \* 2 / ( 1 - 5 ) ^ 2 ^ 3

![](https://2030049235-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MUt7Y8-dUQcwNZkL6dz%2Fsync%2Fdc97232cdd4b84fdaa5944d5d78d0bc76c4955cc.JPG?generation=1614792532864129\&alt=media) ![](https://2030049235-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MUt7Y8-dUQcwNZkL6dz%2Fsync%2Fa18370645011a6bdd2c1fb7710d7f387c26300c7.JPG?generation=1614792533096149\&alt=media)

* 因为有负号，运算顺序不能颠倒；
* 数字可能是多数位的，也可能是0，不能 assume 都是一位数；
* 带括号的处理方式；

### 复现了一下 Dijkstra 的 shunting yard algorithm，因为只有 “+” 和 “-” ，运算符优先级上要简单一些。在这个代码基础上扩展任何新的运算符都很容易，加个判断函数就行了。

* **建个 StringBuilder 存输出的 RPN，一个 Stack 存运算符；**
* **如果看到数字，直接添加到 StringBuilder 中；**
* **如果看到 "(" ，直接添加到 Stack 上；**
* **如果看到 ")"，把 Stack 上的所有运算符 pop 出来添加到 StringBuilder，直到遇见 "(" 为止；**
* **如果看到运算符，把 Stack 上所有 "大于等于当前运算符优先级" 的 pop 出来加到 StringBuilder，最后把自己放入 Stack，此时要么 Stack 为空，要么 Stack.peek() 的优先级比当前运算符小。**
* **优先级 ："乘除 = 3"， "加减 = 2”**

```java
public class Solution {
    public int calculate(String s) {
        // "(10+(  14+25+2)-0)+(0+18)"
        // multiple digits;
        // number zero;
        // have spaces;
        return solveRPN(getRPN(s));
    }

    // "123 \s 23 \s + \s 45 \s - \s 44 ..."
    private String getRPN(String s){
        StringBuilder sb = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char chr = s.charAt(i);
            if(chr == ' ') continue;

            if(Character.isDigit(chr)){
                sb.append(chr);
            } else {
                sb.append(' ');

                if(chr == '('){
                    stack.push(chr);
                } else if (chr == ')'){
                    while(!stack.isEmpty() && stack.peek() != '('){
                        sb.append(stack.pop());
                        sb.append(' ');
                    }
                    stack.pop();
                } else {
                    // is "+" or "-" operator with same precedence level
                    while(!stack.isEmpty() && stack.peek() != '('){
                        sb.append(stack.pop());
                        sb.append(' ');
                    } 
                    stack.push(chr);
                } 
            }
        }
        while(!stack.isEmpty()){
            sb.append(' ');
            sb.append(stack.pop());
        }

        return sb.toString();
    }

    private int solveRPN(String s){
        String[] strs = s.split(" ");
        Stack<Integer> stack = new Stack<>();
        for(String str : strs){
            if(str.equals("")) continue;
            if("+-".indexOf(str) != -1){
                int num2 = stack.pop();
                int num1 = stack.pop();

                if(str.equals("+")) stack.push(num1 + num2);
                if(str.equals("-")) stack.push(num1 - num2);
            } else {
                stack.push(Integer.parseInt(str));
            }
        }

        return stack.pop();
    }
}
```

## [ Basic Calculator II](https://leetcode.com/problems/basic-calculator-ii/)

Shunting Yard Algorithm 的做法同上，加一个优先级就行。

```java
public class Solution {
    public int calculate(String s) {
        return evalRPN(getRPN(s));
    }

    private String getRPN(String s){
        StringBuilder sb = new StringBuilder();
        Stack<Character> stack = new Stack<>();

        for(int i = 0; i < s.length(); i++){
            char chr = s.charAt(i);
            if(chr == ' ') continue;

            if(Character.isDigit(chr)){
                sb.append(chr);
            } else {
                sb.append(' ');
                if(chr == '('){
                    stack.push(chr);
                } else if(chr == ')'){
                    while(stack.peek() != '('){
                        sb.append(stack.pop());
                        sb.append(' ');
                    }
                    stack.pop();
                } else {
                    while(!stack.isEmpty() && getPrecedence(chr) <= getPrecedence(stack.peek())){
                        sb.append(stack.pop());
                        sb.append(' ');
                    }
                    stack.push(chr);
                }
            }
        }
        while(!stack.isEmpty()){
            sb.append(' ');
            sb.append(stack.pop());
        }
        return sb.toString();
    }

    private int evalRPN(String s){
        String[] strs = s.split(" ");
        Stack<Integer> stack = new Stack<>();

        for(String str : strs){
            if(str.equals("")) continue;
            // Is operator
            if("+-*/".indexOf(str) != -1){
                int num2 = stack.pop();
                int num1 = stack.pop();

                if(str.equals("+")) stack.push(num1 + num2);
                if(str.equals("-")) stack.push(num1 - num2);
                if(str.equals("*")) stack.push(num1 * num2);
                if(str.equals("/")) stack.push(num1 / num2);
            } else {
                stack.push(Integer.parseInt(str));
            }
        }
        return stack.pop();
    }

    private int getPrecedence(char chr){
        if(chr == '*' || chr == '/') return 3;
        if(chr == '+' || chr == '-') return 2;

        return 0;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/kuo_hao_ff0c_shu_zhi_ff0c_yu_ji_suan_qi.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.