괄호 매칭 문제

gistfile1.txt

#1. Given the string of parentheses only, write the function to check if they are balanced.
((())) is balanced,
(() is not.
)( not balanced

bool isBalanced(char input[]) {
   Stack stack;
   
   int len = strlen(input);
   
   for(int i=0; i<len ; i++) {       
       if(input[i] == '(') stack.push(input[i]);
       else if( !(stack.isEmpty()) && input[i] == ')') stack.pop();
       else return false;
   }
   
   if(stack.isEmpty()) return true;
   else return false;
}
#2. with { ( [, modify the #1 solution.

(){[]()} , ({[]}) balanced
([)] not balanced

bool isOpen(char c); //{ [ (
bool isClose(char c); //} ] )
bool isMatch(char c1, char c2); // (,) , {,} , [,] --> true

bool isBalanced2(char input[]) {
   Stack stack;
   
   int len = strlen(input);
   
   for(int i=0; i<len ; i++) {       
       if( isOpen(input[i]) ) stack.push(input[i]);
       else if( !(stack.isEmpty()) && isClose(input[i])) {
           if( !isMatch(stack.back(), input[i]) ) return false;
           stack.pop();
       }
       else return false;
   }
   
   if(stack.isEmpty()) return true;
   else return false;
}


광성님이 제시하신 map을 이용한 확장성 있는 괄호쌍 매칭 함수.
map<char, char> paren = {{'{','}'}, {'[', ']'}, {'(', ')'}};

bool isOpen(char c) {
    return paren.find(c) != paren.end();
}

bool isBalanced(string s) {
    stack<char> st;

    for (const auto& c : s) {
        if (isOpen(c))
            st.push(c);
        else {
            if (st.empty() || paren[st.top()] != c)
                return false;
            st.pop();
        }
    }

    return st.empty();
}