#include #define MAXQ 800005 typedef struct { int prev; char mode; // 0 = LEFT, 1 = RIGHT } Node; Node nodes[MAXQ]; int nodeCnt = 0; /* stateValid[i] = 현재 문자열 길이가 i일 때, 그 prefix가 파싱 가능한지 stateTop[i] = 그때 열린 괄호 스택의 top node index */ char stateValid[MAXQ]; int stateTop[MAXQ]; int main(void) { int Q; scanf("%d", &Q); int len = 0; stateValid[0] = 1; stateTop[0] = 0; for (int qi = 0; qi < Q; qi++) { int type; scanf("%d", &type); if (type == 1) { char c; scanf(" %c", &c); char valid = stateValid[len]; int top = stateTop[len]; len++; if (!valid) { stateValid[len] = 0; stateTop[len] = top; } else { if (c == '(') { ++nodeCnt; nodes[nodeCnt].prev = top; nodes[nodeCnt].mode = 0; // LEFT stateValid[len] = 1; stateTop[len] = nodeCnt; } else if (c == '|') { if (top != 0 && nodes[top].mode == 0) { ++nodeCnt; nodes[nodeCnt].prev = nodes[top].prev; nodes[nodeCnt].mode = 1; // RIGHT stateValid[len] = 1; stateTop[len] = nodeCnt; } else { stateValid[len] = 0; stateTop[len] = top; } } else { // c == ')' if (top != 0 && nodes[top].mode == 1) { stateValid[len] = 1; stateTop[len] = nodes[top].prev; } else { stateValid[len] = 0; stateTop[len] = top; } } } } else { // type == 2 len--; } if (stateValid[len] && stateTop[len] == 0) { printf("Yes\n"); } else { printf("No\n"); } } return 0; }