Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 표현식 트리(Expression Tree) 알고리즘: 후위 표기식 변환 프로그램

표현식 트리란?

표현식 트리(Expression Tree)는 산술 또는 논리 수식을 표현하기 위해 사용되는 이진 트리입니다. 표현식 트리에서는 내부 노드(internal node)가 연산자에 해당하고, 리프 노드(leaf node)가 피연산자에 해당합니다. 예를 들어 중위 표기식 "a+b*c"는 루트가 '+', 왼쪽 자식이 'a', 오른쪽 서브트리가 '*'를 루트로 하는 트리 형태로 표현됩니다.

이 글에서 소개하는 C++ 프로그램은 후위 표기식(postfix expression)을 입력으로 받아 이에 대응하는 표현식 트리를 생성한 뒤, 중위 순회(inorder traversal)를 통해 중위 표기식(infix expression)을 출력합니다.

알고리즘

Begin
    function construct_expression_tree():
        피연산자일 때 Flag = 1
        연산자일 때 Flag = -1
        S = suffix[0] : 수식의 첫 번째 문자를 읽음
    i = 0부터 s != 0이 아닐 때까지 반복
        현재 기호가 피연산자인지 연산자인지 확인
        중위 순회를 위해 inorder() 함수 호출
        결과 출력
        i 증가
End.

핵심 동작 원리

표현식 트리 생성은 스택(stack)을 이용해 이루어집니다. 후위 표기식을 왼쪽부터 한 문자씩 읽으며 다음 과정을 반복합니다.

  1. 읽은 문자가 피연산자라면, 해당 문자를 값으로 갖는 새 노드를 생성해 스택에 push합니다.
  2. 읽은 문자가 연산자라면, 스택에서 노드 두 개를 pop합니다. 먼저 꺼낸 노드는 오른쪽 자식, 나중에 꺼낸 노드는 왼쪽 자식으로 연결하고, 연산자를 루트로 하는 새 서브트리를 만들어 다시 스택에 push합니다.
  3. 모든 문자를 처리하면 스택에는 완성된 표현식 트리의 루트 노드 하나만 남게 됩니다.

예제 코드

#include <iostream>
using namespace std;

struct n { // 노드 선언
    char d;
    n *l;
    n *r;
};
char pf[50];
int top = -1;
n *a[50];
int r(char inputch) { // 기호가 연산자인지 피연산자인지 확인
    if (inputch == '+' || inputch == '-' || inputch == '*' || inputch == '/')
        return (-1);
    else if (inputch >= 'A' || inputch <= 'Z')
        return (1);
    else if (inputch >= 'a' || inputch <= 'z')
        return (1);
    else
        return (-100);
}
void push(n *tree) { // 스택에 노드 삽입(push)
    top++;
    a[top] = tree;
}
n *pop() {
    top--;
    return (a[top + 1]);
}
void construct_expression_tree(char *suffix) {
    char s;
    n *newl, *p1, *p2;
    int flag;
    s = suffix[0];
    for (int i = 1; s != 0; i++) {
        flag = r(s);
        if (flag == 1) {
            newl = new n;
            newl->d = s;
            newl->l = NULL;
            newl->r = NULL;
            push(newl);
        } else {
            p1 = pop();
            p2 = pop();
            newl = new n;
            newl->d = s;
            newl->l = p2;
            newl->r = p1;
            push(newl);
        }
        s = suffix[i];
    }
}

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

int main(int argc, char **argv) {
    cout << "Enter Postfix Expression : ";
    cin >> pf;
    construct_expression_tree(pf);
    cout << "\nInfix Expression : ";
    inOrder(a[0]);
    return 0;
}

코드 설명

  • r() 함수: 입력 문자가 '+', '-', '*', '/' 중 하나이면 -1(연산자)을 반환하고, 영문자이면 1(피연산자)을 반환하여 문자의 종류를 판별합니다.
  • push(), pop() 함수: 배열 기반 스택에 트리 노드를 저장하고 꺼내는 역할을 담당합니다.
  • construct_expression_tree() 함수: 후위 표기식을 한 글자씩 읽어 앞서 설명한 규칙대로 노드를 생성하고 결합하며 트리를 완성합니다.
  • inOrder() 함수: 왼쪽 서브트리 → 루트 → 오른쪽 서브트리 순서로 재귀적으로 방문하여 중위 표기식을 출력합니다.

참고: 위 코드의 r() 함수에서 알파벳 범위 검사 조건이 ||(OR)로 작성되어 있어 논리적으로는 항상 참이 됩니다. 다만 연산자 검사가 먼저 수행되기 때문에 예제에서는 정상적으로 동작합니다. 더 엄격한 판별을 위해서는 &&(AND)를 사용해 inputch >= 'A' && inputch <= 'Z' 형태로 수정하는 것이 좋습니다.

실행 결과

Enter Postfix Expression : 762*+6+
Infix Expression : 7+6*2+6

후위 표기식 "762*+6+"를 입력하면 프로그램이 이를 표현식 트리로 변환한 뒤, 중위 순회를 통해 중위 표기식 "7+6*2+6"을 출력합니다. 이처럼 표현식 트리는 컴파일러의 수식 해석, 계산기 구현 등 다양한 분야에서 활용되는 핵심 자료구조입니다.