括号匹配

正文索引 [隐藏]

题目描述:

给定一串字符,不超过100个字符,可能包括括号、数字、字母、标点符号、空格,编程检查这一串字符中的( ) ,[ ],{ }是否匹配。

输入描述:

输入在一行中给出一行字符串,不超过100个字符,可能包括括号、数字、字母、标点符号、空格。

输出描述:

如果括号配对,输出yes,否则输出no。

输入样例1:

sin(10+20)

输出样例1:

yes

输入样例2:

{[}]

输出样例2:

no

解题思路:

用栈来求解,若是左括号直接推入栈中,若是右括号则判断栈是否为空、判断栈顶元素是不是与该右括号匹配,若不匹配则return false,若匹配则取出栈顶元素。当字符串被遍历完后,若栈为空return true,否则return false。

AC代码:

#include <bits/stdc++.h>
using namespace std;

bool matched(string str)
{
    stack<char> s;
    for(auto it : str)
    {
        switch(it)
        {
            case '(': case '[': case '{': s.push(it); break;
            case ')':
                if(s.empty() || s.top()!='(')
                {
                    return false;
                }
                else s.pop();    //一定要else,不然会被卡22分
                break;
            case ']':
                if(s.empty() || s.top()!=']')
                {
                    return false;
                }
                else s.pop();
                break;
            case '}':
                if(s.empty() || s.top()!='(')
                {
                    return false;
                }
                else s.pop();
                break;
            default: break;
        }
    }
    return s.empty();
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    string s;
    getline(cin,s);
    printf("%s\n",matched(s)?"yes":"no");
    return 0;
}