취미 알고리즘 - 괄호 일치

취미 알고리즘 - 괄호 일치:
스 택 으로 괄호 정 보 를 저장 하고 왼쪽 괄호 를 만 나 스 택 에 들 어가 면 오른쪽 을 만 나 스 택 꼭대기 의 괄호 와 일치 하여 스 택 에서 문자열 을 계속 검색 합 니 다.

#include <stdio.h>
#include <stdlib.h>


// using stack to save and judge the string
// return the index where the bracket not match
// return 0 no problem
int IsMatch(char* strTest, int nLen)
{
    char* pStack = NULL;
    char* pChr = strTest;
    int   i = 0;
    int   nStackIdx = 0;


    if ((pChr == NULL) || (nLen == 0))
    {
        return -1;
    }
    pStack = (char*) malloc(sizeof(char)*nLen);


    if (pStack == NULL)
    {
        return -1;
    }


    while (i < nLen)
    {
        switch(*pChr)
        {
        case '{':
        case '[':
        case '(':
        case '<':
            pStack[nStackIdx] = *pChr;
            nStackIdx++;
            break;


        case '}':
            if ((nStackIdx > 0) && (pStack[nStackIdx-1] == '{'))
            {
                nStackIdx--;
            }
            else
            {
                printf("Miss mathc } at %d
", i+1);
                return i+1;
            }
            break;
        case ']':
            if ((nStackIdx > 0) && (pStack[nStackIdx-1] == '['))
            {
                nStackIdx--;
            }
            else
            {
                printf("Miss mathc ] at %d
", i+1);
                return i+1;
            }
            break;
        case ')':
            if ((nStackIdx > 0) && (pStack[nStackIdx-1] == '('))
            {
                nStackIdx--;
            }
            else
            {
                printf("Miss match ) at %d
", i+1);
                return i;
            }
            break;
        case '>':
            if ((nStackIdx > 0) && (pStack[nStackIdx-1] == '<'))
            {
                nStackIdx--;
            }
            else
            {
                printf("Miss match > at %d
", i+1);
                return i;
            }
            break;
        default:
            break;
        }
        i++;
        pChr++;
    }
    if (nStackIdx == 0)
        printf("The string: %s is ok
", strTest);
    else
        printf("The string is not bracket match: missing %c at %d
", 
               pStack[nStackIdx-1], nStackIdx);


    free(pStack);
    return nStackIdx;
}


int main()
{
    char sTestOk[] = "{<[<<{{{[<<>>[[]]]}}}>>]>}";
    char sTestFail[] = "{";
    char sTestFail1[] = "<<{[(asdfe]]}>>";
    int i = 0;
    IsMatch(sTestOk, strlen(sTestOk));
    IsMatch(sTestFail, strlen(sTestFail));
    IsMatch(sTestFail1, strlen(sTestFail1));
    scanf("%d", &i);
    return 0;
}

알고리즘 복잡 도 분석:
시간 복잡 도: O (n), 한 번 스 캔 하면 문자열 이 일치 하 는 지 확인 할 수 있 습 니 다.