首页 > 试题广场 >

判断一个括号字符串是否匹配正确,如果括号有多种,怎么做?如(

[问答题]
判断一个括号字符串是否匹配正确,如果括号有多种,怎么做?如(([]))正确,[[(()错误。
推荐
用栈来出现,凡是左括号就压栈,凡是右括号就出栈,最后如果栈为空就匹配正确
编辑于 2015-01-28 16:29:31 回复(0)
以下是我用Java编写的代码,是用“栈”来辅助解决的,有考虑到括号的优先级。比如{1[2(3)4]5} 是正确的。但是[1{2}3]是不正确的。具体代码如下:
package javaTest;

import java.util.Stack;

public class JavaTest {

    public static boolean solve(StringBuilder str) {
    	
    	if (str.length() == 0) return false;
    	
    	Stack<Character> stack = new Stack<Character>();
    	
    	for (int i = 0; i < str.length(); i++) {
    		char ch = str.charAt(i);
    		switch (ch) {
    		case '{':
    		case '[':
    		case '(':
    			if (!stack.empty()) {
    				char chX = stack.peek();
    				if ((ch == '{' && chX == '{')
    						|| (ch == '{' && chX == '[')
    						|| (ch == '{' && chX == '(')
    						|| (ch == '[' && chX == '[')
    						|| (ch == '[' && chX == '(')
    						|| (ch == '(' && chX == '(')) {
    					return false; //左括号入栈前,要判断优先级,如果不符合,则false
    				} else {
    					stack.push(ch); //符合优先级,则入栈
    				}
    			} else {
        			stack.push(ch);
    			}
    			break;
    		case '}':
    		case ']':
    		case ')':
    			if (!stack.empty()) {
    				char chX = stack.pop();
    				if ((ch == '}' && chX != '{')
    						|| (ch == ']' && chX != '[')
    						|| (ch == ')' && chX != '('))
    					return false;
    			} else {
    				return false;
    			}
    			break;
    		default:
    			break;
    		}
    	}
    	
    	if (!stack.empty()) //栈内不为空,则证明还有左括号没有匹配,所以false
    		return false;
    	else
    		return true;
    }
    
	public static void main(String[] args) {
		StringBuilder str = new StringBuilder();
		str.append("(){}[]{[]}([])");
		System.out.print(solve(str));
	}
}

编辑于 2016-10-05 15:06:47 回复(3)
static boolean isMatch(String s) {  
        Stack<Character> sk = new Stack<Character>();  
        for (int i = 0; i < s.length(); i++) {  
            if (s.charAt(i) == '(') {  
                sk.push('(');  
            }  
            if (s.charAt(i) == ')') {  
                if (!sk.isEmpty() && sk.pop() == '(')  
                    continue;  
                else  
                    return false;  
            }  
            if (s.charAt(i) == '[') {  
                sk.push('[');  
            }  
            if (s.charAt(i) == ']') {  
                if (!sk.isEmpty() && sk.pop() == '[')  
                    continue;  
                else  
                    return false;  
            }  
        }  
        if (sk.isEmpty())  
            return true;  
        else  
            return false;  
    } 

发表于 2015-09-08 21:52:57 回复(0)
首先先定义不同类型的匹配原则,如 (匹配),【匹配】,{匹配}。再借助栈,遇到左括号则入栈,遇到右括号则比较它和栈顶括号的类型,要是不匹配则终止返回错误,要是匹配则将栈顶元素出栈,继续往字符串右边走,接着入栈或是判断。一直到走到字符串的尾部,且栈为空,则返回正确
发表于 2015-08-11 11:04:19 回复(0)
 
#include<iostream>
#include<string>
#include<stack>
using namespace std;

bool IsMatch(string str)
{
	int i=0;
	stack<char> stk;
	bool flag=true;
	while(str[i]!='\0'&&flag==true)
	{
		switch(str[i])
		{
			case '(':
			case '[':
			case '{':stk.push(str[i]);break;
			case ']':
				{
					if(stk.top()=='[')
						stk.pop();
					else
						flag = false;
					break;
				}
			case ')':
				{
					if(stk.top()=='(')
						stk.pop();
					else
						flag = false;
					break;
				}
			case '}':
				{
					if(stk.top()=='{')
						stk.pop();
					else
						flag = false;
					break;
				}
		}
		i++;
	}
	if(!stk.empty())
		flag=false;
	return flag;
}

void main()
{
	string str;
	char c;
	while((c=cin.get())!='\n')
		str=str+c;
	if(IsMatch(str))
		cout<<"正确"<<endl;
	else
		cout<<"不正确"<<endl;
}

发表于 2015-09-17 16:30:34 回复(1)
import java.util.Stack; 
public class Solution{
      public boolean isMatch(String str){
            Stack stack = new Stack();
            for(int i = 0; i < str.length(); ++i){
                char ch = str.charAt(i);
                if(ch == '[' || ch == '{' || ch == '('){
                     stack.push(ch); 
                } else if(ch == ']' || ch == '}' || ch == ')'){
                    if(stack.isEmpty()){
                         return false; 
                    }
                   char top = stack.peek();
                   if(ch == ']' && top == '[' || ch == '}' && top == '{' || ch == ')' && top == '('){
                      stack.pop();
                     }
                     else{
                       return false;
                     }
                }
             }
         return stack.isEmpty(); 
      } 
    public static void main(String[] args){
         String str = "{{[sda]}}}()";
         Solution solution = new Solution();               
         System.out.println(solution.isMatch(str)); 
  }
 } 

发表于 2015-04-07 17:14:18 回复(2)
YvY头像 YvY
java代码。
我的理解是括号要对应,][这种情况应该算错的。
	public static boolean Judge(String str){
		if(str==null||str.trim().equals("")){
			return false;
		}
		HashMap<Character , Character> Brackets=new HashMap<Character, Character>();
		Brackets.put('(', ')');
		Brackets.put('{', '}');
		Brackets.put('[', ']');
		char ch[] =str.toCharArray();
		int length = ch.length;
		if(length%2!=0){
			return false;
		}
		for(int i = 0 ; i<length/2 ;i++ ){
			try{
				if(Brackets.get(ch[i])!=ch[length-i-1]){
					return false;
				}
			}catch(Exception e){
				return false;
			}
		}
		return true;
	}

编辑于 2015-08-18 16:54:04 回复(1)
思路:
使用【栈】,从头到尾依次读取每个字符,遇到一个左括号则将其入栈,一个右括号则出栈一个元素并将两者进行匹配,如果是一对则继续往后读,如果不是一对则返回错误。如果读完后栈为空,则返回正确,栈不空则返回错误
伪码:
读取一个字符 c;
for(遍历每一个字符 c){
if(c 属于 左括号){
入栈;
}else if(c 属于 右括号){
if(栈为空)
return false
栈顶字符 tar 出栈;
if(c 与 tar 不属于一对)
return false;
}
}
// 字符读取完毕
if(栈空)
return true;
else
return false;
代码:
public static boolean ifValidate(String str){
        Stack<Character> stack = new Stack<Character>();
        int len = str.length();
        char c;
        for(int i = 0; i < len; i++){
            c = str.charAt(i);
// 左括号-入栈
            if('(' == c )
                stack.push(')');
            if('[' == c )
                stack.push(']');
            if('{' == c)
                stack.push('}');
// 右括号-比较
            if(')' == c || ']' == c || '}' == c){
                if(stack.empty())
                    return false;
                if (stack.pop() != c)
                    return false;
            }
        }
        if(!stack.empty())
             return false;
        return true;

发表于 2019-06-24 17:58:25 回复(0)
使用栈就可以简单解决:遍历字符串,遇到左括号就入栈,遇到右括号就和栈定比较是否匹配,若匹配则栈定出栈,继续遍历。

import java.util.Scanner;
import java.util.Stack;

/**
 * @Title:
 * @Description:
 * @author: zwq
 * @date: 2020/2/813:57
 */
public class Kuohao {
	
	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		String str = "";
		if (in.hasNext()){
			str = str + in.next();
		}

		if(kuoHaoStack(str)){
			System.out.println(true);
		}else {
			System.out.println(false);
		}


	}

	public static boolean kuoHaoStack(String str){
		Stack<String> stringStack = new Stack<>();
		for (int i=0;i<str.length();i++){
			String current = strAt(str,i);
			int leftOrRight = leftOrRight(current);
			if(leftOrRight == -1){
				stringStack.push(current);
			}else if(leftOrRight == 1){
				String top = stringStack.peek();
				if(kuoHaoPiPei(top,current)){
					stringStack.pop();
				}else {
					return false;
				}
			}
		}
		return true;
	}

	/**
	 * 判断括号匹配
	 * @return
	 */
	public static boolean kuoHaoPiPei(String a,String b) {
		if (a.equals("(") || b.equals(")"))
			return true;
		if (a.equals("[") || b.equals("]"))
			return true;
		if (a.equals("{") || b.equals("}"))
			return true;

		if (b.equals("(") || a.equals(")"))
			return true;
		if (b.equals("[") || a.equals("]"))
			return true;
		if (b.equals("{") || a.equals("}"))
			return true;

		return false;
	}

	/**
	 * 判断括号为左括号或者右括号
	 * @param str
	 * @return: 1:右括号,-1:左括号,0:其他
	 */
	private static int leftOrRight(String str){
		if(str.equals(")") || str.equals("]") || str.equals("}")){
			return 1;
		}else if(str.equals("(") || str.equals("[") || str.equals("{")){
			return -1;
		}
		return 0;
	}

	/**
	 * 获取某个位置字符
	 * @param str
	 * @param i
	 * @return
	 */
	private static String strAt(String str,int i){
		String currentStr = str.substring(i,i+1);
		return currentStr;
	}
}


发表于 2020-02-08 15:22:46 回复(0)

发表于 2018-06-21 12:40:56 回复(0)
请问如果只有()这种括号,不用栈怎么做?????
发表于 2017-09-21 00:23:27 回复(0)

/**

 * 括号匹配问题 

 * 要求:满足正确的匹配关系(包括括号正确配对与{[(的正确嵌套) 

 * 解决:利用栈的思想依次将符号入站(紧急匹配的符号一定在栈顶)

 * 如果刚好匹配则出栈(在这里需要注意在入栈时进行嵌套关系判断 即栈中只有左边括号)

 */

public class 括号匹配 {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

String str = in.nextLine();

char[] arr = str.toCharArray();

Boolean flag = check(arr);

System.out.println(flag);

}


private static Boolean check(char[] arr) {

Stack<Character> stack = new Stack<Character>();

// System.out.println(stack.peek());

for (int i = 0; i < arr.length; i++) {

if (stack.isEmpty()) {

stack.push(arr[i]);

} else {

if (compareNest(stack.peek(), arr[i])) {

if (compareSuit(stack.peek(), arr[i])) {

// 正确匹配,出栈

stack.pop();

} else {

stack.push(arr[i]);

}

}

// 嵌套关系错误

else {

return false;

}

}

}

if (stack.isEmpty())

return true;

else

return false;


}


// 确定c1,c2 能否嵌套“{[(”

public static Boolean compareNest(char c1, char c2) {

if (c1 == '(') {

if (c2 == '(' || c2 == ')') {

return true;

} else {

return false;

}

} else if (c1 == '[') {

if (c2 == '[' || c2 == '(' || c2 == ']') {

return true;

} else {

return false;

}

} else

return true;

}


// 比较是否匹配

public static Boolean compareSuit(char c1, char c2) {

if (c1 == '(' && c2 == ')' || c1 == '[' && c2 == ']' || c1 == '{' && c2 == '}')

return true;

else

return false;

}

}

发表于 2017-08-03 22:49:09 回复(0)


发表于 2016-12-05 16:17:31 回复(0)
gdn头像 gdn
def bracket_match(s):
    left = '([{'
    right = ')]}'
    stack = []
    for ch in s:
        if ch in left:
            stack.append(ch)
        else:
            if stack and stack.pop() == left[right.index(ch)]:
                continue
            else:
                return False
    return stack == []


发表于 2016-10-05 20:39:41 回复(0)
void part(int A[], int n)
{
    int left, right;
    int tmp;
    
    left=0; right=n-1;
    while(left<right)
    {
        while(left<n && A[left]%2!=0) left += 1;
        while(right>=0 && A[right]%2==0) right -= 1;
        if(left < right){
            tmp=A[left]; A[left]=A[right]; A[right]=tmp;
        }
    }
}
发表于 2016-08-22 16:13:36 回复(0)
public  boolean init(String s){
		for(int i=0;i<s.length();i++){
			switch(s.charAt(i)){
			case '{': if(s.charAt(s.length()-1-i)!='}'){return false;}break;
			case '[': if(s.charAt(s.length()-1-i)!=']'){return false;}break;
			case '(': if(s.charAt(s.length()-1-i)!=')'){return false;}break;
			}
		}
		return true;
	}

发表于 2016-01-04 10:13:28 回复(0)
#include <iostream>
#include <stack>

using namespace std;

bool str_match(const char * p)
{
	stack<char> st;

	while(*p!='\0')
	{
		if(*p=='(' || *p=='{' || *p=='[')
		{
			st.push(*p);
		}

		if(*p==')' || *p=='}' || *p==']')
		{
			if(st.empty()) return false;
			else
			{
				char q;
				q=st.top();
				if(*p==')' )
				{
					if(q=='(')
					{
						++p;
						st.pop();
					//	continue;
					}else return false;
				}else if(*p=='}')
				{
					if(q=='{')
					{
						++p;
						st.pop();
					//	continue;
					}else return false;
				}else
				{
					if(q=='[')
					{
						++p;
						st.pop();
					//	continue;
					}else return false;
				}
			}	
		}
		else	++p;
	}

	if(st.empty()) return true;
	else return false;

}

int main()
{
	char * str="([*0780{lj;}k'{l])";

	if(str_match(str)) cout<<"match sucess"<<endl;
	else cout<<"match faile"<<endl;


	return 0;
}


发表于 2015-09-11 17:32:09 回复(0)
class Solution():
    def match(self, str):
        s = []
        for i in range(len(str)):
            if str[i] == '{' or str[i] == '[' or str[i] == '(':
                s.append(str[i])
            elif str[i] == '}':
                if s.pop() != '{':
                    return -1
            elif str[i] == ']':
                if s.pop() != '[':
                    return -1
            elif str[i] == ')':
                if s.pop() != '(':
                    return -1
            print(s)


        if len(s) == 0:
            return 1
        else:
            return -1

发表于 2015-09-07 20:36:41 回复(0)

#include<iostream>
#include<stack>

using namespace std;


bool  Ismate(char *str)
{
stack<char> mystr;
while(*str!='\0')
{
if(mystr.empty()||*str=='('||*str=='[')
{
mystr.push(*str);
}
else if(*str==')')
{
if(mystr.top()=='(')
{
mystr.pop();
}
else
return false;
}
else if(*str==']')
{
if(mystr.top()=='[')
{
mystr.pop();
}
else 
return false;
}
str++;
}
if(mystr.empty())
return true;
else
return false;
}

int main()
{
char str[]="(([";
if(Ismate(str))
cout<<"括号匹配";
else
cout<<"括号不匹配";

return 0;

}
发表于 2015-08-28 09:43:48 回复(0)
应该还是用栈,遇到‘(’ 1入栈‘【’ 2入栈 遇到 ‘)’先判断栈顶元素是否是1 如出栈 不是报错。 同理遇到‘】’ 先判断栈顶元素是否是2 是出栈否报错。如果还是其他类型的括号 可以用3,4,5。。。来表示最后栈为空即对。
发表于 2015-08-06 22:39:05 回复(0)
如果是这样的呢:(][)或者([)]或者)([]能算是对的吗?

发表于 2015-07-17 10:27:05 回复(2)