###### tags: `Leetcode` `medium` `divide and conquer` `python` `c++`

# 241. Different Ways to Add Parentheses

## [題目連結:] https://leetcode.com/problems/different-ways-to-add-parentheses/description/

## 題目:
Given a string ```expression``` of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in **any order**.

The test cases are generated such that the output values fit in a 32-bit integer and the number of different results does not exceed 10**4.

**Example 1:**

Input: expression = "2-1-1"
Output: [0,2]
Explanation:
((2-1)-1) = 0 
(2-(1-1)) = 2

**Example 2:**

Input: expression = "2*3-4*5"
Output: [-34,-14,-10,-10,10]
Explanation:
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

## 解題想法:
* 題目為給一表達式，可能含有加減乘，可再任意位置添加括號，求出所有可能表達式的值
* Divide and Conquer:
* **核心概念** :
* 若當前字符為 **運算符**
* 切割字串為左右字串，分別進行遞迴
* Step1:
* 建立結果res數組，遍歷expression中所有字符
* Step2:
* 當前字符為運算符，將expression分成左右兩段遞迴
* Step3:
* 由Step2，得到左右遞迴結果: left,right，兩串數組
* 分別從left,right中的數字，經由當前運算符進行運算，並存於res
* Step4:
* 若遍歷完expression後，res仍為空，表示expression為數字，直接轉換成整數存入res即可
* Step5:
* return res

## Python:

class Solution(object):
    def diffWaysToCompute(self, expression):
        """
        :type expression: str
        :rtype: List[int]
        """
        res=list() #創新一個list
        n = len(expression)
        for i in range(n):
            if expression[i]=='+' or expression[i]=='-' or expression[i]=='*':
                #以當前i為中心 
                left = self.diffWaysToCompute(expression[:i]) #左半段 不包含i
                right = self.diffWaysToCompute(expression[i+1:]) #右半段 不包含i
                for l in left:
                    for r in right:
                        if expression[i]=='+':
                            res.append(l+r)
                        elif expression[i]=='-':
                            res.append(l-r)
                        elif expression[i]=='*':
                            res.append(l*r)
        if not res: #純數字
            res.append(int(expression))
        return res

expression = "2*3-4*5"
result = Solution()
ans=result.diffWaysToCompute(expression)
print(ans)

## C++:
* string to int: **stoi**

class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        vector<int> res;
        int n=expression.size();
        for (int i=0; i<n; i++){
            if (expression[i]=='+' || expression[i]=='-' || expression[i]=='*'){
                vector<int> left=diffWaysToCompute(expression.substr(0,i));// substr(pos,len)
                vector<int> right=diffWaysToCompute(expression.substr(i+1)); //(pos~end)
                for (int valL: left){
                    for (int valR: right){
                        if (expression[i]=='+')
                            res.push_back(valL+valR);
                        else if (expression[i]=='-')
                            res.push_back(valL-valR);
                        else
                            res.push_back(valL*valR);
                    }
                }
            }
        }
        if (res.empty())
            res.push_back(stoi(expression)); //String TO Int
        return res;
    }
};