括号匹配

正文索引 [隐藏]

题目描述：

给定一串字符，不超过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;
}
C++
Copy