括號匹配算法

1、基于棧的應用

  括號匹配算法是棧的一個典型應用；所以的借用棧來實現，保存相應的信息；

  算法思想：遇到第一個字符， 判斷棧空，字符入棧，其后的字符和棧頂元素進行比較，括號匹配的話，則棧頂元素出棧，否則，當前元素入棧，直到遇到0結束標志；最后根據棧空判斷，空：括號匹配，否則，不匹配；

  例：([{}])是匹配的括號，為正確的；

2、代碼實現

#include<iostream>
#include<stack>
using namespace std;

typedef unsigned char boolean;
#define    TRUE    1
#define FALSE    0

boolean backetMatch(char *str);
boolean backetMatch(char *str){
    stack<int> s;
    int i = 0;
    
    while(str[i]){
        if(s.empty()){
            s.push(str[i]);
        }else{
            if(s.top() == ')' || s.top() == ']' || s.top() == '}'){
                return FALSE;  //首先出現右括號的，肯定是不匹配的；
            }

            if(s.top() == '('){ //為'('的情況
                if(str[i] == ')'){
                    s.pop();
                }else{
                    s.push(str[i]);
                }
            }else if(s.top() == '['){ //為'['的情況
                if(str[i] == ']'){
                    s.pop();
                }else{
                    s.push(str[i]);
                }
            }else if(s.top() == '{'){ //為'{'的情況
                if(str[i] == '}'){
                    s.pop();
                }else{
                    s.push(str[i]);
                }
            }
        }
            i++;
    }

    if(s.empty()){
        return TRUE;
    }else{
        return FALSE;
    }
}

int main(void){
    char *str = "({[])}";
    boolean flag;

    flag = backetMatch(str);
    if(flag){
        printf("括號匹配\n");
    }else{
        printf("括號不匹配\n");
    }
    
    return 0;
}

3、結果截圖