括号比對算法

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、結果截圖