算法括号的匹配

- 日理万妓 2022-05-27 04:52 195阅读 0赞

括号的匹配用到了栈的初始化，压栈，弹栈，栈顶元素的获取，和栈是否为空，这里就不写了，我们也可以使用stl中的stack来定义一个栈，，，

算法步骤：

1.初始化一个空栈

2.定义一个flag标记，用以判断括号是否匹配，初始化的时侯将flag标记设为1，当括号不匹配时，flag变为0

3.用循环语句，首先遇到'('，'\['，'\{'时，将字符压入栈中，若遇到')'，'\]'，'\}'时，栈顶没有与之匹配的左括号，就将flag变为0，若有与之匹配的左括号，就弹栈

4.最后用判断语句，若栈为空且flag标记依然为1，返回true，否则返回false

程序：

#include <iostream>
    #include <stack>
    #include <cstdio>
    using namespace std;
    
    //将左括号压入栈中
    void Left(char ch, stack <char> &s)
    {
        switch(ch)
        {
            case '(':
            case '[':
            case '{': s.push(ch);
                      break;
            default: break;
        }
    }
    //右括号匹配成功弹出栈顶元素
    void Right(char ch, stack <char> &s, int &flag)
    {
        switch(ch)
        {
            case ')': if(s.top() == '(')
                          s.pop();
                      else
                        flag = 0;
                      break;
            case ']': if(s.top() == '[')
                          s.pop();
                      else
                        flag = 0;
                      break;
            case '}': if(s.top() == '{')
                          s.pop();
                      else
                        flag = 0;
                      break;
            default : break;
        }
    }
    //匹配
    int match(char *a)
    {
        int flag = 1;
        stack <char> s; //初始化一个空栈
        while(*a)
        {
            Left(*a, s);
            Right(*a, s, flag);
            a++;
        }
        if(s.empty() && flag)
            return 1;
        else
            return 0;
    }
    int main()
    {
        char a[100];
        gets(a);   //读入表达式
        if(match(a))    //判断表达式是否匹配
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
        return 0;
    }