임의로 중첩된 삼항 표현식(ternary expression)을 나타내는 문자열이 주어졌을 때, 해당 표현식의 최종 결과를 계산하는 문제를 살펴보겠습니다. 입력으로 주어지는 표현식은 항상 유효하며, 숫자 0~9, ?, :, T, F 다섯 종류의 문자로만 구성됩니다. 여기서 T와 F는 각각 참(True)과 거짓(False)을 의미합니다.
문제의 제약 조건
- 주어진 문자열의 길이는 10,000 이하여야 합니다.
- 각 숫자는 한 자리(0~9)로만 구성됩니다.
- 조건식은 오른쪽에서 왼쪽 방향(right-to-left)으로 그룹화됩니다.
- 조건 부분은 항상
T또는F이며, 절대 숫자가 될 수 없습니다. - 표현식의 최종 결과는 항상 숫자 0~9,
T,F중 하나입니다.
동작 예시
예를 들어 입력이 "F?1:T?4:5"라고 해보겠습니다. 조건식이 오른쪽에서 왼쪽으로 그룹화되므로, 가장 오른쪽의 "T?4:5"가 먼저 평가되어 4를 반환합니다. 그러면 전체 식은 "F?1:4"가 되고, 조건이 F(거짓)이므로 최종 결과는 4가 됩니다.
해결 접근 방법
이 문제는 스택(stack)을 활용해 문자열을 뒤에서 앞으로 순회하는 방식으로 효율적으로 해결할 수 있습니다. 알고리즘은 다음과 같습니다.
- 결과를 담을 빈 문자열
ret과 문자열 길이n을 준비하고, 문자 저장용 스택st를 생성합니다. - 인덱스
i를n-1부터0까지 거꾸로 순회하며 다음을 수행합니다.x = s[i]로 현재 문자를 가져옵니다.- 스택이 비어 있지 않고 스택의 최상단이
'?'라면:'?'를 스택에서 제거(pop)합니다.first를 스택 최상단 값으로 설정한 뒤 두 개의 요소를 제거합니다.second를 스택 최상단 값으로 설정한 뒤 제거합니다.x가T이면first를, 그렇지 않으면second를 스택에 push합니다.
- 그 외의 경우에는 문자
x를 그대로 스택에 push합니다.
- 스택이 빌 때까지 최상단 값을
ret에 이어 붙이며 pop합니다. ret을 뒤집어(reverse) 반환합니다.
C++ 구현 예제
아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string parseTernary(string s) {
string ret = "";
int n = s.size();
stack <char> st;
for(int i = n - 1; i >= 0; i--){
char x = s[i];
if(!st.empty() && st.top() == '?'){
st.pop();
char first = st.top();
st.pop();
st.pop();
char second = st.top();
st.pop();
if(x == 'T'){
st.push(first);
}
else st.push(second);
}
else{
st.push(x);
}
}
while(!st.empty()){
ret += st.top();
st.pop();
}
reverse(ret.begin(), ret.end());
return ret;
}
};
main(){
Solution ob;
cout << (ob.parseTernary("F?1:T?4:5"));
}입력
"F?1:T?4:5"
출력
4
정리
이 알고리즘은 문자열을 뒤에서부터 한 번만 순회하기 때문에 시간 복잡도는 O(n)이며, 공간 복잡도 역시 스택 크기에 비례해 O(n)입니다. 조건식이 오른쪽에서 왼쪽으로 결합되는 특성 덕분에 역방향 순회와 스택을 조합하면 재귀 호출 없이도 중첩된 삼항 표현식을 간결하고 효율적으로 평가할 수 있습니다.