문제

👉 20. Valid Parentheses
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

풀이방법

• "(, { , [" 이 나오면 스택에 저장한다.
• 스택이 비어있다면 false를 리턴한다.
  ex) input이 "]" 이 나온다면 괄호가 완성될 수 없다.
• "), }, ]"가 나온다면 스택에서 제일 위에 위치한 문자와 비교하여 괄호가 완성되면 스택에서 pop한다.

코드

class Solution {
public:
    bool isValid(string s) {
        stack<char> list;
        bool result = false;
        for (int i = 0; i < s.size(); i++) {
            char c = s[i];
            if (c == '(' || c == '{' || c == '[') {
                list.push(c);
            }
            if (list.empty()) {
                return false;
            }else if (c == ')' || c == '}' || c == ']') {
                char peek = list.top();
                cout << c <<", " << peek << endl;
                if (c == ')' && peek == '(') {
                    list.pop();
                } else if (c == '}' && peek == '{') {
                    list.pop();
                } else if (c == ']' && peek == '[') {
                    list.pop();
                } else {
                    return false;
                }
            }

        }
        return list.empty();
    }
};