자료구조 및 알고리즘 #13 - Tree Traversal and Parsing

1. Tree traversal

 

트리의 모든 노드들을 방문하는 과정을 트리 순회, Tree Traversal 이라고 합니다. 이때 방문은 정말 "방문" 만 하는 것이 아니라 해당 노드에서 어떤 수행을 하는것을 의미합니다.

 

일반적으로 트리의 순회에는 다음과 같은 방법들이 있습니다.

• 전위 순회(Preorder)
• 중위 순회(Inorder)
• 후위 순회(Postorder)

이런 순회는 보통 DFS 를 통해 구현할 수 있습니다.

Traverse(Node *D)
{
    if (D == NULL) return;
    Visit(D); <- Preorder Traversal
    Traverse(D->Left);
    Visit(D); <- Inorder Traversal
    Traverse(D->Right);
    Visit(D); <- Postorder Traversal
}

 

Tree

이렇게 생긴 트리가 있을 때, 각 순회 방식에 따른 노드 방문의 순서는 어떻게 될까요?

• Preorder : 6, 4, 2, 1, 3, 5, 8, 7, 9
• Inorder : 1, 2, 3, 4, 5, 6, 7, 8, 9
• Postorder : 1, 3, 2, 5, 4, 7, 9, 8, 6

여기에서 각 순회 방식의 차이를 알 수 있습니다.

• Preorder의 특징 : (root) / (left) / (right) 의 재귀적 형태, 가장 처음 노드가 최상단 노드(루트 노드).
  • 6(root) / 4,2,1,3,5(left) / 8,7,9(right)
    • 4(root) / 2,1,3(left) / 5(right)         8(root) / 7(left) / 9(right)
      • 2(root) / 1(left) / 3(right)
• Inorder의 특징 : (left) / (root) / (right)
• Postorder의 특징 : (left) / (right) / (root) , 가장 마지막에 오는 노드가 최상단 노드(루트 노드)

(* 이러한 특징들로 인해, Preorder 와 Inorder 값만 이용하여 BT 의 형태를 찾을 수 있습니다.)

 

2. an Application

 

흔히 우리가 식을 표현할 때는 중위 표현식(* Infix Notation) 을 사용합니다. 예를 들어 (6 / 3 + 5) * (6 - 4) 의 형태가 있습니다. 하지만 이 외에도 전위 표현식과 후위 표현식이 있습니다.

 

* + / 6 3 5 - 6 4 의 형태는 전위 표현식(* Prefix Notation) 이라고 합니다.

6 3 / 5 + 6 4 - * 의 형태는 후위 표현식(* Postfix Notation) 이라고 합니다.

 

해당 표현식들은 () 를 사용하지 않아도 된다는 장점이 있습니다.

 

Parsing 은 컴파일러가 어떤 식을 해석하기 위한 방법입니다. Parsing 의 과정이 바로 중위 표현식을 트리로 만드는 것 입니다. 

Parsing

code generation

(* 위에서 만든 트리를 이용하여 Preorder traversal 을 하면 Prefix Notation, Postorder traversal 을 하면 Postfix Notation 이 됩니다. 그리고 컴파일러는 후위 표현식을 통해 code 를 생성합니다.)

 

자세한 알고리즘을 설명하기는 힘들고 간단히만 하자면

Stack 과 각 operator 의 우선순위를 이용하면 됩니다. 이때 중요한 점은 () 의 우선순위입니다.

• ... + ( ... ) ...  : 의 경우 () 안에 연산이 끝날 때까지 + 연산을 하지 못하므로, () 의 밖에서는 () 의 우선순위가 + 의 우선순위 보다 더 높습니다.
• ... ( ... + ... ) ... : 의 경우 () 안의 + 연산자는 ) 보다 우선순위가 높습니다. 왜냐하면 () 안의 + 연산자의 연산이 끝나고 나서 () 가 끝날 수 있기 때문입니다.
• 또한 연산자 Stack 에서 ( 과 ) 이 만나면 그냥 사라집니다.(* 괄호 안 연산 아에 끝)

만약 operator stack 내부에 operator 를 넣으려고 하는데 기존에 있던 operator 보다 새롭게 넣으려 했던 operator 가 우선순위가 낮으면 기존 stack 에 있던 operator 를 연산해줍니다.

 

(* 여기서 연산이란 operator 노드의 자식으로 operand 들을 넣어주는것을 말합니다.)

 

이렇게 해서 Stack 이 모두 비어버리면 연산은 끝, Tree 가 완성됩니다.

 

그리고 컴파일러는 이를 후위 표현식으로 만들어 하나하나의 코드를 이어 붙입니다.

#include <iostream>
#include <stack>
#include <string>

class Node{
public:
    char key;
    Node* L;
    Node* R;

    Node(char c){key = c; L = R = NULL;};
};

void treeTraversal(Node* n){
    if(n == NULL)
        return;
    treeTraversal(n->L);
    treeTraversal(n->R);
    std::cout << n->key;
}

// 해당 입력이 연산자인지 아닌지 구분해주는 함수
// 연산자가 맞으면 true, 아니면 false 를 return 한다.
bool isOperator(char c){
    if(c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')')
        return true;
    return false;
}

// 우선순위를 계산해주는 함수
// 여기서 중요한점은 괄호의 우선순위가 가장 낮다는 점이다.
// 특히 여는 괄호는 stack 에서 빼서 계산할때는 우선순위가 가장 낮지만
// 입력으로 여는 괄호를 받을 때는 우선순위가 가장 높다.
int calculatePriority(char c){
    if(c == '*' || c == '/')
        return 1;
    else if(c == '+' || c == '-')
        return 2;
    else { // ')' || '('
        return 3;
    }
}

// 계산해주는 함수
// 연산자 노드의 자식 노드로 피연산자들을 붙여준다.
Node* calculate(Node* op, Node* x, Node* y){
    op->L = y;
    op->R = x;
    return op;
}

// 이 Parsing 함수는 식의 처음과 마지막에 () 가 되있는 경우에만 정상작동을 보장합니다.
// 만약 () 가 없는 경우에도 작동시키려면
// 함수에 마지막에 stack 이 빌때까지 calculate 함수를 사용해주면 됩니다.
void Parsing(){
    std::string str;
    std::cin >> str;

    std::stack<Node*> operatorStack;
    std::stack<Node*> operandStack;
    
    for(int i=0; i<str.length(); i++){
        char c = str[i];
        if(isOperator(c)){
        // stack 이 비어있으면 바로 넣고 다음 입력을 받는다.
        // 그리고 여는 괄호는 우선순위가 무엇보다도 높으니
        // 우선순위를 계산하지 않고 바로 stack 에 넣어준다.
            if(operatorStack.empty() || c == '('){
                operatorStack.push(new Node(c));
                continue;
            }
            else{
                Node* prevOperatorNode = operatorStack.top();
                char prevOperator = prevOperatorNode->key;
                if(calculatePriority(prevOperator) <= calculatePriority(c)){
                    operatorStack.pop();
                    Node* operand1 = operandStack.top();
                    operandStack.pop();
                    Node* operand2 = operandStack.top();
                    operandStack.pop();
                    operandStack.push(calculate(prevOperatorNode, operand1, operand2));
                }
                if(c == ')' && operatorStack.top()->key == '('){
                    operatorStack.pop();
                    continue;
                }
                operatorStack.push(new Node(c));
            }
        }
        else{
            operandStack.push(new Node(c));
        }
    }
    treeTraversal(operandStack.top());
}

int main(){
	Parsing();
    return 0;
}