[LeetCode] Valid Parentheses

프로그래머스에서 풀었었던 괄호문제!

 

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

 

Example 1:

Input: s = "()"

Output: true

Example 2:

Input: s = "()[]{}"

Output: true

Example 3:

Input: s = "(]"

Output: false

Example 4:

Input: s = "([])"

Output: true

 

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

stack을 사용하여 문제를 푼다.

자세한건 주석으로~

 

#define MAX_SIZE 10000 

bool isValid(char* s) {
    char stack[MAX_SIZE + 1];
    int top = -1; // stack의 최상단 인덱스

    int length = strlen(s);

    for(int i = 0; i < length; i++){
        // 여는 괄호는 stack에 추가
        if(s[i] == '(' || s[i] == '[' || s[i] == '{')
        {
            stack[++top] = s[i];
        }
        // 닫는 괄호 처리
        else if(s[i] == ')' || s[i] == ']' || s[i] == '}')
        {
            if(top == -1)
            {
                // 닫는괄호일때 스택이 비어있으면 짝이 맞지 않으므로 false
                return false;
            }

            char lastChar = stack[top--];

            if((s[i] == ')' && lastChar != '(') ||
               (s[i] == ']' && lastChar != '[') ||
               (s[i] == '}' && lastChar != '{')) {
                    return false;
                }
        }
    }


return (top == -1);

}