当前位置:首页 > C++知识 > 正文内容

【数据结构】栈—括号匹配检验

亿万年的星光5年前 (2021-02-21)C++知识20859

【题目描述】

假设表达式中允许包含两种括号:圆括号和方括号,其嵌套的顺序随意,如([ ]())或[  (  [  ] [  ] ) ] 等为正确的匹配,[  (  ]  )或 ([ ] ( )

或 (  ( ) ) )均为错误的匹配。

现在的问题是,要求检验一个给定的表示式中的括号是否正确匹配?

输入一个只包含圆括号和方括号的字符串,判断字符串中的括号是否匹配,匹配就输出“OK”,不匹配就 输出“wrong”。输入一个字符串:

[  ( [ ] [  ] ) ], 输出OK。

【输入描述】

输入仅一行字符(字符个数小于255)

【输出描述】

匹配就输出“OK”,不匹配就输出“wrong”

【样例输入】

[ ( ] )

【样例输出】

wrong

【题目分析与思路】

  1. 从样例中可以看出,匹配规则是从最内部(实际操作可以看成是栈顶)开始匹配。

  2. 按类型匹配,“[” 一定匹配“]”,可以考虑压栈的时候针对于不同的符号进行压栈操作。

  3. 可以用1,2,3,4来分别代表上面的符号




#include<iostream>
#include<stack>
#include<cstring> 
using namespace std;
char str[1000];
stack<int> S;
int main() {
	cin>>str;
    int len=strlen(str);
    for(int i=0;i<len;i++)
    {
        if(str[i]=='(')//记录左圆括号
            S.push(1);
        else if(str[i]==')')//记录右圆括号
        {
            if(S.empty())//栈为空
                S.push(2);
            else if(S.top()==1)
                S.pop();
            else
                S.push(2);
        }
        else if(str[i]=='[')//记录左方括号
            S.push(3);
        else if(str[i]==']')//记录右方括号
        {
            if(S.empty())//栈为空
                S.push(4);
            else if(S.top()==3)
                S.pop();
            else
                S.push(4);
        }
    }
    if(S.empty())
        printf("OK");
    else
        printf("Wrong");
    return 0;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

2021CSP-J/S全国晋级二轮分数线公布

普及组CSP-J序号省市CSP-J人数CSP-J晋级晋级比例最高分晋级最低分1甘肃13413399.25%86152宁夏10310198.06%65243天津46345197.41%8615.54云南...

如何估算时间复杂度

首先:  常见的算法时间复杂度由小到大依次为:Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n^2)<Ο(n^3)<…<Ο(2^n)<Ο(n!)时间复杂度可以简单理解为最多执...

如何计算一个程序的运行时间(防止超时)

再一些OJ系统中,做题的时候常常会超时,但是很多人不知道自己的程序是否会超时,不知道如何检查自己的程序。这篇文章主要介绍几种监测自己程序运行时间的程序。头文件<time.h> ...

指针(三):指针与函数

1.交换的例子#include<iostream> #include<cstdio> #include<cstring> using namespa...

【数据结构】并查集1

【数据结构】并查集1

1.引入    对于一个集合S={a1, a2, …, an-1, an},我们还可以对集合S进一步划分: S1,S2,…,Sm-1,Sm,我们希望能够快速确定...

【算法】分治算法

前言所谓分治算法就是指分而治之,即将较大规模的问题分解成几个较小规模的问题,通过对较小问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称为二分法。比如,我们玩过最简单的猜...