241 Different Ways to Add Parentheses

2019-11-06 08:09:40

字体：大中小

来源：转载

供稿：网友

一、题目描述

给定一个数字和操作的字符串，返回通过所有方式组合数字和操作符的计算结果。有效的操作符为“+ $+$ ”“− $-$ ”和“∗ $*$ ”。 示例1： 输入："2−1−1" $"2-1-1"$ ((2−1)−1)=0 $((2-1)-1)=0$ (2−(1−1))=2 $(2-(1-1))=2$ 输出：[0,2] $[0,2]$ 示例2： 输入："2∗3−4∗5" $"2*3-4*5"$ (2∗(3−(4∗5)))=−34 $(2*(3-(4*5))) = -34$ ((2∗3)−(4∗5))=−14 $((2*3)-(4*5)) = -14$ ((2∗(3−4))∗5)=−10 $((2*(3-4))*5) = -10$ (2∗((3−4)∗5))=−10 $(2*((3-4)*5)) = -10$ (((2∗3)−4)∗5)=10 $(((2*3)-4)*5) = 10$ 输出：[−34,−14,−10,−10,10] $[-34, -14, -10, -10, 10]$ 根据示例2的输出可以推断，最终结果有递归得到的vector $vector$ 排序得到。 函数原型：

vector<int> diffWaysToCompute(string input)

二、编程思路

对于一个含有操作符的字符串str $str$ 来说： i⨂i⨂i⨂i⨂i⨂i;(其中⨂表示加、减、乘等操作) $i /bigotimes i/bigotimes i/bigotimes i/bigotimes i/bigotimes i ;(其中/bigotimes 表示加、减、乘等操作)$ 若使用分治的思想来解决问题，则有如下思路：

递归步：若串str $str$ 中含有操作符，则列举所有可能，将其划分为左右两个字符串left_str、right_str $left/_str、right/_str$ ,每一个操作符对应一种划分方式。对其分别递归调用该函数得到left_vct和right_vct $left/_vct和right/_vct$ ，将left_vct和right_vct $left/_vct和right/_vct$ 两两进行⨂ $/bigotimes$ 操作，装入结果vector $vector$ 即可。 递归基：若串str $str$ 中不包含操作符，说明已经进入到递归的最低端，该字符串中只含有数字，直接将字符串转化为数字，装入结果vector $vector$ 返回即可。

函数名称	头文件	简介	函数原型
count	`algorithm`	返回[first，last)范围内，val出现的次数	`template < class InputIterator, class T> typename iterator_traits<InputIterator$>::difference_type count (InputIterator first, InputIterator last, const T& val);`
find	`algorithm`	返回[first,last)范围内val出现的次数，若为找到，则返回last	`template <class InputIterator, class T> InputIterator find (InputIterator first, InputIterator last, const T& val);`
substr	`string`	返回从位置pos开始，长度为npos的字符串	`basic_string substr (size_type pos = 0, size_type len = npos) const;`
cstr	`string`	返回当前字符串所对应的字符数组的字符数组首地址的指针	`const charT* c_str() const;`
atoi	`cstdlib`	将c字符数组转为int类型数字	`int atoi (const char * str);`

三、代码设计

class Solution {public: vector<int> diffWaysToCompute(string input) { int len = input.size(); vector<int>ans; if (len == 0) return ans; ans = compute(input); return ans; } vector<int> compute(string input){ string op = "+-*"; int sign_num = 0; for (int i = 0; i < op.size(); i++){ sign_num += count(input.begin(), input.end(), op[i]); } //cout << "sign num：" << sign_num << endl; vector<int> ans; //定义递归基：当字符串中包含一个符号时，直接装入其值； if (sign_num == 0){ int num = string2num(input); ans.push_back(num); //cout << "basis" << endl; return ans; } //定义递归步：当字符串中含有多个字符时，依次将其分割； else{ for (int i = 0; i < op.size(); i++){ int idx=input.find_first_of(op[i]); while (idx != string::npos){ //cout << "idx: " << idx << endl; string left, right; vector<int>left_vct, right_vct; left = input.substr(0, idx); right = input.substr(idx + 1,input.length()-idx-1); /*cout << "sign"<<input[idx] << endl; cout <<"left and right"<<left << " " << right << endl;*/ left_vct = compute(left); right_vct = compute(right); //cout << "left size:" << left_vct.size() << " right size:" << right_vct.size() << endl; switch (op[i]) { case '+': for (int p = 0; p < left_vct.size(); p++){ for (int q = 0; q < right_vct.size(); q++){ ans.push_back(left_vct[p] + right_vct[q]); } } break; case '-': for (int p = 0; p < left_vct.size(); p++){ for (int q = 0; q < right_vct.size(); q++){ ans.push_back(left_vct[p] - right_vct[q]); } } break; case '*': for (int p = 0; p < left_vct.size(); p++){ for (int q = 0; q < right_vct.size(); q++){ ans.push_back(left_vct[p] * right_vct[q]); } } break; default: break; } idx = input.find(op[i], idx + 1); } } return ans; } } int string2num(string str){ const char* str_char = str.c_str(); int num = atoi(str_char); return num; }};