C++로 삼항 연산자 표현식을 이진 트리로 변환하는 방법

이 튜토리얼에서는 C++를 사용하여 삼항 연산자(ternary operator)로 작성된 표현식을 이진 트리(binary tree)로 변환하는 프로그램을 다룹니다.

삼항 표현식은 a?b:c와 같은 형태로, 조건에 따라 두 가지 선택지 중 하나를 고르는 구조입니다. 여기서 우리의 목표는 주어진 삼항 표현식을 가능한 경로(선택지)에 따라 이진 트리 형태로 변환하는 것입니다.

문제 접근 방법

삼항 표현식은 중첩될 수 있기 때문에(예: a?b?c:d:e), 재귀적으로 파싱하는 것이 가장 효율적입니다. 기본 아이디어는 다음과 같습니다.

현재 위치의 문자는 해당 노드의 데이터가 됩니다.
다음 문자가 '?'라면, '?' 뒤의 표현식은 왼쪽 자식 서브트리가 되고, ':' 뒤의 표현식은 오른쪽 자식 서브트리가 됩니다.
다음 문자가 '?'가 아니라면, 해당 노드는 리프 노드이므로 그대로 반환합니다.

예제 코드

#include<bits/stdc++.h>
using namespace std;
// 트리 노드 구조체 정의
struct Node {
    char data;
    Node *left, *right;
};
// 새 노드 생성 함수
Node *newNode(char Data){
    Node *new_node = new Node;
    new_node->data = Data;
    new_node->left = new_node->right = NULL;
    return new_node;
}
// 삼항 표현식을 이진 트리로 변환하는 함수
Node *convertExpression(string str, int & i){
    // 현재 문자를 저장
    Node * root =newNode(str[i]);
    // 마지막 문자라면 기저 사례(base case)로 반환
    if(i==str.length()-1)
        return root;
        i++;
    // 다음 문자가 '?'라면,
    // 현재 노드에 서브트리가 존재함
    if(str[i]=='?'){
        // '?' 건너뛰기
        i++;
        root->left = convertExpression(str,i);
        // ':' 문자 건너뛰기
        i++;
        root->right = convertExpression(str,i);
        return root;
    }
    else return root;
}
// 이진 트리 출력 함수 (전위 순회)
void display_tree( Node *root){
    if (!root)
        return ;
    cout << root->data <<" ";
    display_tree(root->left);
    display_tree(root->right);
}
int main(){
    string expression = "a?b?c:d:e";
    int i=0;
    Node *root = convertExpression(expression, i);
    display_tree(root) ;
    return 0;
}

출력 결과

a b c d e

코드 동작 원리

입력 표현식 a?b?c:d:e를 예로 들면, 변환 과정은 다음과 같이 진행됩니다.

첫 번째 문자 'a'가 루트 노드가 되고, 바로 뒤에 '?'가 있으므로 왼쪽과 오른쪽 서브트리를 재귀적으로 생성합니다.
'?' 다음인 'b'부터 처리하며, 'b' 역시 뒤에 '?c:d'가 있으므로 왼쪽 자식으로 'c', 오른쪽 자식으로 'd'를 갖습니다.
':' 뒤의 'e'는 더 이상 '?'가 없으므로 리프 노드가 되어 'a'의 오른쪽 자식이 됩니다.

결과적으로 생성된 트리를 전위 순회(preorder traversal) 방식으로 출력하면 a b c d e가 출력됩니다. 이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n), 재귀 호출 깊이는 표현식 길이에 비례하여 O(n)의 공간 복잡도를 가집니다.