Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.
Example 1:
Input: expression = "2-1-1"
Output: [0,2]
Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2
Example 2:
Input: expression = "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
Constraints:
- 1 <= expression.length <= 20
- expression consists of digits and the operator '+', '-', and '*'.
- All the integer values in the input expression are in the range [0, 99].
출력 샘플과 같이 괄호가 어디에 있느냐에 따라 다양한 조합이 가능하다.
연산자가 등장할 때 좌/우 분할을 하고 각각 계산 결과를 반환한다.
"2*3-4*5" 를 입력할 경우,
1번째 for문: 처음에는 (2) * (3-4*5)로 분할이 되고
- left인 (2)는 if expression.isdigit()에서 걸러져 [2]가 반환된다.
- right인 (3-4*5)는 재귀를 통해서 다시 분할한다.
- 1번째 for문: (3-4*5)는 (3) - (4*5)로 분할된다.
- left인 (3)은 if expression.isdigit()에서 걸러져 [3]이 반환된다.
- right인 (4*5)는 재귀를 통해서 다시 분할한다.
- (4*5)는 (4) * (5) 로 분할된다.
- left인 (4)는 [4]반환
- right인 (5)는 [5] 반환
- 2번째 for문: (3-4*5)는 (3-4) * (5)로 분할된다.
- ...
2번째 for문: (2*3) - (4*5) 로 분할이 된다.
class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
def compute(left, right, operator):
results = []
for l in left:
for r in right:
results.append(eval(str(l) + operator + str(r)))
return results
if expression.isdigit():
return [int(expression)]
answer = []
for idx, val in enumerate(expression):
if val in "-+*":
left = self.diffWaysToCompute(expression[:idx])
right = self.diffWaysToCompute(expression[idx+1:])
answer.extend(compute(left, right, val))
return answer
eval( )
문자열을 파싱하고 파이썬 표현식으로 처리해주는 함수
>>> '1+2'
'1+2'
>>> eval('1+2')
3
append( ) & extend( )
append는 리스트에 또 다른 리스트를 append하면 또 다른 리스트를 엘리먼트로 처리한다.
>>> a = [1,2,3]
>>> b = [4,5]
>>> a.append(b)
>>> a
[1,2,3,[4,5]]
extend는 삽입 대상의 리스트를 풀어서 각각의 엘리먼트로 확장해 삽입한다.
>>> a = [1,2,3]
>>> b = [4,5]
>>> a.extend(b)
>>> a
[1,2,3,4,5]
