[编程题]括号配对问题
""""
括号匹配，借助栈后进先出的性质
"""
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)
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
回复(0)
本题是很简单的一道题，当时学数据结构的书上讲到栈的部分正好就有本题的一个例子，即用栈
来保存左边括号，遇到右边括号便与当前栈顶进行匹配。但是本题在题目描述上有点粗糙，一开
始我只是输出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)
str1 = input('请输入一个字符串')
left = ['([']
right = [')]']
matchingchar = {']':'[',')':'('}
stack = []
flag = True
for i in str1:
if i in left:
stack.append(i)
if i in right:
if stack==[]:
flag= False
elif matchingchar.get(i)==stack[-1]:
stack.pop()
else:
flag == False
if flag == True and stack==[]:
print('True')
else:
print('False')
发表于 2021-07-01 13:03:35
回复(0)
#include<iostream>
(720)#include<string>
#include<stack>
using namespace std;
int main(void){
string s;
cin>>s;
stack<char> st;
int i;
for (i = 0; i < s.size(); i++){
if (s[i] == '(' || s[i] == '[')
st.push(s[i]);
else if(s[i] == ']'){
if (!st.empty() && st.top() == '[')
st.pop();
else{
cout<<"false"<<endl;
return 0;
}
}
else if(s[i] == ')'){
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;
}
发表于 2020-05-10 16:32:50
回复(0)
更加美丽的Java！import java.util.*; public class Main { private static final List<Character> leftBrackets = Arrays.asList('[', '('); private static final List<Character> rightBrackets = Arrays.asList(']',')'); public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNextLine()){ String str = scanner.nextLine(); if (str.isEmpty()) System.out.println("false"); else System.out.println(isBalanced(str) ? "true" : "false"); } } public static boolean isBalanced(String str){ Stack<Character> stack = new Stack<>(); for (char ch : str.toCharArray()){ if (isLeftBracket(ch)) stack.push(ch); else if (isRightBracket(ch)) { if (stack.isEmpty()) return false; char top = stack.pop(); if (!match(top, ch)) return false; } } return stack.isEmpty(); } public static boolean isLeftBracket(char ch){ return leftBrackets.contains(ch); } public static boolean isRightBracket(char ch){ return rightBrackets.contains(ch); } public static boolean match(char leftBracket,char rightBracket){ return leftBrackets.indexOf(leftBracket) == rightBrackets.indexOf(rightBracket); } }
编辑于 2020-03-20 00:43:04
回复(0)
import java.util.*;
public class Main{
public static void main(String[]args){
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
boolean res = true;
Stack stack = new Stack();
for(int k = 0;k < str.length();k++) {
if(str.charAt(k) == '(' || str.charAt(k) == '[') {
stack.push(str.charAt(k));
}else if(str.charAt(k) == ')') {
if(stack.isEmpty() || (Character)stack.pop() != '(') {
res = false;
break;
}
}else if(str.charAt(k) == ']') {
if(stack.isEmpty() || (Character)stack.pop() != '[') {
res = false;
break;
}
}else{
continue;
}
}
if (!stack.isEmpty()) {
res = false;
}
System.out.println(res);
}
}
发表于 2020-02-26 00:13:48
回复(0)
这个挺简单的，用一个stack保存之前的括号就行了，不过有一些边界条件需要考虑才能A
string = input()
stack = []
END = False
for s in string:
if s.isalpha():
continue
elif s == '[' or s == '(':
stack.append(s)
elif s == ']':
if len(stack) > 0 and stack[-1] == '[':
stack.pop()
else:
print('false')
END = True
break
elif s == ')':
if len(stack) > 0 and stack[-1] == '(':
stack.pop()
else:
print('false')
END = True
break
if not END: print('true' if len(stack) == 0 else 'false')
发表于 2019-09-08 14:46:40
回复(0)
class My_Stack:
def __init__(self, elements=[]):
self._elements = list(elements)
def is_empty(self):
#return not self._elements
return self._elements == []
def push(self, element):
self._elements.append(element)
def pop(self):
if self.is_empty():
raise ValueError
element = self._elements.pop()
return element
def func(input_str):
st = My_Stack()
for ch in input_str:
if ch == "[" or ch == "(":
st.push(ch)
elif ch == "]":
if st.is_empty():
print("false")
return
element = st.pop()
if element != "[":
print("false")
return
elif ch == ")":
if st.is_empty():
print("false")
return
element = st.pop()
if element != "(":
print("false")
return
else:
continue
if not st.is_empty():
print("false")
else:
print("true")
input_str = input()
func(input_str)
发表于 2019-08-30 23:47:59
回复(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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
