首页 > 试题广场 >

括号的匹配

[编程题]括号的匹配
  • 热度指数：1680 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}在算术表达式中，除了加、减、乘、除等运算外，往往还有括号。在本题中，我们视括号有四种：大括号 \texttt{\{...\}}，中括号 \texttt{[...]}，小括号 \texttt{(...)}，尖括号 \texttt{<...>}。
\hspace{15pt}我们定义合法的括号表达式为：
\hspace{23pt}\bullet\,对于每一对括号，必须先有左边括号，然后才有右边括号。
\hspace{23pt}\bullet\,如果有多个括号，则每种类型的左括号和右括号的个数必须相等。
\hspace{23pt}\bullet\,对于多重括号的情形，按运算规则，从外到内的括号嵌套顺序为：大括号 \rightarrow 中括号 \rightarrow 小括号 \rightarrow 尖括号。例如，\texttt{\{[(<>)]\}}，\texttt{\{()\}}，\texttt{\{\{\}\}} 为一个合法的表达式，而 \texttt{([\{\}])}，\texttt{\{([])\}}，\texttt{[\{<>\}]} 都是非法的。
\hspace{15pt}现在给定一个仅由上述四类括号组成的括号表达式，请你判断它是否为合法的括号表达式。

输入描述:
\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leq T\leq 10^4\right) 代表数据组数，每组测试数据描述如下：

\hspace{15pt}在一行上输入一个长度为 {\rm length}(s)，仅由上述四类括号组成的括号表达式 s \left(1\leq {\rm length}(s) \leq 2\times 10^5\right)。

\hspace{15pt}除此之外，保证单个测试文件的 {\rm length}(s) 之和不超过 2\times 10^5。


输出描述:
\hspace{15pt}对于每一组测试数据，新起一行。如果表达式是合法的，输出 \texttt{YES}；否则输出 \texttt{NO}。
示例1

输入

5
{[(<>)]}
[()]
<>()[]{}
[{}]
{()}

输出

YES
YES
YES
NO
YES

备注:
本题已于下方时间节点更新，请注意题解时效性：
1. 2025-11-13 优化题面文本与格式。原数据存在空白行，重造数据。
算法知识视频讲解
添加回答
马兰花开_头像 马兰花开_
发表于 2026-02-17 22:48:21 回复(0)
精致的熊熊在努力存钱头像 精致的熊熊在努力存钱
dic_left = {'{':4,'[':3,'(':2,'<':1}
dic_right = {'}':4,']':3,')':2,'>':1}
n = int(input())
for i in range(n):
    li = []
    s = input()
    result = True
    for j in s:
        if j in dic_left.keys():
            if not li:
                li.append(j)
            elif dic_left[li[-1]] >= dic_left[j]:
                li.append(j)
            else:
                print('NO')
                result = False
                break
        else:
            if li:
                if dic_right[j] == dic_left[li[-1]]:
                    li.pop()
                else:
                    print('NO')
                    result = False
                    break
            else:
                print('NO')
                result = False
                break
    if result:
        if not li:
            print('YES')
        else:
            print('NO')
发表于 2026-02-06 12:50:50 回复(0)
C++
成熟的火龙果觉得你很赞头像 成熟的火龙果觉得你很赞 

	
	

		#include <iostream>
	


	

		#include<string>
	


	

		#include<vector>
	


	

		using namespace std;
	


	

		void isvaild(const string &s){
	


	

		    int x;
	


	

		    vector<int>st;
	


	

		    for(char c : s){
	


	

		       if(c=='{'||c=='}')x=4;
	


	

		       else if(c=='['||c==']')x=3;
	


	

		       else if(c=='('||c==')')x=2;
	


	

		       else if(c=='<'||c=='>')x=1;
	


	

		       else {
	


	

		        cout<<"NO"<<endl;
	


	

		        return ;
	


	

		       }
	


	

		       if(c=='{'||c=='['||c=='('||c=='<'){
	


	

		        if(!st.empty()&&st.back()<x){
	


	

		            cout<<"NO"<<endl;
	


	

		            return ;
	


	

		        }
	


	

		        st.push_back(x);
	


	

		        //检验是否匹配
	


	

		       }else{
	


	

		        if(!st.empty()&&st.back()!=x){
	


	

		            cout<<"NO"<<endl;
	


	

		            return ;
	


	

		        }
	


	

		        st.pop_back();
	


	

		       }
	


	

		    }
	


	

		    if(st.empty())cout<<"YES"<<endl;
	


	

		    else cout<<"NO"<<endl;
	


	

		}
	


	

		int main(){
	


	

		    int n;
	


	

		    cin>>n;
	


	

		   string v;
	


	

		    for(int i=0;i<n;i++){
	


	

		        cin>>v;
	


	

		        isvaild(v);
	


	

		    }
	


	

		}
发表于 2026-02-01 15:50:42 回复(1)
C++
gotoreturn头像 gotoreturn
#include <iostream>
#include <map>
#include <stack>
using namespace std;

int main() {
    //stack<char> qou ;
    int n ;
    cin >> n ;
    string qs ;
    map<char, char> ql {
        {'}','{'},{')','('},{']','['},{'>','<'}
    } ;
    map<char, int> qi {
        {'{',4},{'(',2},{'[',3},{'<',1}        
    };
    while (n--) {
        cin >> qs ;
        stack<char> qou ;
        bool valid = true ;
        for (char q : qs) {
            if (q == '[' || q=='(' || q=='<' || q=='{') {
                if (qou.empty() || qi[q]<=qi[qou.top()]) {qou.push(q) ;}
                else { valid = false ;break ;}
            }
            else {
                if (qou.empty()|| qou.top()!=ql[q]) { valid = false ;break ;}
                qou.pop() ;
            }
        }
        if (valid && qou.empty()) {cout << "YES" << '\n' ;}
        else {cout << "NO" << '\n';}
    }

    return 0 ;
}
发表于 2026-01-18 16:22:20 回复(0)
提交观点

问题信息

难度：
4条回答 168浏览

热门推荐

相关试题

括号的匹配

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号