首页 > 试题广场 >

括号配对问题

[编程题]括号配对问题

热度指数：10569 时间限制：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)

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)

孙玉朝

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

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

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

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)

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)

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)

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)

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)

Nitrene

#include<bits/stdc++.h>

using namespace std;

stack<char> st;

int main(){

string s;

cin>>s;

for( char c:s){

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

st.push(c);

}

else if(c==')'){

if(!st.empty()&& st.top()=='('){

st.pop();

}

else {

cout<<"false"<<endl;

return 0;

}

else if(c==']'){

if(!st.empty()&& st.top()=='['){

st.pop();

}

else {

cout<<"false"<<endl;

return 0;

}

if(st.empty()){

cout<<"true"<<endl;

}

else cout<<"false"<<endl;

return 0;

}

发表于 2025-09-13 14:05:26 回复(0)

Python3

嵩胜Sycml

a = list(input())
temp =[]
res = 1
for aaa in a:
    if aaa == '('&nbs***bsp;aaa=='[':
        temp.append(aaa)
    elif aaa==')':
        if temp:
            temp2 = temp.pop()
            if temp2!= '(':
                res = 0
                print('false')
                break
        else:
            res = 0
            print('false')
            break
    elif aaa==']':
        if temp:
            temp2 = temp.pop()
            if temp2!= '[':
                res = 0
                print('false')
                break
        else:
            res = 0
            print('false')
            break
if res:
    print("true")

防御型代码你值得拥有

发表于 2025-09-06 00:20:37 回复(0)

想去重庆的牛油在debug

利用栈先进后出的特点解题，遇到第一个右括号就与栈顶元素进行比较。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//顺序栈
typedef struct {
    char *str;
    int top;
} stack_t;

//顺序栈的创建与初始化
stack_t *stack_init(int len);
//入栈
void stack_push(stack_t *sq, char data);
//出栈
void stack_pop(stack_t *sq);
//判空
int stack_is_empty(stack_t *sq);

int main() {
    int len;
    char str[10000];
    scanf("%s", str);
    len = strlen(str);
    stack_t *sq = stack_init(len);
    for(int i = 0; str[i] != '\0'; i++){
        if ((str[i] == '(') || (str[i] == '[')){
            stack_push(sq, str[i]);   //满足条件，是左括号，入栈
        } else if ((str[i] != ')') && (str[i] != ']')){
            continue;
        }
        if ((str[i] == ')') || (str[i] == ']')){       //遍历到右括号开始位置，进行配对判断
            if(stack_is_empty(sq) == 0){               //如果栈为空，直接结束程序，并输出false
                printf("false\n");
                free(sq->str);
                free(sq);
                return 0;
            }
            if((sq->str[sq->top] == '(') && (str[i] == ')')){
                stack_pop(sq);     //满足条件，出栈     
                continue;
            }
            else if((sq->str[sq->top] == '[') && (str[i] == ']')){
                stack_pop(sq);     //满足条件，出栈
                continue;
            }
            else{
                printf("false\n");
                free(sq->str);
                free(sq);
                return 0;
            }
        }
    }

    if(stack_is_empty(sq) == -1){
        printf("false\n");
        free(sq->str);
        free(sq);
        return 0;
    } else {
        printf("true\n");
        free(sq->str);
        free(sq);
        return 0;
    }
    return 0;
}




//顺序栈的创建与初始化
stack_t *stack_init(int len)
{
    stack_t *sq = (stack_t *)malloc(sizeof(stack_t));
    if(sq == NULL){
        printf("sq create failed\n");
        return NULL;
    }
    sq->str = (char *)malloc(sizeof(char) * len);
    if(sq->str == NULL){
        printf("sq->str create failed\n");
        return NULL;
    }
    sq->top = -1;
    return sq;
}
//入栈
void stack_push(stack_t *sq, char data)
{
    sq->top += 1;
    sq->str[sq->top] = data;
}
//出栈
void stack_pop(stack_t *sq)
{
    sq->top -= 1;
}
//判空
int stack_is_empty(stack_t *sq)
{
    if(sq->top != -1)
        return -1;       //返回-1为非空
    else
        return 0;        //返回0为空
}

发表于 2025-08-10 17:12:26 回复(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)

Python 3

失落的三文鱼又熬夜了

s = list(input())

stack = []

ifs == '':

print('true')

else:

fori in range(len(s)):

ifs[i] == '('or s[i] == '[':

stack.append(s[i])

ifs[i] == ')':

iflen(stack) != 0 and stack[-1] == '(':

stack.pop(-1)

else:

# print('false')

stack.append(s[i])

# break

ifs[i] == ']':

iflen(stack) != 0and stack[-1] == '[':

stack.pop(-1)

else:

# print('false')

stack.append(s[i])

# break

iflen(stack) == 0:

print('true')

else:

print('false')

发表于 2025-07-25 11:17:41 回复(0)

精致的熊熊在努力存钱

# 通过栈来进行括号匹配
class Stock:

def __init__(self) -> None:

self.li = []

def push(self, x):

self.li.append(x)

def pop(self):

if self.li:

return self.li.pop()

else:

return "Empty"

def query(self):

if self.li:

return self.li[-1]

else:

return "Empty"

def size(self):

return len(self.li)

def pmatch(s: str):

found = True

stock = Stock()

for i in s:

if i == "[":

stock.push(i)

elif i == "(":

stock.push(i)

elif i == ")":

if stock.size() > 0:

result = stock.pop()

if result != "(":

found = False

break

else:

found = False

break

elif i == "]":

if stock.size() > 0:

result = stock.pop()

if result != "[":

found = False

break

else:

found = False

break

else:

pass

if stock.size() == 0 and found:

return "true"

else:

return "false"

if __name__ == "__main__":

s = input()

print(pmatch(s))

发表于 2025-07-19 16:05:51 回复(0)

提交观点

问题信息

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

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

上传者：小小

难度：

31条回答 126收藏 9133浏览

通过挑战的用户

查看代码

牛客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

括号配对问题

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题