首页 > 试题广场 >

Problem E

[编程题]Problem E
  • 热度指数:4344 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
请写一个程序,判断给定表达式中的括号是否匹配,表达式中的合法括号为”(“, “)”, “[", "]“, “{“, ”}”,这三个括号可以按照任意的次序嵌套使用。

输入描述:
有多个表达式,输入数据的第一行是表达式的数目,每个表达式占一行。


输出描述:
对每个表达式,若其中的括号是匹配的,则输出”yes”,否则输出”no”。
示例1

输入

4
[(d+f)*{}]
[(2+3))
()}
[4(6]7)9

输出

yes
no
no
no
({}))}()]]})})[}}{{[{}{)]]]]]([){}{])[)([[}}))([]}[{{{}){{}}[)({[]{)}]}}}((([)[]([){)(}][{{[}[)[}]]}[](}))}][}](){{[])}}[)[}{]})[}[[[])]{(](}({([[)})(})[)](({)()([]))]})(]({){{)}([(}([()[(]]{)){{{]})(]({)}([([(][])[]{{))}}[]))}([]{()())())(}{({}[))({]()}]{[[[]]{]}{{[}()]}[((}[}])(()}}{{[{(}{][]){}({(({[{[[()]}}](){{}()]]}[]{({){[)[{{(((}{)(]()({]]](](]}(}]{([{[{](}){{}}{}]]]})){}(]}]]()})])]){)([]{)[)(}{{(}}])][([](){}(][[{)(({]}(([][{{{]}](}][{)((){))(}]}]){}[[}}{])(([]()((][{)]]}{){)[{}(])[[(}}{}}(}][]]]}{}[){}{[[}{)})[[)])[)[}}}{}]{]{[{})((}[(()[([{((})(()[(](}[[[{{{)
通过率60%,这个用例不应该是no?
发表于 2020-04-13 09:46:19 回复(0)
#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)
[(d+f)*{}]
为什么结果是no!?
发表于 2019-06-25 22:02:54 回复(1)
 #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)
发表于 2020-06-10 10:17:16 回复(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 <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 回复(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)
#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:注意栈顶指针的使用,是先入栈再增加栈顶指针还是先增加栈顶指针再入栈要考虑清楚;
最后判断是否匹配的时候,由于我预先设置的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)
#include <iostream>
#include <stack>

using namespace std;

void func(string s) {
    stack<char> stack1;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            stack1.push(s[i]);
        } else if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
            if (stack1.empty()) {
                printf("no\n");
                return;
            }
            if (s[i] == ')' && stack1.top() == '(') {
                stack1.pop();
            } else if (s[i] == ']' && stack1.top() == '[') {
                stack1.pop();
            } else if (s[i] == '}' && stack1.top() == '{') {
                stack1.pop();
            }
        }
    }
    if (stack1.empty()) {
        printf("yes\n");
    } else {
        printf("no\n");
    }
}

int main() {
    int N;
    string s;
    while (cin >> N) {
        for (int i = 0; i < N; ++i) {
            cin >> s;
            func(s);
        }
    }
    return 0;
}

发表于 2019-09-09 10:10:13 回复(0)

问题信息

上传者:小小
难度:
28条回答 3029浏览

热门推荐

通过挑战的用户

查看代码