LeetCode 224 Basic Calculator: Python 스택 풀이와 추적

LeetCode 224, Basic Calculator는 eval을 쓰지 않고 숫자, +, -, 괄호, 공백으로 이루어진 문자열을 계산하는 문제입니다. 곱셈이나 나눗셈이 없으니 연산자 우선순위를 따질 필요도 없습니다. 어려운 건 괄호뿐이고, 상태를 저장하는 스택 하나면 한 번의 순회로 깔끔하게 해결됩니다.

문제

음이 아닌 정수, +, -, (, ), 공백으로 이루어진 수식을 나타내는 문자열 s가 주어질 때, 그 값을 반환하세요. 마이너스 기호는 -(2 + 3)처럼 단항 연산자로도 쓰일 수 있습니다.

예시:

핵심 아이디어

왼쪽에서 오른쪽으로 훑으면서 세 가지를 유지합니다. 지금까지의 계산 결과, 현재 부호, 그리고 만들고 있는 숫자입니다. (를 만나면 하위 수식이 시작됩니다. 괄호 앞의 결과와 부호를 스택에 저장한 뒤, 결과는 0, 부호는 +1로 새로 시작합니다. )를 만나면 하위 수식을 마무리하고, 저장해 둔 부호를 곱한 다음 저장해 둔 결과에 더합니다.

각 문자를 이렇게 처리합니다:

마지막에 마지막 sign * num을 더합니다.

def calculate(s):
    result, sign, num = 0, 1, 0
    stack = []
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch in "+-":
            result += sign * num
            num = 0
            sign = 1 if ch == "+" else -1
        elif ch == "(":
            stack.append(result)
            stack.append(sign)
            result, sign = 0, 1
        elif ch == ")":
            result += sign * num
            num = 0
            result *= stack.pop()   # the sign before the parenthesis
            result += stack.pop()   # the result before the parenthesis
    return result + sign * num

pop 순서가 중요합니다. 부호를 나중에 push했으니 먼저 pop됩니다.

추적

수식: 1-(2+3).

1 - (2 + 3) = -4로 일치합니다.

단항 마이너스

맨 앞의 마이너스는 별도 코드 없이 처리됩니다. 시작할 때 num이 0이므로, 첫 -는 결과에 sign * 0을 더한 뒤 부호를 -1로 설정합니다. ( 뒤에서도 마찬가지입니다. 저장된 상태가 result를 0으로, sign을 +1로 초기화하므로 (-2)도 같은 방식으로 처리됩니다.

복잡도

• 시간: O(n), 문자열을 한 번 순회합니다.
• 공간: 괄호가 깊게 중첩된 최악의 경우 O(n)입니다. 여는 괄호마다 스택에 값 두 개가 들어가기 때문입니다.

중첩 괄호와 단항 마이너스가 있는 무작위 수식 4,000개로 이 함수를 테스트하면서 Python 자체 평가 결과와 비교했는데, 모두 일치했습니다.

대안: 재귀

수식을 파싱하다가 (를 만나면 자기 자신을 호출하는 재귀 함수로도 작성할 수 있습니다. 읽기는 자연스럽지만 입력이 깊게 중첩되면 재귀 한도에 걸릴 위험이 있으니, Python에서는 스택 버전이 더 안전합니다.

면접관이 요구하는 확장

엣지 케이스

흔한 실수

1. 각 숫자를 따로따로 하나의 수로 취급하기.
2. 마지막에 마지막 sign * num을 더하는 걸 잊기.
3. pop 순서를 틀리기.
4. 연산자 뒤에 num을 초기화하지 않기.
5. 맨 앞의 마이너스를 잘못 처리하기.

면접에서 설명하는 방법

1. 허용되는 문자와 단항 마이너스가 나오는지 확인합니다.
2. 우선순위 문제는 없으니 괄호만 어렵다고 말합니다.
3. 세 변수와 스택이 저장하는 것을 설명합니다.
4. 화이트보드에서 1-(2+3)을 따라가 봅니다.
5. 복잡도를 말한 뒤 Calculator II 확장을 언급합니다.

관련 연습

복잡도 용어는 Big O 치트 시트를, AI LeetCode 튜터 가이드와 코딩 인터뷰 어시스턴트 가이드도 참고하세요. Valid Parentheses와 Decode String도 같은 스택 아이디어를 씁니다.

연습할 때는 추적 과정을 소리 내어 설명하세요. 모의 면접 기록을 보면 스택의 목적을 제대로 설명했는지 알 수 있습니다. 실시간 평가에서는 AI 도구에 관한 회사 규칙을 따르세요.