문제 소개
덧셈(+), 뺄셈(-), 곱셈(*), 나눗셈(/) 연산자로 이루어진 수학 표현식 문자열이 주어졌을 때, 파이썬의 내장 함수를 사용하지 않고 이 표현식을 직접 평가하여 결과를 반환하는 프로그램을 작성해 보겠습니다. 여기서 나눗셈(/)은 정수 나눗셈을 의미합니다.
예를 들어 입력이 s = "2+3*5/7"이라면 출력은 4가 됩니다. 연산자 우선순위에 따라 2 + ((3 * 5) / 7) = 2 + (15 / 7) = 2 + 2 = 4로 계산되기 때문입니다.
해결 접근 방법
이 문제의 핵심은 연산자 우선순위를 올바르게 처리하는 것입니다. 곱셈과 나눗셈이 덧셈과 뺄셈보다 먼저 수행되어야 하므로, 문자열을 뒤집어 뒤에서부터 한 글자씩 처리하는 방식을 사용합니다. 전체 알고리즘은 다음과 같이 진행됩니다.
- 주어진 문자열 s를 역순으로 뒤집습니다.
- get_value() 함수 정의
- 부호 sign을 1로 초기화합니다.
- s가 비어 있지 않고 마지막 문자가 '-'라면, 해당 문자를 제거하고 sign을 -1로 설정합니다.
- 값 value를 0으로 초기화한 뒤, s가 비어 있지 않고 마지막 문자가 숫자인 동안 value = value * 10 + 마지막 문자의 숫자 값을 반복하며 자릿수를 쌓습니다.
- sign * value를 반환합니다.
- get_term() 함수 정의
- term을 get_value()의 결과로 초기화합니다.
- s가 비어 있지 않고 마지막 문자가 '*' 또는 '/'인 동안, 연산자 op를 꺼내고 다음 값을 get_value()로 읽어 들입니다.
- op가 '*'이면 term = term * value로 갱신하고, '/'이면 term = floor(1.0 * term / value)로 정수 나눗셈을 수행합니다.
- term을 반환합니다.
- 메인 로직
- ans를 get_term()의 결과로 초기화합니다.
- s가 빌 때까지 연산자 op와 항 term을 차례로 꺼내며, op가 '+'이면 ans에 더하고 그렇지 않으면 뺍니다.
- 최종 ans를 반환합니다.
구현 예제
다음 파이썬 코드를 통해 위 알고리즘이 실제로 어떻게 동작하는지 확인할 수 있습니다.
from math import floor, trunc class Solution: def solve(self, s): s = list(s[::-1]) def get_value(): sign = 1 if s and s[-1] == "-": s.pop() sign = -1 value = 0 while s and s[-1].isdigit(): value *= 10 value += int(s.pop()) return sign * value def get_term(): term = get_value() while s and s[-1] in "*/": op = s.pop() value = get_value() if op == "*": term *= value else: term = floor(1.0 * term / value) return term ans = get_term() while s: op, term = s.pop(), get_term() if op == "+": ans += term else: ans -= term return ans ob = Solution() s = "2+3*5/7" print(ob.solve(s))
입력
"2+3*5/7"
출력
4
코드 동작 원리
이 코드는 세 부분으로 구성됩니다. 첫째, get_value()는 뒤집힌 문자열에서 연속된 숫자 문자를 하나씩 꺼내 10을 곱하고 더하는 방식으로 다자리 정수를 만들어냅니다. 숫자 앞에 붙은 음수 부호도 함께 처리합니다. 둘째, get_term()은 곱셈과 나눗셈처럼 우선순위가 높은 연산을 연속으로 처리하여 하나의 '항'을 완성합니다. 나눗셈에는 math.floor를 사용해 정수 결과를 얻습니다. 셋째, 메인 루프는 남은 '+'와 '-' 연산자를 기준으로 각 항을 더하거나 빼며 최종 답을 계산합니다.
문자열을 뒤집어 처리하기 때문에 복잡한 재귀 호출이나 별도의 파서 없이도 연산자 우선순위를 자연스럽게 반영할 수 있다는 점이 이 접근법의 가장 큰 장점입니다. 모든 문자를 정확히 한 번씩 처리하므로, 문자열의 길이를 n이라 할 때 시간 복잡도는 O(n)으로 매우 효율적입니다.