[데이터 구조] 스 택 의 응용 - 괄호 가 일치 하 는 지 확인 합 니 다.

5655 단어 데이터 구조
1. 괄호 일치 검사
가설 표현 식 에는 세 가지 괄호 가 포함 되 어 있 습 니 다. 괄호, 네모 난 괄호, 큰 괄호 등 이 포함 되 어 있 습 니 다. 즉, {() []} 또는 {()} 등 이 올 바른 형식 으로 일치 하 는 것 입 니 다. 즉, 일치 하 는 것 입 니 다. [(]) 또는 ()} 등 은 올 바 르 지 않 은 형식 으로 일치 하지 않 습 니 다. 괄호 가 일치 하 는 지 확인 하 는 방법 은 '기대 하 는 긴박 도' 라 는 개념 으로 설명 할 수 있 습 니 다.
괄호 매 칭 은 다음 과 같은 몇 가지 상황 으로 나 뉜 다.
char a[] = "(())abc{[(])}" ; //            
char b[] = "(()))abc{[]}" ; //          
char c[] = "(()()abc{[]}" ; //          
char d[] = "(())abc{[]()}" ; //         

2. 코드 구현
코드 는 다음 과 같 습 니 다:
#include 
#include 
using namespace std;

bool MatchBrackets(char str[], size_t size)
{
    stack<char> s;
    for (size_t i = 0; i < size; ++i)
    {
        if (str[i] != '(' && str[i] != ')' &&
            str[i] != '[' && str[i] != ']' &&
            str[i] != '{' && str[i] != '}')
        {
            continue;
        }
        else
        { 
            if ('(' == str[i] || '{' == str[i] || '[' == str[i])
            {
                s.push(str[i]);
            }
            else
            {
                if (s.empty())
                {
                    cout << "        " << endl;
                    return false;
                }
                char c = s.top();
                if (('(' == c && ')' == str[i]) ||
                    ('{' == c && '}' == str[i]) ||
                    ('[' == c && ']' == str[i]))
                {
                    s.pop();
                }
                else
                {
                    cout << "       " << endl;
                    return false;
                }
            }
        }
    }
    if (!s.empty())
    {           
        cout << "        " << endl;
        return false;
    }
    cout << "    " << endl;
    return true;
}

int main()
{
    char a[] = "(())abc{[(])}";  //            
    char b[] = "(()))abc{[]}";   //         
    char c[] = "(()()abc{[]}";   //         
    char d[] = "(())abc{[]()}";  //         

    cout << MatchBrackets(a, strlen(a)) << endl;
    cout << MatchBrackets(b, strlen(b)) << endl;
    cout << MatchBrackets(c, strlen(c)) << endl;
    cout << MatchBrackets(d, strlen(d)) << endl;
    return 0;
}

좋은 웹페이지 즐겨찾기