20.Valid Parentheses 栈的应用：括号匹配

àì夳堔傛蜴生んèń 2022-06-08 11:20 154阅读 0赞

十分简单的括号匹配，用栈来操作就可以了

\#define max\_size 1000001

class Solution \{  
public:  
    typedef struct SqStack\{  
            int top;  
            char data\[max\_size\];  
        \}Stack;  
    void Init\_Stack(Stack &s)  
        \{  
            s.top = -1;  
        \}  
          
        int PopStack(Stack &s,char &c)  
        \{  
            if(s.top==-1)  
                return 0;  
            c = s.data\[s.top--\];  
            return 1;  
        \}  
          
        int PushStack(Stack &s,char c)  
        \{  
            if(s.top==max\_size)  
                return 0;  
            s.data\[++s.top\] = c;  
            return 1;  
        \}  
      
    bool isValid(string s) \{  
          
    Stack st;  
    Init\_Stack(st);  
    int i=0;  
    char c;  
    while(s\[i\]!='\\0')  
    \{  
        if(s\[i\]=='('|| s\[i\] =='\{' ||s\[i\]=='\[')  
            PushStack(st,s\[i\]);  
        else\{  
        if(s\[i\]==')')  
        \{  
            PopStack(st,c);  
            if(c!='(')  
                return false;  
        \}  
        if(s\[i\]=='\]')  
        \{  
            PopStack(st,c);  
            if(c!='\[')  
                return false;  
        \}  
        if(s\[i\]=='\}')  
        \{  
            PopStack(st,c);  
            if(c!='\{')  
                return false;  
        \}  
        \}  
        i++;  
    \}  
    if(st.top==-1)  
        return true;  
    return false;     
    \}  
\};