判断一个括号字符串是否匹配正确，如果括号有多种，怎么做？如（_百度笔试题

推荐

香蕉牛奶

用栈来出现，凡是左括号就压栈，凡是右括号就出栈，最后如果栈为空就匹配正确

编辑于 2015-01-28 16:29:31 回复(0)

FantasyLin

以下是我用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)

时态的空白&trade;

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)

dandelion_lt

#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)

hellolintong

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

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)

ChenXj

栈

发表于 2018-06-21 12:40:56 回复(0)

mark2017

请问如果只有()这种括号，不用栈怎么做？？？？？

发表于 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)

lukas_513

发表于 2016-12-05 16:17:31 回复(0)

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)

modewise

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)

coco酱是个程序媛哟

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)

ABCD

如果是这样的呢:(][)或者([)]或者)([]能算是对的吗？

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

判断一个括号字符串是否匹配正确，如果括号有多种，怎么做？如（

问题信息

热门推荐

相关试题