**Reference: **https://leetcode.com/problems/different-ways-to-add-parentheses/
这题虽然我的解法比较挫，但是涉及几个子问题广：
- 数字字符串的解析
- Unique Binary Search Trees
- 树的后序遍历
- 逆波兰表达式
代码：
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;
}
};