首页 > 试题广场 >

括号配对问题

[编程题]括号配对问题

热度指数：14811 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给定一个字符串 $S$ ，请检查字符串中仅由括号字符 $\texttt{`['}$ 、 $\texttt{`]'}$ 、 $\texttt{`('}$ 、 $\texttt{`)'}$ 组成的子序列是否构成合法括号序列。合法括号序列的定义如下：

$\hspace{23pt}\bullet\,$ 空序列是合法括号序列；

$\hspace{23pt}\bullet\,$ 如果 $A$ 是合法括号序列，则 `(A)` 和 `[A]` 都是合法括号序列；

$\hspace{23pt}\bullet\,$ 如果 $A$ 和 $B$ 都是合法括号序列，则它们的拼接 $AB$ 也是合法括号序列。

$\hspace{15pt}$ 字符串 $S$ 可能包含其他字符，但只需考虑括号部分，忽略其他字符。

输入描述:

在一行中输入一个字符串 ，长度 ，由可见字符组成。

输出描述:

如果字符串  中的括号部分能构成合法括号序列，则输出 ；否则输出 。

示例1

输入

abcd(])[efg

输出

false

说明

提取括号 `(`、`)`、`[`、`]` 后为 `(])[`，不是合法括号序列。

示例2

输入

a[x(y)z]

输出

true

说明

提取括号后为 `[()]`，是合法括号序列。

算法知识视频讲解

Python

ElonB

""""
括号匹配，借助栈后进先出的性质
"""

if __name__ == "__main__":
    s = input().strip()
    ans = True
    flag = []
    for c in s:
        if c == '[' or c == '(':
            flag.append(c)
        elif c == ']':
            if not flag or flag.pop() != '[':
                ans = False
                break
        elif c == ')':
            if not flag or flag.pop() != '(':
                ans = False
                break
        else:
            pass
    if flag:
        ans = False
    print("true" if ans else "false")

编辑于 2019-07-12 11:22:20 回复(0)

孙玉朝

将无论是中括号还是小括号，只要遇到左括号 [ 或（就入栈。

遇到了右括号 ] 或者），就直接查看栈顶元素是不是与之配对，如果是，则匹配成功，否则匹配失败。

大二数据结构书中的简单计算器中的括号配对，就是用的这个原理，这个栈，就是急迫队列，我们遇到的右括号会和急迫队列中的左括号匹配。

import java.util.Scanner;
import java.util.Stack;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        System.out.println(check(str));
    }
    private static boolean check(String str){
        char[] chars = str.toCharArray();
        Stack<Character> match = new Stack<>();
        for (char ch : chars) {
            if (ch=='[' || ch=='('){
                match.push(ch);
            }else if (ch==']'){
                if (match.empty() || match.pop()!='[') return false;
            }else if (ch==')'){
                if (match.empty() || match.pop()!='(') return false;
            }
        }
        return true;
    }
}

发表于 2020-03-15 15:38:28 回复(1)

那年，那些年

循环结束后还应该判断一下栈内是否为空，若为空再返回true

例如：输入为"(()()()"，返回应该为false，本例返回true

发表于 2019-06-26 09:27:41 回复(2)

C/C++

Andrew_Y

本题是很简单的一道题，当时学数据结构的书上讲到栈的部分正好就有本题的一个例子，即用栈
来保存左边括号，遇到右边括号便与当前栈顶进行匹配。但是本题在题目描述上有点粗糙，一开
始我只是输出flag，但是调试一直提示失败，然后才明白要输出的是字符串………………
#include<iostream>
#include<string>
#include<stack>
using namespace std;

int main()
{
    string s;
    cin>>s;
    stack<char> tmp;
    bool flag=false;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='[')
            tmp.push(s[i]);
        if(s[i]=='(')
            tmp.push(s[i]);
        if(s[i]==']')
        {
            if(tmp.empty())
            {
                flag=false;
                break;
            }
            else{
            char c=tmp.top();
            tmp.pop();
            if(c=='[')
                flag=true;
            else
            {
                flag=false;
                break;
            }
            }
        }
        if(s[i]==')')
        {
            if(tmp.empty())
            {
                flag=false;
                break;
            }
            else{
            char c=tmp.top();
            tmp.pop();
            if(c=='(')
                flag=true;
            else
            {
                flag=false;
                break;
            }
            }
        }
    }
    if(!tmp.empty())
        flag=false;
    if(flag)
        cout<<"true";
    else
        cout<<"false";
}

发表于 2019-10-14 21:02:52 回复(0)

WMYW

#include<iostream>
#include<stack>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int i=0;
    stack<char> t;
    while(i<s.size())
    {
        if(t.empty()&&(s[i]==']'||s[i]==')'))
        {
            cout<<"false";
            return 0;
        }
        else if(s[i]=='['||s[i]=='(')
            t.push(s[i]);
        else if(s[i]==']')
        {
            if(t.top()=='[')
                t.pop();
            else
            {
                cout<<"false";
                return 0;
            }
        }
        else if(s[i]==')')
        {
            if(t.top()=='(')
                t.pop();
            else
            {
                cout<<"false";
                return 0;
            }
        }
        i++;
    }
    if(t.empty())
        cout<<"true";
    else
        cout<<"false";
}

编辑于 2020-02-16 10:21:55 回复(0)

C/C++

昔遥暮云

#include <bits/stdc++.h>
using namespace std;
int main(){
    stack<char> st;
    bool flag=true;
    char c;
    while((c=cin.get())!='\n'){
        if(c=='('||c=='[')
            st.push(c);
        else if(c==')'){
            if(st.empty()||st.top()!='('){
                flag=false;
                break;
            }
            st.pop();
        }
        else if(c==']'){
            if(st.empty()||st.top()!='['){
                flag=false;
                break;
            }
            st.pop();
        }
    }
    cout<<(flag ? "true":"false");
    return 0;
}

发表于 2019-10-19 17:55:59 回复(0)

乌托邦的难民

#include<stdio.h>
#define MAXSIZE 1000
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef struct{//顺序栈的定义 
	char c[MAXSIZE];
	int top;
}SeqStack;

void initStack(SeqStack *s);
int push(SeqStack *s, char c);
int pop(SeqStack *s, char *c);
int getTop(SeqStack *s, char *c);
int isTrue(char *temp, char c);
void outStack(SeqStack *s);

int main()
{
	SeqStack s, *s1 = &s;
	char str[MAXSIZE] = {"\0"};
	scanf("%s", str);
	initStack(s1);
	for(int i = 0; str[i] != '\0'; i++)
	{
//		outStack(s1);
		char b, *temp = &b;
		char c = str[i];
		switch(c)
		{
			case '(':
			case '[':
			case '{':
				push(s1, c);//压进栈内 
				break;
			case ')':
			case ']':
			case '}': 
				if(getTop(s1, temp) && isTrue(temp, c))	pop(s1, temp);
				else
				{
					printf("false\n");
					return 0;
				}
				break;
		}
	}
	if(s1->top != -1)
	{
		printf("false\n");
		return 0;
	}
	else printf("true\n");
	return 0;
}

//初始化顺序栈
void initStack(SeqStack *s)
{
	s->top = -1;
}

//顺序进栈运算
int push(SeqStack *s, char c)
{
	//将x置入s栈新栈顶
	if(s->top == MAXSIZE - 1)
	return FALSE;
	s->top++;
	s->c[s->top] = c;
	return TRUE;
}

//顺序栈出栈运算
int pop(SeqStack *s, char *c)
{
	//将栈S栈顶元素读出,放到x所指的存储空间中,栈顶指针保持不变
	if(s->top < 0)
	return FALSE;
	*c = s->c[s->top];
	s->top--;
	return TRUE;
} 

//将栈顶元素读出
int getTop(SeqStack *s, char *a)
{
	if(s->top < 0)
	return FALSE;
	*a = s->c[s->top];
	return TRUE;
}

//判断括号是否匹配 
int isTrue(char *temp, char c)
{
	switch(*temp)
	{
		case '(':
			if(c == ')') return TRUE;
			else return FALSE;
			break;
		case '[':
			if(c == ']') return TRUE;
			else return FALSE;
			break;
		case '{':
			if(c == '}') return TRUE;
			else return FALSE;
			break;
		default:
			return FALSE;
			break;
	}
}

发表于 2019-10-13 11:03:35 回复(0)

无心2019

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    stack<char>st;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='('||s[i]=='[')
            st.push(s[i]);
        else if(s[i]==')')
        {
            if(st.top()=='(')
                st.pop();
            else
            {
                cout<<"false";
                return 0;
            }
        }
        else if(s[i]==']')
        {
            if(st.top()=='[')
                st.pop();
            else
            {
                cout<<"false";
                return 0;
            }
        }
        else
            continue;
    }
    if(st.empty())
        cout<<"true";
    else
        cout<<"false";
    return 0;
}

发表于 2019-07-03 10:31:03 回复(0)

Java

呃。。。

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        Stack<Character> stack = new Stack<>();
        for (int i=0;i<str.length();i++){
            char c = str.charAt(i);
            if (c == '(' || c == '[')
                stack.push(c);
            else if (c == ')'){
                if (stack.isEmpty() || stack.pop() != '(') {
                    System.out.println(false);
                    return;
                }
            }else if (c == ']'){
                if (stack.isEmpty() || stack.pop() != '[') {
                    System.out.println(false);
                    return;
                }
            }
        }
        if (stack.isEmpty())
            System.out.println(true);
        else
            System.out.println(false);
    }
}

发表于 2019-08-14 15:27:33 回复(0)

Polestar_a

s = input()
left = ['[','(']
right = [']',')']
pair = {'[':']','(':')'}
res = []
for i in s:
    if i in left:
        res.append(i)
    if i in right:
        if res and pair[res[-1]]==i:
            res.pop()
        else:
            res.append(i)
            break
print('true' if not res else 'false')

发表于 2019-07-09 21:56:57 回复(1)

C/C++

广州市民林先生

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main(){
    // 后出现，先配对： ( [ ] ) 如左图, ]要先配对，所以采用栈
    string str;
    stack<char> st;
    cin >> str;
    for(int i = 0; i < str.length(); ++i){
        if(str[i] == '(' || str[i] == '['){
            st.push(str[i]);
        }
        else if(str[i] == ')'){
            if(!st.empty() && st.top() == '('){
                st.pop();
            } else{
                cout << "false" << endl;
                return 0;
            }
        }
        else if(str[i] == ']'){
            if(!st.empty() && st.top() == '['){
                st.pop();
            } else{
                cout << "false" << endl;
                return 0;
            }
        }
    }
    cout << "true" << endl;
    return 0;
}

发表于 2020-05-30 11:37:38 回复(0)

Python3

意若久时天然呆

import sys

a, s, t = "", "", []

for line in sys.stdin:

a = line.split()

for i in a[0]:

if i in "()[]":

s += i

for j in s:

if len(t) == 0:

t.append(j)

else:

t.pop(-1) if t[-1] + j in ["()", "[]"] else t.append(j)

print("true" if not t else "false")

发表于 2025-11-14 08:50:32 回复(0)

Java

BraveCoder

import java.util.Scanner;
import java.util.Stack;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.next();
        System.out.print(bracketMatch(str));
    }

    public static boolean bracketMatch(String str) {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);

            // 如果是左括号，入栈
            if (c == '(' || c == '[') {
                stack.push(c);
            }
            // 如果是右括号
            else if (c == ')' || c == ']') {
                // 栈为空，没有匹配的左括号
                if (stack.isEmpty()) {
                    return false;
                }

                // 弹出栈顶元素并检查是否匹配
                char top = stack.pop();
                if ((c == ')' && top != '(') || (c == ']' && top != '[')) {
                    return false;
                }
            }
        }

        // 所有括号处理完毕后，栈必须为空才是完全匹配
        return stack.isEmpty();
    }
}

发表于 2025-07-31 16:43:06 回复(0)

C++

追风的羽汀

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    stack<char> ss;
    bool flag = true;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='(' || s[i]=='[')
        {
            ss.push(s[i]);
        }
        else if(s[i]==')' || s[i]==']')
        {
            if( ss.size()==0 )
            {
                flag=false;
                break;
            }else if((s[i]==')' && ss.top()=='(') || (s[i]==']' && ss.top()=='[')){
                ss.pop();
            }else {
                flag=false;
                break;
            }
        }
        else{}
    }
    if(ss.empty() && flag == true){
        cout << "true";
    }else if(flag == false){
        cout << "false";
    }
}

发表于 2025-07-28 19:44:38 回复(0)

Python3

勇闯无人区

A = list(map(str,input().strip()))
legal_arr = []

brask = {'(':')','[':']'}

for a in A:
    if a in '()[]':
        if a in brask: #是左括号
            legal_arr.append(a)
        elif a in brask.values(): #是右括号
            if not legal_arr&nbs***bsp;brask[legal_arr[-1]] != a: 
                #为空或者前面的不是左括号，此时肯定大于1，结束函数并输出false
                print('false')
                exit()
            legal_arr.pop() #不为空且前面的是左括号，弹出前面的和不存当前的右括号

print('true' if not legal_arr else 'false')

发表于 2025-07-23 17:15:23 回复(0)

JavaScript

萌萌萌哒

JavaScript(Node) 😎题目:唯品会💄-括号配对问题（stack+flag）

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    ouput: process.stdout
})
rl.on('line', line=>{
    let inArr = line.trim().split(' ')
    let s = inArr[0].split('')
    let stack = []
    let flag = 1
    for (let i = 0; i < s.length; i++) {
        if(s[i] == '[' || s[i] == '('){
            stack.push(s[i])
        }else if(s[i] == ']' || s[i] == ')'){
            if(stack.length === 0){
                flag = 0
                break
            }
            let c = stack[stack.length -1]
            stack.pop()
            if((c == '[' && s[i] != ']') || ( c == '(' && s[i] != ')' )){
                flag  = 0
                break
            }
        }
    }
    if(stack.length !== 0){
        flag = 0
    }
    console.log(flag? 'true' : 'false')
})

发表于 2020-03-01 17:39:19 回复(0)

Comeand

#include <stdio.h>

#include <stdbool.h>

int main(){

int s;

char stack[500];

int top=-1;

bool hefa=true;

while((s=getchar())!=EOF&&hefa){

switch(s) {

case'(':

case'[':

stack[++top]=s;

break;

case')':

if(top==-1||stack[top]!='('){

hefa=false;

}

else{

top--;

}

break;

case ']':

if(top==-1||stack[top]!='['){

hefa=false;

}

else{

top--;

}

break;

}

if(hefa&&top==-1){

printf("true");

}else {

printf("false");

}

return 0;

}

发表于 2025-11-22 15:39:08 回复(0)

Python3

袁钦照

s = input()
rule = ["[","]","(",")"]
list_r = [["[","]","(",")"],["(",")","[","]"],["(","[","]",")"],["[","(",")","]"],["(",")"],["[","]"]]
list_s = []
list_n = []
n = 1
for i in s:
    if i in rule:
        list_s.append(i)
if len(list_s)<=4:
    if list_s in list_r:
        res = "true"
    else:
        res = "false"
if len(list_s)>4:
    while len(list_s)> 4:
        list_n = list_s[-4:]
        list_s = list_s[:-4]
        if list_n in list_r:
            res = "true"
        else:
            res = "true"
    if len(list_s)<=4:
        if list_s in list_r:
            res = "true"
        else:
            res = "false"
print(res)

史山代码

发表于 2025-11-19 14:32:56 回复(1)

Python3

牛客633339748号

import sys

source_str = ""

for line in sys.stdin:

source_str = line.split()

dest_str = ""

for m in source_str[0]:

if m in "()[]":

dest_str += m

stack =[]

for c in dest_str:

if len(stack) == 0 :

stack.append(c)

else:

if (stack[-1]+c) in ['()', '[]']:

stack.pop(-1)

else:

stack.append(c)

if len(stack) == 0:

print("true")

else:

print("false")

发表于 2025-11-12 06:57:17 回复(0)

牛客736096499号

#include <stdio.h>

#include<stdlib.h>

int main() {

int cap=4;

char *stack=(char*)malloc(cap*sizeof(char));

int top=-1;

char c;

if(stack==NULL){

printf("内存分配失败");

return 1;

}

while((c=getchar())!=EOF&&c!='\n')

{

if(c=='('||c=='['||c==')'||c==']')

{

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

{top++;

if(top+1>cap){

cap*=2;

stack=(char*)realloc(stack,cap*sizeof(char));

}

stack[top]=c;

}

else{

if(top==-1){

printf("false\n");

free(stack);

return 0;

}

if((c==')'&&stack[top]=='(')||(c==']'&&stack[top]=='['))

{

top--;

}

else{

printf("false");

free(stack);

return 0;

}

if(top==-1){

printf("true\n");

}

else{

printf("false\n");

}

free(stack);

return 0;

}

发表于 2025-11-11 21:22:39 回复(0)

提交观点

问题信息

字符串栈唯品会测试工程师

来自：唯品会2019秋招互金测试岗

上传者：小小

难度：

38条回答 170收藏 10192浏览

通过挑战的用户

查看代码

牛客13331...

2022-09-02 14:02:18
牛客91087...

2022-08-30 19:23:21
牛客21133...

2022-08-30 16:20:25
前端学习中

2022-08-27 19:04:47
牛客28225...

2022-08-26 10:32:25

括号配对问题

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题