题目 P1037 括号匹配检验

作者是一名蒟蒻，请多多点赞指教！

温馨提醒

本题将用到数据结构：栈； 不要以为数据结构很难，其实超级简单，它没有算法，没有让人cpu烧的东西，它就是一种类似数组的容器，所以你怎么学数组就怎么学栈，怎么学数据结构！

题目解析

这题的意思是给我们一段以："[" ,"]","(",")"这四个符号组成的字符串，让我们判断能否组成多对"()"或"[]"。

知识了解

要想解决这道题，我们要先了解一个数据结构：栈。 我在这里简单概括一下，栈就是一种类似弹夹的储存数据（包括数字，字符，字符串，bool等）的容器，先进去的数据会向先压进去的子弹一样，在最底下，后进的数据一个个压在上面。想要取出数据也要从上面取出。所以栈有着后进先出的特点； 举个栗子：我们先后向栈内存入1，2，3，4，5；那么想要取出所有数据，那么取出顺序为5，4，3，2，1； 实在不懂，没关系，现在想象你在minecraft（我的世界）中搭了一个中空的管道，你现在有不同颜色的混凝土粉末，你站在管道顶端,往管道里放，带有重力的混凝土粉末会下落到管道底端，你依次放入红，橙，黄，绿，青，蓝，紫，在不破坏管道的情况下你只能从上往下撸掉混泥土，那你会依次得到紫，蓝，青，绿，黄，橙，红，紫色混泥土是最后一个放至的，却是第一个撸掉的现在你可以明白栈的后进先出了吧。 更多知识请点进链接查看；

点明思路

这题可以用栈来解决，我们输入一个字符串，然后将字符串中的字符一个一个压入栈，每次压入字符，就判断一次栈最顶上的元素与第二个元素是否可以组成一对，若可以，将第一第二个删除；所有字符都压入后，若栈为空则说明都可以组成对。

就比如输入"[()]",第一次压入"[",第二次压入"(",此时栈内"["在最底下，"("在最顶上,"["与"("不能组成一对。第三次压入")",此时")"在最顶上，"("是第二个，"("与")"可以组成一对，删除第一第二个，现在"["在顶上，第四次压入"]",此时"]"在最顶上，"["是第二个，"["和"]"组成一对，删除第一第二个，发现都压完了，且栈为空，所以都可以组队；

编写代码

有了思路，代码就很简单了；我们可以用数组来模拟栈，用一个变量来标记栈顶

string a;//输入的内容
char s[10005];//用数组s模拟栈
int top = 0;//存储栈顶

输入了内容之后我们要遍历字符串,得到所有字符（字符串中的每个字符也是有下标的，也可以像数组一样查询，如s = asdf,s[1] = s;

cin >> a;//输入
int b = a.length();//获取字符串长度
for(int i = 0;i < b;i++)//遍历字符
｛
  
 ｝

字符遍历切记要从0开始循环，应为字符串第一位下标为0;

现在每一次遍历，我们要将一个字符压入栈，并将top+1，然后判断栈顶与次栈顶是否可以组成一对；然后删除第一第二元素；

for(int i = 0;i < b;i++)
   {
        top++;//栈顶增加1
        s[top] = a[i];//将第i个元素压入栈
        if(s[top-1] == '[')//判断是否组成一对
        {
            if(s[top] == ']')
            {
                top-=2;//删除栈第一第二元素；
            }
        }
        if(s[top-1] == '(')
        {
            if(s[top] == ')')
            {
                top-=2;//删除栈第一第二元素；
            }
        }
    }

最后，判断栈是否为空，可以通过判断栈顶坐标，即top是否为0；

if(top == 0)//判断栈是否为空
{
    cout << "OK";//输出
}
else//否
{
    cout << "Wrong";//输出
}

代码全线讲解到此结束🎉️

参考代码

我是到各位很急，这不来了嘛 请勿一口吞噬，会被噎死封号的哦！

#include <iostream>//别看了，老土了
using namespace std;
string a;
char s[10005];//定义栈
int top;
int main()
{
    cin >> a;//输入
    int b = a.length();
    for(int i = 0;i < b;i++)//遍历
    {
        top++;
        s[top] = a[i];
        if(s[top-1] == '[')
        {
            if(s[top] == ']')
            {
                top-=2;
            }
        }
        if(s[top-1] == '(')
        {
            if(s[top] == ')')
            {
                top-=2;
            }
        }
    }
    if(top == 0)
    {
        cout << "OK";
    }
    else
    {
        cout << "Wrong";
    }
    return 0;
}

相信你一定听懂了吧，别忘了点个赞哦

#include <bits/stdc++.h>
using namespace std;
stack<char> sta;
string a;
string oper;
int main(){
    cin>>a;
    for (int i=0;i<a.length();i++){
        if (sta.empty())sta.push(a[i]);
        else{
            if (a[i]==']' and sta.top()=='[')sta.pop();
            else if (a[i]==')' and sta.top()=='(')sta.pop();
            else sta.push(a[i]);
        }
    }
    if (sta.empty())cout<<"OK";
    else cout<<"Wrong";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
stack<char> a;
int main()
{
	string s;
	cin >> s;
	for (int i = 0;i < (int)s.length();i++)//如果不强制转换会有提示，但不耽误AC
	{
		if (a.empty())
		{
			a.push(s[i]);
		}/*这一段至关重要，没有的话会第五个测试点过不去。
				段错误
				Segmentation fault（段错误）
				是一种常见的程序错误，
				通常在C或C++等编程语言中出现。
				 它表示程序试图访问不允许的内存位置，
				 或者试图操作未分配给程序的内存区域。
				  当程序访问了未分配的内存、
				  已释放的内存、
				  越界访问数组或字符串等场景时，
				  可能会导致段错误。（本解释来自浏览器）*/ 
		else if (s[i] == '(' || s[i] == '[')
		{
			a.push(s[i]);
		}
		else if (s[i] == ')' && a.top() == '(')
		{
			a.pop();
		}
		else if (s[i] == ']' && a.top() == '[')
		{
			a.pop();
		}
	}
	if (a.empty())//检验是否全部配对 
	{
		cout << "OK";
	}
	else
	{
		cout << "Wrong";
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
string t;//t字符串存储括号
stack<char>s;//栈，char类型
string::iterator it;//这个是迭代器的定义，知道STL的都知道
/*
STL小知识->迭代器
迭代器有3种--随机迭代器，双向迭代器，没有迭代器
随机迭代器：迭代器可以比大小，还能使用下标
双向迭代器：不能比大小,只能用迭代器
没有迭代器：迭代器都不能用
迭代器定义：STL<type>::iterator it;
反向迭代器定义：STL<type>::reverse_iterator it;
STL迭代器:begin(),end();
STL反向迭代器:rbegin(),rend()
-------------------------------------
STL容器&&迭代器
vector(动态数组)随机迭代器
deque(双向队列)随机迭代器
string(字符串)随机迭代器
list(链表)双向迭代器
set(集合)双向迭代器
map(映射)双向迭代器
pair(可以看成结构体)双向迭代器
stack(栈)没有迭代器
queue(队列)没有迭代器
priority_queue(优先队列)没有迭代器
--------------------------------------
迭代器遍历
正向：for(it=s.begin();it!=s.rend();it++)cout<<*it<<" "；
反向：for(it=s.rbegin();it!=s.end();it++)cout<<*it<<" "；
----------------------------------------
附赠迭代器遍历
for(const auto b:s)
*/
int main(){
    cin>>t;//输入字符串
    s.push('#');//为了保证栈不为空
    for (it=t.begin();it<t.end();it++){//迭代器正向遍历
        if (*it=='('||*it=='[')s.push(*it);//如果是左括号，括号入栈
        else{//是右括号
             //判断是否有匹配左括号，有弹出栈顶括号，没有，输出no
             if (*it==')'&&s.top()=='('||*it==']'&&s.top()=='[')s.pop();
             else {
                 cout<<"Wrong";
                 return 0;
             }
         }
    }
    if(s.size()==1)cout<<"OK";//输出
    else cout<<"Wrong";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
stack<char> stk;
char ch;
int main()
{
    while ( scanf( "%s", &ch ) )
    {
        if ( ch == '(' || ch == '[' )
            stk.push( ch );
        if ( ch == ')' )
        {
            if ( stk.top() == '(' ) stk.pop();
            else
            {
                cout << "Wrong" << endl;
                system("pause");
                return 0;
            }
        }
        else if ( ch == ']' )
        {
            if ( stk.top() == '[' ) stk.pop();
            else
            {
                cout << "Wrong" << endl;
                system("pause");
                return 0;
            }
        }
    }
    cout << "OK" << endl;
    system("pause");
    return 0;
}

请问一下这道题的输入如果用 while( cin >> x ) 应该怎么结束输入呢？ 答案为Wrong的时候是可以的，OK的时候结束不了