BOJ 4817 괄호

📝 문제 정보

링크: https://www.acmicpc.net/problem/4817

🧐 관찰 및 접근

최대한 괄호를 제거해야 한다.
- 괄호 안에 덧셈이 없다면, 해당 괄호는 제거해도 된다.
- 어떨 때 괄호를 살려야 하는가?
  - $((x+y)z)$와 같이, 어떤 괄호로 이루어진 덧셈이 포함된 식과 어떤 식이 곱해지는 경우 남겨야 한다.
  - 라곤 했지만… 구현이 만만치 않다.
이를 위해 추상 구문 트리 라는것을 보통 사용한다고 한다.
- 노드단위로 연산을 나타내자.
- 이때 파싱 과정에서, 연산 우선순위가 낮은걸 먼저 해야한다. (상위 노드가 먼저 계산되므로)
  - 따라서 덧셈 -> 곱셈 -> 괄호의 순서로 진행하자.
쉽지 않은데.. 이런 생각보다 파서를 만드는 과정이 재밌다.
- 전산언어학 문제를 좀더 풀어보도록 하자.

💻 풀이

코드 (C++):

struct Node{
    char type;
    char var;
    Node *left, *right;

    Node(char c){ // var
        type = 'v';
        var = c;
        left = right = nullptr;
    }

    Node(char op, Node *l, Node *r){ // op
        type = 'o';
        var = op;
        left = l;
        right = r;
    }
};

struct AST{
    Node *root;

    AST(Node *r) : root(r) {}

    string emit(Node *n, char parOp){
        if(n->type == 'v') return string(1, n->var);
        if(n->var == '+'){
            string L = emit(n->left, '+');
            string R = emit(n->right, '+');
            if(parOp == '*') return "(" + L + "+" + R + ")";
            return L + "+" + R;
        }

        return emit(n->left, '*') + emit(n->right, '*');
    }

    string toString(){
        return emit(root, 0);
    }
};

struct Parser{
    const string &S;
    int pos;

    Parser(const string &s): S(s), pos(0){}

    Node *parseVal(){
        if(S[pos] == '('){
            pos++;
            Node *node = parsePlus();
            pos++;
            return node;
        }
        return new Node(S[pos++]);
    }

    Node *parseMul(){
        Node *node = parseVal();
        while(pos < (int)S.size() && (islower(S[pos]) || S[pos] == '(')){
            Node *right = parseVal();
            node = new Node('*', node, right);
        }
        return node;
    }

    Node *parsePlus(){
        Node *node = parseMul();
        while(pos < (int)S.size() && S[pos] == '+'){
            pos++;
            Node *right = parseMul();
            node = new Node('+', node, right);
        }
        return node;
    }

    AST parse(){
        return AST(parsePlus());
    }
};

void solve(){
    string S;
    while(cin >> S){
        Parser parser(S);
        AST ast = parser.parse();
        cout << ast.toString() << "\n";
    }
}