Parsing

📝 문제 정보 # 링크: 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"; } } 🔒 구현 코드 잠금