S-표현식으로 문자열이 있다고 가정합니다. S-expression을 평가하고 결과를 정수로 반환해야 합니다. s-expression은 하나의 숫자인 표현식이거나 (+ (- 3 2) (* 3 3))와 같이 괄호로 묶인 재귀 표현식이며, 이는 (3 - 2) + (3 * 3) =10. 여기서 유효한 연산자는 +, -, * 및 /입니다.
따라서 입력이 s ="(- (+ 3 2) 2)"와 같으면 출력은 ((3 + 2) - 2) =3과 같이 3이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
스택 :=새 스택
-
s
의 여는 괄호와 닫는 괄호 제거 -
a :=공백을 사용하여 s를 나누고 파티션 목록을 만듭니다.
-
각 i에 대해 역순으로
-
i의 크기가 1보다 크면
-
i[0]이 "-"와 같으면
-
i를 정수로 스택에 푸시
-
다음 반복으로 이동
-
-
그렇지 않으면
-
i를 정수로 스택에 푸시
-
-
-
그렇지 않으면 i가 숫자일 때
-
i를 정수로 스택에 푸시
-
-
그렇지 않으면
-
스택 크기>=2인 경우
-
num1 :=스택에서 팝
-
num2 :=스택에서 팝
-
i가 "+"와 같으면
-
num1 + num2를 수행하고 스택에 푸시
-
-
그렇지 않으면 i가 "-"와 같을 때
-
num1 - num2를 수행하고 스택에 푸시
-
-
그렇지 않으면 i가 "*"와 같을 때
-
num1 * num2를 수행하고 스택에 푸시
-
-
그렇지 않으면
-
num1 / num2를 수행하고 스택에 푸시
-
-
-
-
-
스택에서 맨 위 요소를 반환하고 맨 위 요소를 제거합니다.
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
class Solution:
def solve(self, s):
stack = list()
s = s.replace("(", "")
s = s.replace(")", "")
a = s.split()
for i in a[::-1]:
if len(i) > 1:
if i[0] == "-":
stack.append(int(i))
continue
else:
stack.append(int(i))
elif i.isdigit():
stack.append(int(i))
else:
if len(stack) >= 2:
num1 = stack.pop()
num2 = stack.pop()
if i == "+":
stack.append(int(num1 + num2))
elif i == "-":
stack.append(int(num1 - num2))
elif i == "*":
stack.append(int(num1 * num2))
else:
stack.append(int(num1 / num2))
return stack.pop()
ob = Solution()
s = "(- (+ 3 2) 2)"
print(ob.solve(s)) 입력
s = "(- (+ 3 2) 2)"
출력
3