###### tags: `LeetCode` `DFS` `Medium` `String` `Devide and Conquer`
# LeetCode #241 [Different Ways to Add Parentheses](https://leetcode.com/problems/different-ways-to-add-parentheses/)
### (Medium)

給定一個含有數字和運算符的字符串，為表達式添加括號，改變其運算優先級以求出不同的結果。你需要給出所有可能的組合的結果。有效的運算符號包含 +, - 以及 * 。

---
首先先建立一個無序map容器<string, vector<int>>儲存運算式為x時所有的運算可能(依不同運算優先級別)。

遞迴函式的目標為回傳該字串的所有運算組合(數組), 核心概念為讀取到一個運算符時,以該運算符為界分割左右字串, 並以左右字串為參數遞迴呼叫函式。拿到左右字串遞迴函式回傳的數組後, 針對每一個數組元素進行組合運算, 並將結果存入答案數組中, 最後回傳。

在進行最小分割的遞迴函式時, 由於字串內容只有一個數字, 此時上面的左右子字串進行組合運算不會發生, 因此在for迴圈結束後ans數組為空, 此時直接將字串內容存入ans數組中並回傳, 因此該遞迴的上層函式會收到左右皆為一個數字的數組, 並進行運算在回傳, 並如此遞迴。

此外, 使用無序map儲存計算結果(特定字串為key, 該字串的所有運算結果為value), 並在遞迴函式開始時判斷該算式是否被計算過, 若map中存在該算式, 可直接回傳值(整數數組), 省去時間; 同理,在函式最後回傳答案數組時, 同樣須將該字串的運算式結果組合數組存入map中。

---

namespace cal{
    int plus(int a, int b){
        return a+b;
    }
    int minus(int a, int b){
        return a-b;
    }
    int multiply(int a, int b){
        return a*b;
    }
}

class Solution {
public:
    unordered_map<string, vector<int>> m;
    vector<int> diffWaysToCompute(string expression) {
        return ways(expression);
    }
    const vector<int>& ways(const string& input){
        if(m.count(input))return m[input];
        vector<int> ans;
        for(int i=0;i<input.size();i++){
            char op = input[i];
            if(op=='+'||op=='-'||op=='*'){
                const string left = input.substr(0, i);
                const string right = input.substr(i+1);
                
                const vector<int>& l = ways(left);
                const vector<int>& r = ways(right);
                
                function<int(int, int)> f;
                switch(op){
                    case '+':f=cal::plus;break;
                    case '-':f=cal::minus;break;
                    case '*':f=cal::multiply;break;
                }
                for(int a:l)
                    for(int b:r)
                        ans.push_back(f(a,b));
            }
        }
        if(ans.empty())
            ans.push_back(stoi(input));
        
        return m[input]=ans;
    }
};