[编程题]Problem E
- 热度指数：4717 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
请写一个程序，判断给定表达式中的括号是否匹配，表达式中的合法括号为”(“, “)”, “[", "]“, “{“, ”}”,这三个括号可以按照任意的次序嵌套使用。
输入描述:
有多个表达式，输入数据的第一行是表达式的数目，每个表达式占一行。
输出描述:
对每个表达式，若其中的括号是匹配的，则输出”yes”，否则输出”no”。
示例1
输入
4
[(d+f)*{}]
[(2+3))
()}
[4(6]7)9输出
yes no no no
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
//用栈进行括号匹配，只对(,[,{,进行压栈，对),],}进行与栈顶的匹配
int main(void)
{
vector<string> arr;
int n;
while(cin >> n)
{
while(n--)
{
string s;
cin >> s;
arr.push_back(s);
}
string s1;
for(int i =0;i < arr.size();i++)
{
stack<char> s;
s1 = arr[i];//表达式
char c = s1[0];//存储逐个遍历表达式中的当前字符
int j = 0;
bool mark = 0;//标记遍历字符串的过程中是否已经做出判决
while(c != '\0')//遍历表达式
{
if(c == '(' || c == '[' || c == '{')
s.push(c);
if(c == ')' && !s.empty())
{
char temp = s.top();
if(temp == '(')
s.pop();
else
{
cout << "no" << endl;
mark = 1;
break;
}
}
else if(c == ')' && s.empty())
{
cout << "no" << endl;
mark = 1;
break;
}
if(c == ']' && !s.empty())
{
char temp = s.top();
if(temp == '[')
s.pop();
else
{
cout << "no" << endl;
mark = 1;
break;
}
}
else if(c == ']' && s.empty())
{
cout << "no" << endl;
mark = 1;
break;
}
if(c == '}' && !s.empty())
{
char temp = s.top();
if(temp == '{')
s.pop();
else
{
cout << "no" << endl;
mark = 1;
break;
}
}
else if(c == '}' && s.empty())
{
cout << "no" << endl;
mark = 1;
break;
}
c = s1[++j];
}
//遍历完表达式后做出的判决
if(!s.empty() && mark == 0)
cout << "no" << endl;
if(s.empty() && mark == 0)
cout << "yes" << endl;
}
}
return 0;
}
发表于 2022-02-01 16:01:17
回复(0)
#include<stdio.h>//1.判断个数是否一致
#include<string.h>//2.判断位置(左括号是否在右括号之前
int main()
{
char s[100000];
int i,j,n,key;
scanf("%d",&n);
while(n--)
{
getchar();
gets(s);
int a[6]={0},weizhi[6]={0};
for(i=0;i<strlen(s);i++)
{
if(s[i]=='(')
{a[0]++;weizhi[0]++;}
if(s[i]==')')
{a[1]++;weizhi[1]++;}
if(s[i]=='[')
{a[2]++;weizhi[2]++;}
if(s[i]==']')
{a[3]++;weizhi[3]++;}
if(s[i]=='{')
{a[4]++;weizhi[4]++;}
if(s[i]=='}')
{a[5]++;weizhi[5]++;}
}
key=1;
if(a[0]!=a[1]||a[2]!=a[3]||a[4]!=a[5])//1.个数不一致
key=0;
if(weizhi[0]>weizhi[1]||weizhi[2]>weizhi[3]||weizhi[4]>weizhi[5])//2.后括号在前括号前面
key=0;
if(key==1)
printf("yes\n");
else
printf("no\n");
}
}
编辑于 2020-04-10 14:08:29
回复(1)
括号匹配问题，注意每次输入一个字符串就需要判断，因此栈定义在里面
#include<iostream>
(720)#include<string>
#include<stack>
using namespace std;
int main(){
int n;
string s;
while(cin >> n){
while(n--){
stack<char> st;
cin >> s;
int len=s.size();
bool flag=true;
for(int i=0;i<len;i++){
if(s[i]=='(') st.push(s[i]);
if(s[i]=='[') st.push(s[i]);
if(s[i]=='{') st.push(s[i]);
if(s[i]==')'){
if(st.size()==0){
flag=false;
break;
}
else{
if(st.top()!='('){
flag=false;
break;
}
else st.pop();
}
}
if(s[i]==']'){
if(st.size()==0){
flag=false;
break;
}
else{
if(st.top()!='['){
flag=false;
break;
}
else st.pop();
}
}
if(s[i]=='}'){
if(st.size()==0){
flag=false;
break;
}
else{
if(st.top()!='{'){
flag=false;
break;
}
else st.pop();
}
}
}
if(st.size()!=0) flag=false;
if(flag) cout << "yes" << endl;
else cout << "no" << endl;
}
}
return 0;
}
发表于 2020-04-01 13:01:40
回复(0)
#include<bits/stdc++.h>
using namespace std;
int main()
{
stack<char>s;
int n;
string str;
bool deal;
while(cin>>n)
{
while(n--)
{
cin>>str;
deal = false;
while(!s.empty())
s.pop();
for(int i=0;i<str.size();i++)
{
if(str[i]=='('||str[i]=='{'||str[i]=='[')
s.push(str[i]);
else if(str[i]==')'||str[i]=='}'||str[i]==']')
{
if(s.empty())
{
cout<<"no"<<endl;
deal=true;
break;
}
char c = s.top();
if((str[i]==')'&&c!='(')||(str[i]==']'&&c!='[')||(str[i]=='}'&&c!='{'))
{
cout<<"no"<<endl;
deal=true;
break;
}
s.pop();
}
}
if(!deal)
{
if(s.empty())
cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
}
}
return 0;
} 常规操作。。
发表于 2019-04-30 10:17:38
回复(0)
({}))}()]]})})[}}{{[{}{)]]]]]([){}{])[)([[}}))([]}[{{{}){{}}[)({[]{)}]}}}((([)[]([){)(}][{{[}[)[}]]}[](}))}][}](){{[])}}[)[}{]})[}[[[])]{(](}({([[)})(})[)](({)()([]))]})(]({){{)}([(}([()[(]]{)){{{]})(]({)}([([(][])[]{{))}}[]))}([]{()())())(}{({}[))({]()}]{[[[]]{]}{{[}()]}[((}[}])(()}}{{[{(}{][]){}({(({[{[[()]}}](){{}()]]}[]{({){[)[{{(((}{)(]()({]]](](]}(}]{([{[{](}){{}}{}]]]})){}(]}]]()})])]){)([]{)[)(}{{(}}])][([](){}(][[{)(({]}(([][{{{]}](}][{)((){))(}]}]){}[[}}{])(([]()((][{)]]}{){)[{}(])[[(}}{}}(}][]]]}{}[){}{[[}{)})[[)])[)[}}}{}]{]{[{})((}[(()[([{((})(()[(](}[[[{{{)
通过率60%，这个用例不应该是no？
发表于 2020-04-13 09:46:19
回复(0)
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main(){
int n;
while(cin >> n){
string str;
for(int k=0; k<n; ++k){
cin >> str;
stack<char> bracket;
bool flag = true;
for(int i=0; i<str.size(); ++i){
if(str[i] == '{' || str[i] == '[' || str[i] == '(') {
bracket.push(str[i]);
}else if(str[i] == '}' || str[i] == ']' || str[i] == ')'){
if(bracket.empty()){
cout << "no" << endl;
flag = false;
break;
}else {
if(bracket.top() == '{' && str[i] == '}' || bracket.top() == '[' && str[i] == ']' || bracket.top() == '(' && str[i] == ')') {
bracket.pop();
}
}
}
}
if(!bracket.empty()) cout << "no" << endl;
else if(flag) cout << "yes" << endl;
}
}
}
发表于 2024-03-14 23:06:01
回复(1)
#include <iostream>
using namespace std;
#include "stack"
bool judge_left(char c){//判断是否是左括号
if(c=='('||c=='['||c=='{')
return true;
else return false;
}
bool judge_right(char c){//判断是否是右括号
if(c==')'||c==']'||c=='}')
return true;
else return false;
}
bool match(char c1,char c2){//判断两个符号是否匹配
if(c1 == '(' && c2 == ')')
return true;
else if(c1 == '[' && c2 == ']')
return true;
else if(c1 == '{' && c2 == '}')
return true;
else return false;
}
int main() {
int n;
cin>>n;
while(n--){
string str;
cin>>str;
stack<char>sk;
sk.push('#');//作为栈底
bool flag = true;
for(char & i : str){
if(judge_left(i)){//如果是左括号则入栈
sk.push(i);
}
if(judge_right(i)){//如果是右括号
if(match(sk.top(),i)){//如果和栈顶符号匹配
sk.pop();//弹出栈顶符号
}else{//如果和栈顶元素不匹配
sk.push(i);//这里入栈是为了防止“()}”这种情况
break;
}
}
}
if(sk.top()=='#')//如果栈为空
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
}
发表于 2025-02-12 19:47:47
回复(0)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()) {
int n = scanner.nextInt();
Loop:
for (int i = 0; i < n; i++) {
String str = scanner.next();
List<Character> myList = new ArrayList<Character>();
Stack<Character> myStack = new Stack<Character>();
for (int j = 0; j < str.length(); j++) {
myList.add(str.charAt(j));
}
while(!myList.isEmpty()) {
if (myList.get(0) == '(' || myList.get(0) == '{' || myList.get(0) == '[') {
myStack.push(myList.remove(0));
continue;
}else if (myList.get(0) == ')') {
if (myStack.isEmpty()) {
System.out.println("no");
continue Loop;
}else if (myStack.peek() != '(') {
System.out.println("no");
continue Loop;
}else {
myList.remove(0);
myStack.pop();
}
}else if (myList.get(0) == '}') {
if (myStack.isEmpty()) {
System.out.println("no");
continue Loop;
}else if (myStack.peek() != '{') {
System.out.println("no");
continue Loop;
}else {
myList.remove(0);
myStack.pop();
}
}else if (myList.get(0) == ']') {
if (myStack.isEmpty()) {
System.out.println("no");
continue Loop;
}else if (myStack.peek() != '[') {
System.out.println("no");
continue Loop;
}else {
myList.remove(0);
myStack.pop();
}
}else {
myList.remove(0);
continue;
}
}
if (myStack.isEmpty()) {
System.out.println("yes");
}else {
System.out.println("no");
}
}
}
}
}
编辑于 2024-03-22 17:54:09
回复(0)
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
int n;
while (cin >> n) {
while (n--) {
string str;
cin >> str;
stack<char>brackets;
bool flag = true;
for (const auto& ch : str) {
if (ch == '(' || ch == '[' || ch == '{') {
brackets.push(ch);
} else if (ch == ')') {
if (brackets.empty() || brackets.top() != '(') {
flag = false;
break;
} else {
brackets.pop();
}
} else if (ch == ']') {
if (brackets.empty() || brackets.top() != '[') {
flag = false;
break;
} else {
brackets.pop();
}
} else if (ch == '}') {
if (brackets.empty() || brackets.top() != '{') {
flag = false;
break;
} else {
brackets.pop();
}
}
}
cout << (brackets.empty() && flag ? "yes" : "no") << endl;
}
}
return 0;
}
发表于 2024-03-12 11:29:53
回复(0)
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
//输入字符串，判断每个字符 只需要判断是否是括号即可，如果是别的操作符，不需要做任何操作
while (in.hasNextInt()) {
int n = in.nextInt(); //一共有多少个字符串
in.nextLine();
boolean is_Match = true;
for (int j = 0; j < n; j++) {
String str = in.next();
Stack<Character> stack = new Stack();
for (int i = 0; i < str.length(); i++) {
//如果是左括号直接压入栈中
char c = str.charAt(i);
if (c == '(')
stack.push(c);
else if (c == '[')
stack.push(c);
else if (c == '{')
stack.push(c);
//如果是右括号，判断栈顶元素是否与之匹配，匹配弹出栈顶元素即可
else if (c == ')') {
if (!stack.empty() && stack.peek() == '(') {
stack.pop(); //弹出栈顶元素
} else {
is_Match = false;
break;
}
} else if (c == ']') {
if (!stack.empty() && stack.peek() == '[') {
stack.pop(); //弹出栈顶元素
} else {
is_Match = false;
break;
}
} else if (c == '}') {
if (!stack.empty() && stack.peek() == '{') {
stack.pop(); //弹出栈顶元素
} else {
is_Match = false;
break;
}
} else {
continue; //如果是其他元素，直接遍历下一个元素
}
}
if (is_Match &&
stack.empty()) //当匹配的时候，说明已经遍历完了所有字符串，此时栈中不能有元素
System.out.println("yes");
else
System.out.println("no");
is_Match = true;
}
}
}
}
发表于 2023-03-12 16:08:12
回复(0)
发表于 2021-05-13 22:03:36
回复(0)
#include<cstdio>
#include<iostream>
#include<stack>
#include<string>
using namespace std;
bool isleftbraket(char c){
if(c=='[' || c=='{' || c=='(')
return true;
else
return false;
}
bool isrightbraket(char c){
if(c==']' || c=='}' || c==')')
return true;
else
return false;
}
bool ispair(char c,char b){
if(c == ')'&&b=='(')
return true;
else if(c == ']'&&b=='[')
return true;
else if (c == '}'&&b=='{')
return true;
else return false;
}
stack<char> braket;
int main(){
char c;
string str;
int n;
cin >> n;
getchar();
while(n--){
while(getline(cin,str)){
int flag = 1;
for(int i = 0; i < str.size();i++){
c = str[i];
if(isleftbraket(c))
braket.push(c);
else if(isrightbraket(c)){
if(!braket.empty()&&ispair(c,braket.top()))
braket.pop();
else{
flag = 0;
break;
}
}
else
continue;
}
if(braket.empty()&&flag==1)
cout << "yes"<<endl;
else
cout << "no" << endl;
while(!braket.empty())
braket.pop();
}
}
}
发表于 2021-03-13 11:08:47
回复(0)
#include<cstdio>
#include<string>
#include<iostream>
#include<stack>
using namespace std;
stack<char> st;
string str;
int prior(char c){ //123左括号，456有括号，其他为0
if(c=='(') return 1;
else if(c=='[') return 2;
else if(c=='{') return 3;
else if(c==')') return 4;
else if(c==']') return 5;
else if(c=='}') return 6;
else return 0;
}
int main(){
int n;
cin>>n;
getchar();
while(n--){
getline(cin, str);
for(int i=0;i<str.size();i++){
int temp=prior(str[i]);
if(temp>3&&st.empty()){ //有括号且栈空不匹配
st.push('a'); //随便插入一个字符，以便后面用栈空判断是否匹配
break;
}else if(temp>0){
if(temp<=3){ //左括号直接入栈
st.push(str[i]);
}else {
if(temp==(prior(st.top())+3)){ //判断右括号是否匹配
st.pop();
}else{
break;
}
}
}
}
if(st.empty()) cout<<"yes"<<endl;
else{
cout<<"no"<<endl;
while(!st.empty()) st.pop();
}
}
}
发表于 2021-03-01 22:24:51
回复(0)
栈
tips：注意栈顶指针的使用，是先入栈再增加栈顶指针还是先增加栈顶指针再入栈要考虑清楚；
tips：注意栈顶指针的使用，是先入栈再增加栈顶指针还是先增加栈顶指针再入栈要考虑清楚；
最后判断是否匹配的时候，由于我预先设置的flag为1，所以如果遇到全部为左括号时，跳出循环依旧是flag=1，要再增加一个栈为空的条件。
#include<stdio.h>
#include<string.h>
int main()
{
int sp; // 栈顶指针
int n;
char str[1000];
char bracket[100];
int flag; // 1表示匹配，0表示不匹配
scanf("%d",&n);
for(int i = 0;i<n;i++)
{
sp = -1;
flag = 1;
scanf("%s",str);
for(int j =0 ;j<strlen(str);j++)
{
if(str[j] == '(' || str[j] == '[' || str[j] == '{') // 左括号则入栈
bracket[++sp] = str[j];
else if(str[j] == ')') // 右小括号
{
if(bracket[sp]!= '(')
{
flag = 0;
break;
}
sp--;
}
else if(str[j] == ']') // 右中括号
{
if(bracket[sp]!= '[')
{
flag = 0;
break;
}
sp--;
}
else if(str[j] == '}') // 右大括号
{
if(bracket[sp]!= '{')
{
flag = 0;
break;
}
sp--;
}
}
if(flag && sp == -1)
printf("yes\n");
else
printf("no\n");
}
}
发表于 2021-01-26 15:22:55
回复(0)
#include<cstdio>
#include<stack>
#include<cstring>
using namespace std;
/*4
[(d+f)*{}]
[(2+3))
()}
[4(6]7)9*/
stack<char> tongku;
int main(){
int m=0;
scanf("%d",&m);
while(m--){
char str[50];
scanf("%s",str);
int n=strlen(str);
int flag=0;
for(int i=0;i<n;i++){
if(str[i]=='['||str[i]=='{'||str[i]=='('){
tongku.push(str[i]);
}else if(str[i]==']'||str[i]=='}'||str[i]==')'){
char tm=tongku.top();
if(tongku.empty()){
printf("no\n");
flag=1;
break;
}
else if(tm=='['&&str[i]==']'||tm=='{'&&str[i]=='}'||tm=='('&&str[i]==')'){
tongku.pop();
}else{
printf("no\n");
flag=1;
break;
}
}else{
continue;
}
}
if(tongku.empty()&&flag==0){
printf("yes\n");
}else if(tongku.empty()&&flag==1){
printf("no\n");
}
getchar();
}
return 0;
} 呜呜呜，段错误
发表于 2020-09-27 21:24:48
回复(0)
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
int main(){
int n;
cin>>n;
vector<bool> isMatchs;
for(int i=0; i<n; i++){
stack<int> s;
bool isMatch = true;
string str;
cin>>str;
for(char c : str){
if(c == '(' || c == '[' || c == '{'){
s.push(c);
}else if((c == ')' || c == ']' || c == '}') && !s.empty()){
if(c == ')' && s.top() == '('){
s.pop();
continue;
}else if(c == ']' && s.top() == '['){
s.pop();
continue;
}else if(c == '}' && s.top() == '{'){
s.pop();
continue;
}else{
isMatch = false;
break;
}
}else{
//栈空且遇到右括号
if(s.empty() && (c == ')' || c == ']' || c == '}')){
isMatch = false;
break;
}else{
//其他符号
continue;
}
}
}
//如果栈空且isMatch没有被赋过false，防止：()}
if(s.empty() && isMatch) isMatch = true;
isMatchs.push_back(isMatch);
}
for(bool isMatch : isMatchs){
if(isMatch){
cout<<"yes"<<endl;
}else{
cout<<"no"<<endl;
}
}
return 0;
}
编辑于 2020-05-04 13:55:00
回复(0)
学习了括号匹配问题，该问题不必存储非括号元素，这样每遇到右括号只要拿栈顶元素判断即可，另外，要注意右括号判断前检验右括号是否多余和匹配后检验左括号是否多余。
#include<bits/stdc++.h>
using namespace std;
bool bracketMatch(char str[]){
stack<char> s;
for(int i=0;i<strlen(str);i++){
switch(str[i]){
case '(':
case '[':
case '{':
s.push(str[i]);
break;
case ')':
case ']':
case '}':
if(s.empty()){
return false;//右括号过多
}else{
char temp=s.top();
s.pop();
if(temp=='('&&str[i]!=')'){
return false;
}else if(temp=='['&&str[i]!=']'){
return false;
}else if(temp=='{'&&str[i]!='}'){
return false;
}
}
}
}
if(!s.empty()){
return false;//左括号多余
}
return true;
}
int main(){
int n;
while(~scanf("%d",&n)){
for(int i=0;i<n;i++){
char str[1000];
scanf("%s",str);
bracketMatch(str)?printf("yes\n"):printf("no\n");
}
}
return 0;
}
发表于 2020-03-21 22:06:27
回复(0)
注意点：最后还要判断栈是否为空，不为空则不匹配
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
getchar();
while(n--)
{
stack<char> st;
string s;
getline(cin,s);
int flag=1;
for(int i=0;i<s.size();++i)
{
if(s[i]=='('||s[i]=='['||s[i]=='{') st.push(s[i]);
if(s[i]==')')
{
if(st.empty()||st.top()!='(')
{
flag=0;
break;
}
else st.pop();
}
if(s[i]==']')
{
if(st.empty()||st.top()!='[')
{
flag=0;
break;
}
else st.pop();
}
if(s[i]=='}')
{
if(st.empty()||st.top()!='{')
{
flag=0;
break;
}
else st.pop();
}
}
if(flag&&st.empty()) cout<<"yes\n";
else cout<<"no\n";
}
return 0;
}
发表于 2020-01-30 19:24:27
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-02-27 12:00:08 -
2023-02-04 16:18:24
-
2023-01-09 16:36:08 -
2022-11-28 15:03:49
-
2022-09-06 20:45:11
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
