[PTA] [数据结构] [顺序栈] R7-2 括号匹配 [c++实现] [思路分享]

目录

一. 题目复现

二. 思路解释

三. 代码实现

检查一段C语言代码的小括号( )、 中括号 [ ] 和大括号{ } 是否匹配

输入格式:

在一行中输入一段C语言代码，长度不超过1000个字符（行末以换行符结束）。

输出格式:

第一行输出左括号的数量和右括号的数量，中间以一个空格间隔。
若括号是匹配的，在第二行打印YES，否则打印NO。

二.   思路解释

        本题目的为在字符串里实现'['与']' , '('与')' , '{'与'}' 的字符匹配,难点也是这个。

        思路过程:

        栈有先进后出的特点，本题所设置的一个栈仅对'['与']' , '('与')' , '{'与'}' 的字符进行存、取与查看栈顶操作。如下图为实现过程：
        如图，我们假设此时栈顶元素是'['，此时有两种情况:

        (1)如果下一个即将入栈的字符c(注意c还没有入栈)是']'，则和栈顶的'['匹配，那么可以将栈顶元素'['出栈，当然了字符c既然和栈顶匹配了也不用入栈啦。

        (2)如果一个即将入栈的字符c不与此时的栈顶'['匹配，即不是']'，则将c入栈，等待下一次匹配。
        这样的结果是什么: 每一次匹配成功就有一个符号出栈，当所以字符串都有匹配成功，栈空就是自然而然的事——YES；若最后不是空栈，则说明匹配没有成功——NO。

 三. 代码实现

c++：

#include
#include
using namespace std;

//栈结构体，以SqStack命名
typedef struct {
    char *base;
    char *top;
    int stacksize;
}SqStack;

bool matchChar(char c,char c0);//匹配c和c0是否匹配，如c='[',c0=']'匹配，
                                //注意c='[',若c0='}' 或')' 时就不匹配了
void iniStack(SqStack&S,int size);//初始化栈
void popStack(SqStack&S);//出栈
void pushStack(SqStack&S,char celem);//celem入栈
char getStackTop(SqStack&S);//查看栈顶元素，栈内部结构和元素不改变


int main()
{
    string cstr;
    int stacksize;//本次匹配所需栈的空间，就是输入字符串的长度
    int l=0;//记录左括号
    int r=0;//记录右括号
    SqStack stk;
    
    getline(cin,cstr);//输入字符串
    stacksize=cstr.length();//本次匹配所需栈的空间，就是输入字符串的长度
    iniStack(stk,stacksize);//初始化栈
    
    for(int i=0;i