리트코드 241번
괄호를 이용해 가능한 모든 계산결과 출력
풀이1 재귀
class Solution:
def calculate(self,left,right,opt):
result = []
for l in left:
for r in right:
result.append(eval(str(l) + opt + str(r)))
return result
def diffWaysToCompute(self, expression: str):
answer = []
if expression.isdigit():
return [expression]
for i in range(len(expression)):
if expression[i] in "+-*":
left = self.diffWaysToCompute(expression[:i])
right = self.diffWaysToCompute(expression[i+1:])
answer.extend(self.calculate(left,right,expression[i]))
return answer-
예시 : "3+2*1-5+4" 라는 식이 주어진다면 연산기호를 기준으로 앞뒤를 나눠준다 -> 숫자가 두자리일 수 도 있어서 항상 숫자가 짝수인덱스인것은 아님 (divide)
-
처음에는 (3)+(2*1-5+4) 이렇게 나뉨
-
(3)같은 경우는 더이상 쪼갤 수 없기 때문에 expression.isdigit()에서 걸러져 [3]자체가 반환됩니다.
-
(2*1-5+4) 이부분은 안에서 괄호가 어떻게 되냐에 따라 여러 연산결과가 나올 수 있으므로 재귀를 통해서 또 쪼개준다
-
원리는 "(A)연산기호(B)"로 쪼개졌다면 A가 가질수있는 계산결과를 리스트 left로 B가 가질 수 있는 계산결과를 리스트 right에 담은 다음 2중 for문을 돌려서 그 조합을 반환하는 것
-
따라서 diffWaysToCompute는 매 쪼갠 expression이 가질 수 있는 연산결과 answer을 반환하면 됩니다.
문자열로 된 수식 계산하기
- 문자열로 된 수식 "3+4"를 계산하는 방식은 여러가지가 있겠지만 아래와 같이 eval을 쓰면 편리하게 처리할 수 있습니다. 이때 반환타입은 int입니다.
result = eval("3+4")
print(result) # 7 리스트 합치기
아래의 코드는 주어진 수식에서 나올 수 있는 모든 결과를 구하기 위한 for문안에 코드입니다.
이때 append가 아닌 이유는 가능한 모든 조합(리스트)의 합이기 때문에 append로 처리할 경우 리스트자체가 리스트 안으로 들어가게 됩니다. 따라서 리스트 안에 있는 요소들을 합칠때는 extend나 +연산을 사용하면 됩니다
answer.extend(self.calculate(left,right,expression[i]))