[20]9012号かっこ

9012かっこ

質問する

括弧文字列(Parentosis String,PS)は、2つの括弧記号「(」と「)」からなる文字列である.ここで、括弧形状が正しい文字列を正しい括弧文字列(Valid PS,VPS)と呼ぶ.括弧の「()」文字列をデフォルトVPSと呼びます.xがVPSであれば、括弧に入れる新しい文字列「(x)」もVPSとなります.また,2つのVPSxとyを接続した新しい文字列xyもVPSとなる.例えば、「()()()」「((())」はVPSであるが、「()(」()、「()()())」と「(((()」はVPSではなく文字列である.
入力した括弧文字列がVPSであるかどうかを判断し、結果をYESとNOとして表す必要があります.

入力

入力データは標準入力を採用している.T個のテストデータとして入力します.入力された最初の行は、入力データの数を表す整数Tを与える.各テストデータの最初の行にはカッコ文字列があります.カッコ文字列の長さは2または50以下です.

しゅつりょく

出力は標準出力を採用する.カッコ文字列が正しいカッコ文字列(VPS)である場合は、「YES」または「NO」を行単位で出力します.

コピー例入力1

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

コピー例出力1

NO
NO
YES
NO
YES
NO

コピー例入力2

3
((
))
())(()

コピーサンプル出力2

NO
NO
NO

コード#コード#

//---- 세팅 ----//
const fs = require('fs');
const stdin = (
  process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString()
    : `\
6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(
`
).split('\n');

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

//---- 풀이 -----//

const t = Number(input());
const parenthesisArr = [];

[...Array(t)].forEach(() => {
  parenthesisArr.push(input());
});

const isVPS = str => {
  const stack = [];
  let res = true;
  str.split('').forEach(v => {
    if (v === '(') stack.push('(');
    else if (v === ')') {
      const popped = stack.pop();
      if (popped !== '(' || popped === undefined) {
        res = false;
        return;
      }
    }
  });
  if (stack.length > 0) return false;
  return res;
};

const res = parenthesisArr.map(v => (isVPS(v) ? 'YES' : 'NO'));

console.log(res.join('\n'));

に答える

(ならスタックに入れます.)の場合、スタック内の最後の要素がポップアップされます.

スタックが空またはpopの要素が)である場合、VPSではない.

popの要素が(である場合、それは正しい形式であり、継続する.