算法练习（12） —— Different Ways to Add Parentheses

算法练习（12） —— Different Ways to Add Parentheses

习题

本题取自 leetcode 中的 Divide and Conquer 栏目中的第241题：
Different Ways to Add Parentheses

题目如下：

Description

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example1

Input: “2-1-1”.

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example2

Input: “2*3-4*5”

(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

Output: [-34, -14, -10, -10, 10]

思路与代码

• 做了很久的动态规划，现在从最开始的分治开始复习一下。
• 这个题目很容易理解，就是在不同的地方加上括号来改变整个算式的优先级，计算出所有可能的值。并且如果出现不同算法，结果相同的话，要保存多次（见例2）
• 看到括号和运算符第一时间想到的是压栈，但是仔细想想好像实现起来效果并不好，而且实现挺复杂的。于是采用分治递归的方法。
• 递归的地点在于每次遇到运算符的时候。由于会做一个遍历，所以会对每一个运算符设置不同的优先级，确保了完全性。

具体代码如下：

#include <vector>
#include <string>
using namespace std;class Solution {
public:vector<int> diffWaysToCompute(string input) {vector<int> res;int len = input.length();for (int i = 0; i < len; i++) {// recurse when meeting the operatorif (input[i] == '-' || input[i] == '+' || input[i] == '*') {string left = input.substr(0, i);string right = input.substr(i + 1);vector<int> left_res = diffWaysToCompute(left);vector<int> right_res = diffWaysToCompute(right);for (auto l : left_res)for (auto r : right_res) {if (input[i] == '+')res.push_back(l + r);else if (input[i] == '-')res.push_back(l - r);elseres.push_back(l * r);}}}// if the input doesn't contain operatorsif (res.empty())res.push_back(atoi(input.c_str()));return res;}
};