[LeetCode 241]Different Ways to

**Reference: **https://leetcode.com/problems/different-ways-to-add-parentheses/

这题虽然我的解法比较挫，但是涉及几个子问题广：

1. 数字字符串的解析
2. Unique Binary Search Trees
3. 树的后序遍历
4. 逆波兰表达式

代码：

 class Solution
 {
     struct TreeNode
     {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     };

 public:
     vector<int> diffWaysToCompute(string input)
     {
         vector<int> inputvec = transfer(input);
         if (inputvec.size() <= 1)
             return inputvec;

         vector<int> vec;
         int n = inputvec.size() / 2;
         vector<TreeNode*> nodevec = generateTrees(0, n - 1);
         for (int i = 0; i < nodevec.size(); ++i)
         {
             vector<int> postorder;
             postOrder(nodevec[i], inputvec, postorder);
             vec.push_back(calc(postorder));
         }
         sort(vec.begin(), vec.end());
         return vec;
     }

     vector<int> transfer(string input)
     {
         vector<int> vec;
         int num = 0;
         bool first = true;
         for (int i = 0; i < input.length(); ++i)
         {
             char ch = input[i];
             if (isOperator(ch))
             {
                 vec.push_back(num);
                 vec.push_back(ch);
                 num = 0;
                 first = true;
             }
             else
             {
                 if (first)
                 {
                     num = ch - '0';
                     first = false;
                 }
                 else
                 {
                     num *= 10;
                     num += ch - '0';
                 }
             }
         }
         vec.push_back(num);
         return vec;
     }

     int calc(vector<int> &postorder)
     {
        stack<int> calcsta;
        for (int i = 0; i < postorder.size(); ++i)
        {
            char ch = postorder[i];
            if (isOperator(ch))
            {
                int operand2 = calcsta.top();
                calcsta.pop();
                int operand1 = calcsta.top();
                calcsta.pop();
                int res = 0;
                switch (ch)
                {
                case '+':
                    res = operand1 + operand2;
                    break;
                case '-':
                    res = operand1 - operand2;
                    break;
                case '*':
                    res = operand1 * operand2;
                    break;
                }
                calcsta.push(res);
            }
            else
            {
                calcsta.push(ch);
            }
        }
        return calcsta.top();
     }

     bool isOperator(char ch)
     {
         return ch == '+' || ch == '-' || ch == '*';
     }

     void postOrder(TreeNode *root, vector<int> &input, vector<int> &vec)
     {
         if (nullptr == root)
             return;
         postOrder(root->left, input, vec);
         if (root->left == nullptr)
             vec.push_back(input[root->val - 1]);
         postOrder(root->right, input, vec);
         if (root->right == nullptr)
             vec.push_back(input[root->val + 1]);
         vec.push_back(input[root->val]);
     }

     vector<TreeNode*> generateTrees(int start, int end)
     {
         vector<TreeNode*> vec;
         if (start > end)
         {
             vec.push_back(nullptr);
             return vec;
         }

         for (int i = start; i <= end; ++i)
         {
             vector<TreeNode*> left = generateTrees(start, i - 1);
             vector<TreeNode*> right = generateTrees(i + 1, end);
             for (int l = 0; l < left.size(); ++l)
             {
                 for (int r = 0; r < right.size(); ++r)
                 {
                     TreeNode *tmp = new TreeNode(2 * i + 1);
                     tmp->left = left[l];
                     tmp->right = right[r];
                     vec.push_back(tmp);
                 }
             }
         }
         return vec;
     }
 };

简单的解法是用分治法（Divide and Conquer）：

class Solution
{
public:
    vector<int> diffWaysToCompute(string input)
    {
        vector<int> vec;
        for (int i = 0; i < input.length(); ++i)
        {
            char ch = input[i];
            if (ch == '+' || ch == '-' || ch == '*')
            {
                vector<int> left = diffWaysToCompute(input.substr(0, i));
                vector<int> right = diffWaysToCompute(input.substr(i + 1, input.length() - i - 1));
                for (int l = 0; l < left.size(); ++l)
                {
                    for (int r = 0; r < right.size(); ++r)
                    {
                        int res = 0;
                        switch (ch)
                        {
                        case '-':
                            res = left[l] - right[r];
                            break;
                        case '+':
                            res = left[l] + right[r];
                            break;
                        case '*':
                            res = left[l] * right[r];
                            break;
                        }
                        vec.push_back(res);
                    }
                }
            }
        }

        if (vec.empty())
        {
            int num = 0;
            sscanf_s(input.c_str(), "%d", &num);
            vec.push_back(num);
        }
        return vec;
    }
};