Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 S-표현식(S-expression) 문자열을 계산하는 방법

S-표현식(S-expression)이란?

문자열 s가 S-표현식(S-expression)으로 주어졌을 때, 이를 평가하여 그 결과를 정수로 반환하는 프로그램을 작성해 보겠습니다.

S-표현식은 하나의 숫자이거나, 괄호로 감싸진 재귀적인 표현식입니다. 예를 들어 (+ (- 3 2) (* 3 3))은 일반적인 수학 표기법으로 (3 - 2) + (3 * 3)과 같으며, 그 결과는 10이 됩니다. 사용할 수 있는 유효한 연산자는 +, -, *, / 네 가지입니다.

예를 들어 입력이 s = "(- (+ 3 2) 2)"라면, 이는 ((3 + 2) - 2)와 같으므로 출력 결과는 3이 됩니다.

해결 접근 방법

이 문제는 스택(stack) 자료구조를 활용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • 새로운 스택을 생성합니다.
  • 문자열에서 여는 괄호 (와 닫는 괄호 )를 모두 제거합니다.
  • 공백을 기준으로 문자열을 분리하여 리스트로 만듭니다.
  • 리스트를 뒤에서부터(역순으로) 순회합니다. S-표현식은 연산자가 피연산자보다 앞에 오는 전위 표기법이므로, 역순으로 읽으면 일반적인 후위 표기식처럼 처리할 수 있기 때문입니다.
  • 순회 중 각 요소 i에 대해 다음을 수행합니다.
    • 길이가 1보다 큰 경우: 음수일 가능성이 있습니다. 첫 글자가 -인지 확인한 후 정수로 변환하여 스택에 push합니다.
    • 숫자인 경우: 정수로 변환하여 스택에 push합니다.
    • 연산자인 경우: 스택에서 두 개의 값을 pop하고, 해당 연산을 수행한 뒤 결과를 다시 스택에 push합니다.
  • 모든 순회가 끝나면 스택의 최상단 값을 pop하여 반환합니다. 이것이 최종 계산 결과입니다.

Python 구현 코드

아래 코드를 통해 실제 구현을 확인해 보겠습니다.

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

코드 설명 및 시간 복잡도

이 알고리즘의 동작 과정을 단계별로 살펴보면 다음과 같습니다.

  1. 괄호 제거 후 s는 - + 3 2 2가 되고, 공백으로 분리하면 ["-", "+", "3", "2", "2"] 리스트가 생성됩니다.
  2. 역순으로 순회하면 2, 2, 3이 차례로 스택에 쌓입니다.
  3. +를 만나면 3과 2를 pop하여 더한 값 5를 스택에 push합니다.
  4. -를 만나면 5와 2를 pop하여 뺀 값 3을 스택에 push합니다.
  5. 최종적으로 스택에는 3만 남고, 이것이 반환됩니다.

시간 복잡도는 O(n), 공간 복잡도 역시 O(n)입니다. 여기서 n은 입력 문자열의 길이입니다.

주의할 점은 나눗셈(/)의 경우 Python 3에서 실수 나눗셈을 수행하므로, 정수 결과가 필요하다면 몫 연산(//)을 사용하는 것이 안전할 수 있다는 것입니다. 또한 이 구현은 잘못된 형식의 입력에 대한 예외 처리는 포함하지 않으므로, 실제 서비스에 적용할 때는 유효성 검사 로직을 추가하는 것이 좋습니다.