[BOJ] 1918번: 후위 표기식 (C++)

0. 문제

https://www.acmicpc.net/problem/1918

 

간단한 괄호가 포함된 중위 표기식을 후위 표기식으로 변환하는 문제이다. 풀이 시 연산 순서에 주의하여야 한다.

 

1. 아이디어

문제를 보고 떠오른 것은 프로그래밍 언어 파싱 이론에서의 Parse Tree이다. 부모 노드가 연산자, 자식 노드가 피연산자가 되는 트리로, 순회 순서에 따라 전위/중위/후위 표기식으로 읽을 수 있으며, 그에 따른 실제 연산도 가능하다. 트리 구조이기 때문에 피연산자인 자식 노드가 다른 노드의 연산자, 즉 부모 노드일 수 있다.

예로 A+B*C-D/E의 Parse Tree를 구성하면 다음과 같다.

Post Order 순회 시 ABC*+DE/- 순서로 후위 표기식과 동일하다는 것을 확인할 수 있다.

2. 풀이

#include <iostream>
#include <stack>
#include <vector>

struct node
{
    char c;
    struct node *left = nullptr;
    struct node *right = nullptr;
    struct node *parent = nullptr;
};

void append(struct node **root, struct node *op, struct node *tree, struct node **last_term)
{
    if (*root == nullptr)
    {
        *root = tree;
        *last_term = tree;
    }
    else
    {
        if (op->c == '*' || op->c == '/')
        {
            struct node *parent = (*last_term)->parent;
            (*last_term)->parent = op;
            tree->parent = op;
            op->left = (*last_term);
            op->right = tree;
            op->parent = parent;
            if (parent != nullptr)
            {
                parent->right = op;
            }
            else
            {
                *root = op;
            }
            *last_term = op;
        }
        else
        {
            (*root)->parent = op;
            tree->parent = op;
            op->left = *root;
            op->right = tree;
            *root = op;
            *last_term = tree;
        }
    }
}

struct node *parse(std::string str)
{
    std::vector<std::string> chunks;
    struct node *root = nullptr;
    struct node *op = nullptr;
    struct node *last_term = nullptr;
    std::string::size_type i = 0;
    while (i < str.length())
    {
        if (str[i] == '(')
        {
            std::stack<std::string::size_type> stack;
            std::string::size_type j = i + 1;
            stack.push(i);
            while (j < str.length())
            {
                if (str[j] == '(')
                {
                    stack.push(j);
                }
                else if (str[j] == ')')
                {
                    stack.pop();
                }
                if (stack.empty())
                {
                    break;
                }
                ++j;
            }
            struct node *sub = parse(str.substr(i + 1, j - i - 1));
            append(&root, op, sub, &last_term);
            i = j;
        }
        else
        {
            if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/')
            {
                op = new struct node({str[i]});
            }
            else
            {
                append(&root, op, new struct node({str[i]}), &last_term);
            }
        }
        ++i;
    }
    return root;
}

void postorder(struct node *tree)
{
    if (tree->left != nullptr)
    {
        postorder(tree->left);
    }
    if (tree->right != nullptr)
    {
        postorder(tree->right);
    }
    std::cout << tree->c;
    if (tree->left != nullptr)
    {
        delete tree->left;
        tree->left = nullptr;
    }
    if (tree->right != nullptr)
    {
        delete tree->right;
        tree->right = nullptr;
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    std::string input;
    std::cin >> input;
    struct node *tree = parse(input);
    postorder(tree);
    delete tree;
    tree = nullptr;
}

괄호는 하나의 term이므로, 파싱 도중 여는 괄호를 확인한 경우 해당하는 닫는 괄호 사이의 식을 재귀적으로 파싱한다. 그리고 그 결과물인 서브 트리를 기존 트리에 append한다.

append 함수는 연산자 하나와 피연산자 하나를 기존 트리의 적절한 위치에 추가하는 함수로, 다음과 같은 규칙에 의해 작성되었다.

1. 파라미터 op로 전달된, 추가해야하는 연산자가 + 또는 -인 경우, 연산자 노드가 루트가 되고, 왼쪽에 기존 트리, 오른쪽에 새로 추가되는 피연산자 노드 또는 트리가 추가된다.

2. 연산자가 * 또는 /인 경우, 마지막으로 추가한 term에 해당하는 트리를 추가하는 연산자의 왼쪽 자식으로 삼는다. 오른쪽 자식은 추가하는 피연산자 노드이다. 그리고 기존 term의 부모에 대하여 새로 추가한 연산자 노드는 오른쪽 자식이 된다.

그림으로 표현하면 다음과 같다.

이런 규칙이 발생하는 이유는 곱셉, 나눗셈의 연산 순서 때문이다. A+B*C를 봤을 때, 기존 A+B만 있는 상태에서 B는 last_term이 될 것이고, *C를 추가하게 되면 B*C를 하나의 term으로 보아야하기 때문에 +의 자식 노드가 되어야할 것이다.