간단한 수식 문자열이 주어졌을 때, 해당 수식을 평가하는 기본 계산기를 구현해야 합니다. 수식 문자열에는 여는 괄호와 닫는 괄호, 덧셈(+)과 뺄셈(-) 부호, 음수가 아닌 정수, 그리고 공백이 포함될 수 있으며, 곱셈(*)과 나눗셈(/) 연산자도 함께 등장할 수 있습니다. 이때 정수 나눗셈은 0을 향해 절사(truncate toward zero)해야 합니다.
예를 들어 입력이 "6-4 / 2"라면 출력은 4가 됩니다.
접근 방법
이 문제는 연산 우선순위가 서로 다른 두 단계(덧셈·뺄셈 / 곱셈·나눗셈)를 각각 별도의 변수 쌍으로 관리하고, 괄호를 만나면 현재 상태를 스택에 저장했다가 닫는 괄호를 만났을 때 복원하는 방식으로 해결할 수 있습니다.
핵심 변수 설명
- l1 — 지금까지 확정된 누적 결과값
- l2 — 현재 진행 중인 곱셈/나눗셈 체인의 값
- o1 — 직전 덧셈/뺄셈 연산자 (+는 1, -는 -1)
- o2 — 직전 곱셈/나눗셈 연산자 (*는 1, /는 -1)
- st — 괄호 처리를 위한 스택
알고리즘 단계
- l1 := 0, l2 := 1로 초기화
- o1 := 1, o2 := 1로 초기화
- 스택 st 하나를 정의
- n := 문자열 s의 길이
- i := 0부터 i < n일 때까지 i를 1씩 증가시키며 반복:
- x := s[i]
- x가 '0' 이상 '9' 이하의 숫자라면:
- num := x - '0'
- (i + 1 < n 이고 s[i + 1]이 숫자인) 동안 반복:
- i를 1 증가
- num := (num * 10) + (s[i] - '0')
- l2 := (o2가 1이면 l2 * num, 아니면 l2 / num)
- x가 '('와 같다면:
- l1과 o1을 st에 삽입
- l2와 o2를 st에 삽입
- l1 := 0, o2 := 1로 초기화
- o1 := 1, l2 := 1로 초기화
- x가 ')'와 같다면:
- temp := l1 + o1 * l2
- o2 := st의 최상단 요소를 꺼낸 값
- l2 := st의 최상단 요소를 꺼낸 값
- o1 := st의 최상단 요소를 꺼낸 값
- l1 := st의 최상단 요소를 꺼낸 값
- l2 := (o2가 1이면 l2 * temp, 아니면 l2 / temp)
- x가 '*' 또는 '/'라면:
- o2 := (x가 '*'면 1, 아니면 -1)
- x가 '+' 또는 '-'라면:
- x가 '-'이면서 (i == 0 또는 바로 앞 문자 s[i - 1] == '(')라면 단항 음수이므로 o1 := -1로 설정하고 다음 반복으로 건너뜀
- l1 := l1 + o1 * l2
- o1 := (x가 '+'면 1, 아니면 -1)
- l2 := 1, o2 := 1로 초기화
- 최종적으로 l1 + o1 * l2를 반환
아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int calculate(string s) {
lli l1 = 0;
lli l2 = 1;
lli o1 = 1;
lli o2 = 1;
stack<lli> st;
lli n = s.size();
for (lli i = 0; i < n; i++) {
char x = s[i];
if (x >= '0' && x <= '9') {
lli num = x - '0';
while (i + 1 < n && s[i + 1] >= '0' && s[i + 1] <= '9') {
i++;
num = (num * 10) + (s[i] - '0');
}
l2 = (o2 == 1) ? l2 * num : l2 / num;
}
else if (x == '(') {
st.push(l1);
st.push(o1);
st.push(l2);
st.push(o2);
l1 = 0;
o2 = 1;
o1 = 1;
l2 = 1;
}
else if (x == ')') {
lli temp = l1 + o1 * l2;
o2 = st.top();
st.pop();
l2 = st.top();
st.pop();
o1 = st.top();
st.pop();
l1 = st.top();
st.pop();
l2 = (o2 == 1) ? l2 * temp : l2 / temp;
}
else if (x == '*' || x == '/') {
o2 = (x == '*') ? 1 : -1;
}
else if (x == '+' || x == '-') {
if (x == '-' && (i == 0 || (i - 1 >= 0 && s[i - 1] == '('))) {
o1 = -1;
continue;
}
l1 += o1 * l2;
o1 = (x == '+') ? 1 : -1;
l2 = 1;
o2 = 1;
}
}
return l1 + o1 * l2;
}
};
main(){
Solution ob;
cout << (ob.calculate("(5+9*3)/8"));
}입력
"(5+9*3)/8"
출력
4
동작 원리 살펴보기
입력 "(5+9*3)/8"이 어떻게 처리되는지 단계별로 확인해 보겠습니다.
- '(' 만남 — 현재 상태(l1=0, o1=1, l2=1, o2=1)를 스택에 저장하고 내부 값을 초기화합니다.
- '5' 처리 — l2 = 1 × 5 = 5
- '+' 처리 — l1 = 0 + 1×5 = 5, 새로운 l2 = 1로 시작
- '9', '*', '3' 처리 — l2 = 9 × 3 = 27
- ')' 만남 — 괄호 내부 결과 temp = 5 + 1×27 = 32를 계산한 뒤, 스택에서 이전 상태를 복원하고 l2 = 1 × 32 = 32로 설정합니다.
- '/', '8' 처리 — l2 = 32 ÷ 8 = 4
- 종료 — 최종 결과 l1 + o1 × l2 = 0 + 1×4 = 4를 반환합니다.
이처럼 두 단계의 연산자를 분리 관리하고 스택으로 괄호 컨텍스트를 보존하면, 한 번의 순회(O(n))만으로 복잡한 수식도 정확하게 평가할 수 있습니다.