ABC428 C – Brackets Stack Query

C - Brackets Stack Query

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

(と)の数をカウントして、同数になったときに良い括弧列とする形にしました。

ただし、)(のような形は良い括弧列ではないので(の個数が)の個数以下の時に)がきたら、その場所を記憶しておき、その括弧がなくならないと(と)が同数でも良い括弧列とみなさないことにしました。

例えば()の時、次に)が来た場合、(の個数が)の個数以下なので)の2つ目を記憶しておき、)の2つ目が取り除かれないと(と)が同数でも良い括弧列とみなされないといった形です

以下でACできました。

def i_map(): return map(int, input().split())
def i_list(): return list(map(int, input().split()))

q = int(input())

l = 0
r = 0
a = []
flag = -1

for i in range(q):
  que = input().split()
  if que[0] == '1':
    if que[1] == '(':
      a.append('(')
      l+=1
    else:
      if flag==-1 and l <= r:
        flag = r
      a.append(')')
      r+=1
  else:
    tmp = a.pop(-1)
    if tmp == '(':
      l-=1
    else:
      r-=1
    if flag == r:
      flag = -1

  if l == r and flag == -1:
    print('Yes')
  else:
    print('No')Code language: Python (python)