C++로 접두사 표현식의 식 트리(Expression Tree) 구성하기

식 트리(Expression Tree)는 산술 표현식을 나타내기 위해 사용되는 이진 트리입니다. 식 트리에서는 내부 노드가 연산자에 해당하고, 각 리프 노드가 피연산자에 해당합니다. 이 글에서는 접두사(prefix) 형태로 주어진 표현식으로부터 식 트리를 구성한 뒤, 전위(preorder), 중위(inorder), 후위(postorder) 세 가지 순회 결과를 모두 출력하는 C++ 프로그램을 소개합니다.

식 트리 구성 원리

접두사 표현식은 연산자가 피연산자보다 앞에 오는 형태입니다. 따라서 트리를 만들 때는 문자열을 오른쪽 끝에서 왼쪽으로 한 글자씩 읽어가며 처리하는 것이 편리합니다.

• 읽은 문자가 숫자(피연산자)라면 노드를 생성해 스택에 push 합니다.
• 읽은 문자가 연산자(+, -, *, /)라면 스택에서 노드 두 개를 pop 하여 각각 왼쪽·오른쪽 자식으로 연결한 뒤, 이 연산자 노드를 다시 스택에 push 합니다.
• 모든 문자를 처리하고 나면 스택의 top에 남아 있는 노드가 곧 식 트리의 루트가 됩니다.

알고리즘

시작
    ExpressionTree 클래스 - 다음 함수들을 포함:

    push(): 노드를 스택에 삽입
        스택이 비어 있으면 → 노드를 첫 번째 요소로 push
        그렇지 않으면 → 노드를 push하고 top으로 지정

    pop(): 스택에서 노드를 꺼냄
        스택이 비어 있으면 → "Underflow" 출력
        그렇지 않으면 → 노드를 pop하고 top 갱신

    insert(): 문자 하나를 처리
        숫자이면 → 노드를 생성해 push
        연산자이면 → 노드 두 개를 pop해 자식으로 연결한 뒤 push
        그 외에는 → "Invalid Expression" 출력

    postOrder(): 후위 순회
        트리가 비어 있지 않으면
            postOrder(ptr->l)
            postOrder(ptr->r)
            루트 값을 ptr->d로 출력

    inOrder(): 중위 순회
        트리가 비어 있지 않으면
            inOrder(ptr->l)
            루트 값을 ptr->d로 출력
            inOrder(ptr->r)

    preOrder(): 전위 순회
        트리가 비어 있지 않으면
            루트 값을 ptr->d로 출력
            preOrder(ptr->l)
            preOrder(ptr->r)
끝

예제 코드

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;

// 트리 노드 선언
class TreeN {
   public:
      char d;
      TreeN *l, *r;
      TreeN(char d) {
         this->d = d;
         this->l = NULL;
         this->r = NULL;
      }
};

// 스택 노드 선언
class StackNod {
   public:
      TreeN *treeN;
      StackNod *n;
      StackNod(TreeN *treeN) { // 생성자
         this->treeN = treeN;
         n = NULL;
      }
};

class ExpressionTree {
   private:
      StackNod *top;
   public:
      ExpressionTree() {
         top = NULL;
      }

      void clear() {
         top = NULL;
      }

      // 노드를 스택에 push
      void push(TreeN *ptr) {
         if (top == NULL)
            top = new StackNod(ptr);
         else {
            StackNod *nptr = new StackNod(ptr);
            nptr->n = top;
            top = nptr;
         }
      }

      // 스택에서 노드를 pop
      TreeN *pop() {
         if (top == NULL) {
            cout<<"Underflow"<<endl;
         } else {
            TreeN *ptr = top->treeN;
            top = top->n;
            return ptr;
         }
      }

      TreeN *peek() {
         return top->treeN;
      }

      // 문자 하나를 트리에 삽입
      void insert(char val) {
         if (isDigit(val)) {
            TreeN *nptr = new TreeN(val);
            push(nptr);
         } else if (isOperator(val)) {
            TreeN *nptr = new TreeN(val);
            nptr->l = pop();
            nptr->r = pop();
            push(nptr);
         } else {
            cout<<"Invalid Expression"<<endl;
            return;
         }
      }

      bool isDigit(char ch) {
         return ch >= '0' && ch <= '9';
      }

      bool isOperator(char ch) {
         return ch == '+' || ch == '-' || ch == '*' || ch == '/';
      }

      int toDigit(char ch) {
         return ch - '0';
      }

      // 접두사 표현식을 오른쪽에서 왼쪽으로 읽으며 트리 생성
      void buildTree(string eqn) {
         for (int i = eqn.length() - 1; i >= 0; i--)
            insert(eqn[i]);
      }

      void postfix() {
         postOrder(peek());
      }

      // 후위 순회
      void postOrder(TreeN *ptr) {
         if (ptr != NULL) {
            postOrder(ptr->l);
            postOrder(ptr->r);
            cout<<ptr->d;
         }
      }

      void infix() {
         inOrder(peek());
      }

      // 중위 순회
      void inOrder(TreeN *ptr) {
         if (ptr != NULL) {
            inOrder(ptr->l);
            cout<<ptr->d;
            inOrder(ptr->r);
         }
      }

      void prefix() {
         preOrder(peek());
      }

      // 전위 순회
      void preOrder(TreeN *ptr) {
         if (ptr != NULL) {
            cout<<ptr->d;
            preOrder(ptr->l);
            preOrder(ptr->r);
         }
      }
};

int main() {
   string s;
   ExpressionTree et;
   cout<<"\nEnter equation in Prefix form: ";
   cin>>s;
   et.buildTree(s);
   cout<<"\nPrefix : ";
   et.prefix();
   cout<<"\n\nInfix : ";
   et.infix();
   cout<<"\n\nPostfix : ";
   et.postfix();
}

실행 결과

Enter equation in Prefix form: ++7*626
Prefix : ++7*626
Infix : 7+6*2+6
Postfix : 762*+6+

결과 해석

입력된 접두사 표현식 ++7*626은 중위 표기로 7+6*2+6, 즉 "(7 + 6*2) + 6"과 같은 수식입니다. 동일한 식 트리를 어떤 방식으로 순회하느냐에 따라 접두사, 중위, 후위 표현식이 각각 얻어진다는 점을 실행 결과를 통해 확인할 수 있습니다.