use std::io::{self, Read}; #[derive(Clone, Copy, PartialEq, Eq)] enum Token { LParen, Bar, RParen, Good, } struct Node { token: Token, prev: usize, } fn push(nodes: &mut Vec, top: usize, token: Token) -> usize { nodes.push(Node { token, prev: top }); nodes.len() - 1 } fn token_at(nodes: &[Node], top: usize) -> Option { if top == 0 { None } else { Some(nodes[top].token) } } fn append_char(nodes: &mut Vec, top: usize, c: &str) -> usize { let token = match c { "(" => Token::LParen, "|" => Token::Bar, ")" => Token::RParen, _ => unreachable!(), }; let original_top = push(nodes, top, token); if token != Token::RParen { return original_top; } let mut p = nodes[original_top].prev; if token_at(nodes, p) == Some(Token::Good) { p = nodes[p].prev; } if token_at(nodes, p) != Some(Token::Bar) { return original_top; } p = nodes[p].prev; if token_at(nodes, p) == Some(Token::Good) { p = nodes[p].prev; } if token_at(nodes, p) != Some(Token::LParen) { return original_top; } let rest = nodes[p].prev; if token_at(nodes, rest) == Some(Token::Good) { rest } else { push(nodes, rest, Token::Good) } } fn is_good(nodes: &[Node], top: usize) -> bool { top == 0 || (nodes[top].token == Token::Good && nodes[top].prev == 0) } fn main() { let mut input = String::new(); io::stdin().read_to_string(&mut input).unwrap(); let mut it = input.split_whitespace(); let q: usize = it.next().unwrap().parse().unwrap(); let mut nodes = vec![Node { token: Token::Good, prev: 0, }]; let mut states = vec![0_usize; q + 1]; let mut len = 0_usize; let mut out = String::new(); for _ in 0..q { let ty = it.next().unwrap(); if ty == "1" { let c = it.next().unwrap(); let top = append_char(&mut nodes, states[len], c); len += 1; states[len] = top; } else { len -= 1; } if is_good(&nodes, states[len]) { out.push_str("Yes\n"); } else { out.push_str("No\n"); } } print!("{}", out); }