UVA 673 Paretheses Balance

原题Vjudge

题目大意

怼给你一堆括号，判断是否合法

有三条规则

（1）空串合法

（2）如果\(A和B\)都合法，则\(AB\)合法（例如：\(()和[]\)都合法，则\(()[]\)合法）

（3）如果\(A\)合法，则\((A)和[A]\)都合法（例如\(A = ([])\),则\((([]))和[([])]\)都是合法的）

解题思路

可以成对的括号是贴在一起的（在上述规则的定义下）

通过栈的“后入先出”性质我们可以想到

遇到左括号就入栈，遇到右括号就判断是否与栈顶的左括号匹配，若匹配则出栈，不匹配则说明括号序列不合法，输出\(No\)即可

到最后别忘记检测括号是否全部匹配（即是否栈空）

坑点

注意规则（1）空串合法，所以可能毒瘤UVA会给个空行，所以用\(getline\)进行读入

注意&&是短路运算符，在元素出栈前应该判断是否栈空，设是否栈空为条件\(p\)，括号与栈顶是否匹配为条件\(q\)，则我们的\(if\)语句应该是\(p\wedge q\),此时当\(p\)不成立，即栈空时，会直接短路掉，而不会取到栈顶引发段错误.(不过手写栈可以设置空栈条件是top = 0，这样就不用考虑短路)

代码实现

#include <iostream>

using namespace std;

const int N = 1e7 + 86;

int top;

char mp[358], s[N];

int main()

{

    int T;

    scanf("%d", &T);

    getchar();

    mp['('] = ')', mp['['] = ']';

    while (T -- )

    {

        string val;

        getline(cin, val);

        if (!val.size()) { puts("Yes"); continue ; }

        bool err = 0;

        for (auto c : val)

        {

            if (err) break ;

            if (c == '(' || c == '[') s[ ++ top] = c;

            else if (top && c == mp[s[top]]) -- top;

            else err = 1;

        }

        if (top) err = 1, top = 0;

        puts(err ? "No" : "Yes");

    }

    return 0;

}

Accepted!

UVA 673 Paretheses Balance的相关教程结束。