题目：
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 *.
大意是给定一个运算，求解所有运算序列的解
例如
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) = 10Output: [-34, -14, -10, -10, 10]
算法思路：
将运算转换成栈过程，这样就将问题转换成一个递归问题
即每一步分为两种走法：
1）继续向栈中添加数字与运算符
2）弹出2个数字1个运算符进行计算
代码：
class Solution(object):
def addOperatorAndNumber(self, inputList, stack):
if len(inputList) < 2:
return []
stack.append(inputList[0])
stack.append(inputList[1])
inputList = inputList[2:]
return self.calculate(inputList,stack)
def calculateTopStack(self, inputList, stack):
number1 = int(stack.pop())
operator = stack.pop()
number2 = int(stack.pop())
if operator == "+":
stack.append(number1 + number2)
elif operator == "-":
stack.append(number2 - number1)
elif operator == "*":
stack.append(number1 * number2)
return self.calculate(inputList,stack)
def calculate(self, inputList, stack):
if len(stack) == 1:
if len(inputList) == 0:
return [stack[0]]
else:
return self.addOperatorAndNumber(inputList,stack)
result1 = self.calculateTopStack(inputList[:], stack[:])
result2 = self.addOperatorAndNumber(inputList[:],stack[:])
result1.extend(result2)
return result1
def diffWaysToCompute(self, input):
"""
:type input: str
:rtype: List[int]
"""
input = input.replace('+'," + ")
input = input.replace("-"," - ")
input = input.replace("*"," * ")
inputList = input.split(" ")
stack = [int(inputList[0])]
return self.calculate(inputList[1:],stack)
