括弧匹配检验

2018-01-28 21:05:56


括弧匹配检验

【题目描述】

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

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

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

【输入】

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

【输出】

匹配就输出 “OK” ,不匹配就输出“Wrong”。

【输入样例】

[(])

【输出样例】

Wrong

题目分析:利用栈的性质,如果匹配完了就说明栈空,没匹配完就说明匹配不成功,每次与右括号匹配的时候去栈顶的左括号,因为此时的左括号与右括号最近

#include<cmath>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<set>
#include<stack>
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=1005;
char a[MAXN];
stack<int>s;
#define Ill {puts("Wrong");return 0;}
bool same(char a,char b)//判断两个符号是否相同
{
    if(a=='['&&b==']')return 1;
    if(a=='('&&b==')')return 1;
    return 0;
}
int main()
{
    cin>>a;
    int n=strlen(a);
    for(int i=0;i<n;++i)
    {
        if(a[i]=='('||a[i]=='[')s.push(i);
        else if(a[i]==')'||a[i]==']')
        {
            if(s.empty())//如果有右括号但是没有左括号压入栈
            Ill;
            if(!same(a[s.top()],a[i]))
            Ill;
            s.pop();//如果上面两种都不满足就弹出来 
        }
    }
    if(!s.empty())Ill //如果最后栈不是空的
    puts("OK");
    return 0; 
}