algospot 괄호2(Mismatched Brackets)

문제링크

문제

Best White is a mathematics graduate student at T1 University. Recently, he finished writing a paper and he decided to polish it. As he started to read it from the beginning, he realized that some of the formulas have problems: some of the brackets are mismatched! Since there are so many formulas in his paper, he decided to check their validity with a computer program.

The following kinds of brackets are included in Best White’s paper.

• Round brackets are opened by a ( and closed by a ).
• Curly brackets are opened by a { and closed by a }.
• Square brackets are opened by a [ and closed by a ].

A formula is said well-matched when the following conditions are met:

1. Every bracket has a corresponding pair. ( corresponds to ), [ corresponds to ], et cetera.
2. Every bracket pair is opened first, and closed later.
3. No two pairs "*cross*" each other. For example, [(]) is not well-matched.

Write a program to help Best White by checking if each of his formulas is well-matched. To make the problem easier, everything other than brackets are removed from the formulas.

입력

The first line of the input will contain the number of test cases C (1≤C≤100). Each test is given in a single line as a character string. The strings will only include characters in "[](){}" (quotes for clarity). The length of the string will not exceed 10,000.

출력

For each test case, print a single line "YES" when the formula is well-matched; print "NO" otherwise. (quotes for clarity)

()()
({[}])
({}[(){}])

open-close괄호 미스매치를 확인하는 문제이다.

Stack을 이용한 문제이고 

{[(와 같은 여는 괄호일 경우 스택에 저장한다

}])와 같이 닫는 괄호가 나올 경우 괄호에 맞는 여는괄호가 나오는지 확인하면 된다.

 

package com.ktko.Success;
import java.util.Scanner;
import java.util.Stack;

public class MismatchedBrackets {
    static int testCase;
    static String test;
    static int result[];
    static Stack stack;

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        stack = new Stack<Object>();

        Scanner scan = new Scanner(System.in);
        testCase = Integer.parseInt(scan.nextLine()); // 테스트 케이스
        result = new int[testCase];

        for (int i = 0; i < testCase; i++) {
            test = scan.nextLine().trim();
            result[i] = calMismatched(test);
        }

        for (int i = 0; i < testCase; i++) {
            if (result[i] != 0)
                System.out.println("NO");
            else
                System.out.println("YES");
        }

    }

    public static int calMismatched(String test) {
        stack.clear();
        
        if (test.length() % 2 != 0)
            return -1;
        String openString = "({[";

        char[] charArray = test.toCharArray();

        for (int i = 0; i < charArray.length; i++) {
            if (openString.indexOf(charArray[i]) > -1) {
                stack.push(charArray[i]);
                
            } else {
                if (stack.empty()) {
                    return -1;
                }

                if (charArray[i] == '}') {
                    if((char)stack.pop() == '{')
                        continue;
                    else
                        return -1;
                }
                if (charArray[i] == ']') {
                    if((char)stack.pop() == '[')
                        continue;
                    else
                        return -1;
                }
                if (charArray[i] == ')') {
                    if((char)stack.pop() == '(')
                        continue;
                    else
                        return -1;
                }

            }
        }
        
        if(!stack.isEmpty())
            return -1;
        
        
        return 0;
    }

}