[编程题]括号配对问题
- 热度指数：12620 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
在一行中输入一个字符串
，长度
，由可见字符组成。
输出描述:
；否则输出
。
示例1
输入
abcd(])[efg
输出
false
说明
提取括号 `(`、`)`、`[`、`]` 后为 `(])[`，不是合法括号序列。
示例2
输入
a[x(y)z]
输出
true
说明
提取括号后为 `[()]`，是合法括号序列。
""""
括号匹配，借助栈后进先出的性质
"""
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)
#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)
本题是很简单的一道题，当时学数据结构的书上讲到栈的部分正好就有本题的一个例子，即用栈
来保存左边括号，遇到右边括号便与当前栈顶进行匹配。但是本题在题目描述上有点粗糙，一开
始我只是输出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(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)
#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)
#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)
#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)
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)
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)
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)
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)
import sys
for line in sys.stdin:
s = line.strip()
stack = []
pairs = {')': '(', ']': '['}
for char in s:
if char in '([':
stack.append(char)
elif char in pairs:
if not stack&nbs***bsp;stack.pop() != pairs[char]:
print("false")
break
else:
print("true" if not stack else "false")
发表于 2025-10-30 20:20:49
回复(0)
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
class stack{
constructor(){
this.arr=[]
}
pop(){
this.arr.pop()
}
push(data){
this.arr.push(data)
}
query(){
return this.arr.at(-1)
}
size(){
return this.arr.length
}
}
void async function () {
const map=new Map([
[']','['],
[')','('],
// [']','['],
])
let stack1=new stack()
let s=new Set([']','[',')','('])
let arr1=[]
let tokens=0
let linecount=0
let i=0;
let str='';
// let s=''
// Write your code here
while(line = await readline()){
tokens = [...line.split(' ')];
str=tokens[0]
for(let i of str){
if(!s.has(i)){continue}
if(i==='['||i==='('){
stack1.push(i)
}else{
if(stack1.query()==map.get(i)){
stack1.pop()
}else{
stack1.push(i)
}
}
}
// while(stack1.query()){
// stack1.pop()
// }
// }
// let a = parseInt(tokens[0]);
// let b = parseInt(tokens[1]);
// console.log(a + b);
}
let res=stack1.size()>0?false:true
console.log(res)
}()
发表于 2025-10-28 16:24:53
回复(0)
#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)
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)
利用栈先进后出的特点解题，遇到第一个右括号就与栈顶元素进行比较。
#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)
#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)
问题信息
通过挑战的用户
查看代码-
2022-09-02 14:02:18
-
2022-08-30 19:23:21
-
2022-08-30 16:20:25
-
2022-08-27 19:04:47
-
2022-08-26 10:32:25
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
