AOJ 2340 : Carpenters' Language
問題リンク:Carpenters' Language | Aizu Online Judge
問題概要:
S -> SS | (S) | )S( | ε
このような文法の言語があり、入力がその言語になっているなどうが判定せよ
使用した言語:C++
解法:
'('と')'の数が等しい場合は全て正しい文法なので'('と')'の数を数え,両方の数がひとしいなら"Yes",異なるなら"No"と出力すればよい
ここで注意すべき点は、'('と')'の数を数える際にはlong longを使わなければならないこと
クエリーが10^5で'('と')'の数は最大2^20なのでintには収まらない
コード:
#include<iostream> using namespace std; int main() { int n; cin >> n; long long cnt = 0; for(int i=0;i<n;i++) { int a,b; char c; cin >> a >> c >> b; c == '('?cnt += b:cnt -= b; !cnt?cout << "Yes" << endl:cout << "No" << endl; } return 0; }