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 *.
Example 1:
Input: "2-1-1"
Output: [0, 2]
Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2
Example 2:
Input: "2*3-4*5"
Output: [-34, -14, -10, -10, 10]
Explanation:
(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
描述
给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。
示例 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
思路
- 这道题使用递归求解.
- 以每一个操作符为分割点，我们将给定的字符串分割成两个字串，假设我们递归求解得到了左边的所有组合结果left，右边的所有组合right，我们以当前符号为分隔符，把left和right中的所有数用当前运算符做运算，得到最终结果.
- 递归终止条件，输入的字符串只包含一个数字.
# -*- coding: utf-8 -*- # @Author: 何睿 # @Create Date: 2019-02-02 15:19:33 # @Last Modified by: 何睿 # @Last Modified time: 2019-02-02 16:51:16 class Solution: def diffWaysToCompute(self, input): """ :type input: str :rtype: List[int] """ sovled = {} _input = input return list(self.__recursion(sovled, _input)) def __recursion(self, sovled, _input): # 有记录的递归，如果当前求解的字符串已经求解过了，我们直接返回结果. if _input in sovled: return sovled[_input] patial, num = [], 0 for i in range(len(_input)): # 从字符串中取出数字 if _input[i].isdigit(): num = num * 10 + int(_input[i]) # 如果当前位置是符号 elif _input[i] == '+' or _input[i] == "-" or _input[i] == '*': # 以当前位置为分隔 # 递归求解当前位置左边字符串的解 left = self.__recursion(sovled, _input[0:i]) # 递归求解当前位置右边字符串的解 right = self.__recursion(sovled, _input[i + 1:]) # 将当前位置左边的解和右边的解用当前的符号进行组合 for x in left: for y in right: patial.append(self.__cal(_input[i], x, y)) num = 0 if not patial: patial.append(num) sovled[_input] = patial # 返回当前的解 return patial def __cal(self, operator, num1, num2): # 题目给定只有三个运算符 if operator == "+": return num1 + num2 if operator == "-": return num1 - num2 if operator == "*": return num1 * num2
源代码文件在这里
