Leetcode241.Different Ways to Add Parentheses为运算表达式设计优先级

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

示例 1:

输入: "2-1-1" 输出: [0, 2] 解释: ((2-1)-1) = 0 (2-(1-1)) = 2

示例 2:

输入: "2*3-4*5" 输出: [-34, -14, -10, -10, 10] 解释: (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

采用了分治的思想和方法。

分治法就是将一个大规模的问题分成n个小规模的问题。

这些问题相互独立（小问题之间如何解决不会相互影响），且小问题的问题性质与大问题的性质相同。

通过小问题的解，得出大问题的解。

该问题可以将长的字符串分成短的字符串，以运算符为分界，将字符串一分为二，以只含单个整数的字符作为分界的终点。

因为运算符不止一个，所以若干(1,2,3...)个运算符顺序确定的情况下，剩下的运算符会有多解的情况。

  class Solution {

  public:

	  vector<int> diffWaysToCompute(string input)

	  {

		  vector<int> res;

		  for (int i = 0; i < input.size(); i++)

		  {

			  if (input[i] == '+' || input[i] == '-' || input[i] == '*')

			  {

				  vector<int> left = diffWaysToCompute(input.substr(0, i));

				  vector<int> right = diffWaysToCompute(input.substr(i + 1));

				  for (int a : left)

				  {

					  for (int b : right)

					  {

						  switch (input[i])

						  {

						  case '+':

							  res.push_back(a + b);

							  break;

						  case '-':

							  res.push_back(a - b);

							  break;

						  default:

							  res.push_back(a * b);

							  break;

						  }

					  }

				  }

			  }

		  }

		  /*if (input.size() == 1)

			  res.push_back((int)(input[0] - '0'));*/

		  if (res.empty())

		  {

			  res.push_back(atoi(input.c_str()));

		  }

		  return res;

	  }

  };

附：

string sub = s.substr(5); //只有一个数字5表示从下标为5开始一直到结尾;

string sub = s.substr(5, 3); //从下标为5开始截取长度为3位;

const char *c_str();

c_str()函数返回一个指向正规C字符串的指针常量, 内容与本string串相同.

这是为了与c语言兼容，在c语言中没有string类型，故必须通过string类对象的成员函数c_str()把string 对象转换成c中的字符串样式。

int atoi(const char* str)

参数str是要转换的字符串，返回值是转换后的整数。

巴特西

Leetcode241.Different Ways to Add Parentheses为运算表达式设计优先级

最新文章

热门文章