#include #include #define MAXQ 800005 static char char_stack[MAXQ]; static int char_top = 0; /* * frame_stack: parser frame stack * 0 = this '(' is waiting for its '|' * 1 = this '(' has seen its '|', waiting for ')' */ static int frame_stack[MAXQ]; static int frame_top = 0; /* * error_stack[i] = 1 if the string is invalid after i characters. * error_stack[0] = 0 (empty string is always valid). */ static char error_stack[MAXQ]; static int error_top = 1; int main(void) { error_stack[0] = 0; int Q; scanf("%d\n", &Q); while (Q--) { int type; scanf("%d", &type); if (type == 1) { char c; scanf(" %c", &c); char_stack[char_top++] = c; int cur_err = error_stack[error_top - 1]; if (cur_err) { error_stack[error_top++] = 1; } else { if (c == '(') { frame_stack[frame_top++] = 0; error_stack[error_top++] = 0; } else if (c == '|') { if (frame_top == 0 || frame_stack[frame_top - 1] == 1) { error_stack[error_top++] = 1; } else { frame_stack[frame_top - 1] = 1; error_stack[error_top++] = 0; } } else { /* ')' */ if (frame_top == 0 || frame_stack[frame_top - 1] == 0) { error_stack[error_top++] = 1; } else { frame_top--; error_stack[error_top++] = 0; } } } } else { /* type == 2 */ char c = char_stack[--char_top]; int was_err_this = error_stack[--error_top]; if (!was_err_this) { /* undo the frame_stack change made by this character */ if (c == '(') { frame_top--; } else if (c == '|') { frame_stack[frame_top - 1] = 0; } else { /* ')' */ frame_stack[frame_top++] = 1; } } } int valid = !error_stack[error_top - 1] && frame_top == 0; puts(valid ? "Yes" : "No"); } return 0; }