首页 > 试题广场 > 合法括号序列判断
[编程题]合法括号序列判断
  • 热度指数:10226 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

给定一个字符串A和其长度n,请返回一个bool值代表它是否为一个合法的括号串(只能由括号组成)。

测试样例:
"(()())",6
返回:true
测试样例:
"()a()()",7
返回:false
测试样例:
"()(()()",7
返回:false
这道题刚开始理解有问题,还以为是((a))这样的形式才算过
其实是判断合法的括号串,出现了非括号的字符就算错
第二个测试例子有点误导
发表于 2016-05-20 19:45:42 回复(5)
    public boolean chkParenthesis(String A, int n) {
        int l = 0; //左括号数
        for (int i = 0; i < A.length(); i++) {
            char c = A.charAt(i);
            if (c == '(') {
                l++;
            } else if (c == ')') {
                if (l > 0) {
                    l--;
                } else {
                    return false;
                }
            } else {
                return false;
            }
        }

        return l == 0;
    }

发表于 2016-08-30 16:55:48 回复(10)
Ron头像 Ron
//1.非递归,使用栈结构
	public boolean chkParenthesis(String A, int n) {
		// write code here
		/*
		 * 1.碰到")"开始弹出栈顶的"(",如果此时栈为空,则返回false
		 * 2.碰到其他内容直接返回false
		 * 3.字符串结尾时,栈非空返回false
		 */
		Stack<Character> lefts = new Stack<Character>();
		if(A == null || A.length() != n){
			return false;
		}
		for(int i = 0; i < n; i++){
			if(A.charAt(i) == '('){
				lefts.push(A.charAt(i));
			}else if(A.charAt(i) == ')'){
				if(lefts.empty()){
					return false;
				}else{
					lefts.pop();
				}
			}else{
				return false;
			}
		}
		if(!lefts.empty()){
			return false;
		}else{
			return true;
		}
	}
//2.递归
    public boolean chkParenthesis(String A, int n) {//递归
		// write code here    	 
		if(A == null || A.length() != n){
			return false;
		}
		ArrayList<Character> chs = new ArrayList<Character>();
		int leftCount = 0, rightCount = 0;
		addParen(chs, leftCount, rightCount, A, 0, n);
		if(chs.size() == n){
			return true;
		}else{
			return false;
		}
	}
	private void addParen(ArrayList<Character> chs, int leftCount, int rightCount,
			String str, int count,int n) {
		// TODO Auto-generated method stub
		if(leftCount < 0 || leftCount < rightCount){
			return;
		}
		if(str.length() == 0){
			return;
		}
		if(leftCount == 0 && rightCount == 0){
			for(int i = 0; i < str.length(); i++){
				if(str.charAt(i) != '(' && str.charAt(i) != ')'){
					return;
				}
			}
		}
		char first = str.charAt(0);
		String remain = str.substring(1);

		if(first == '('){	
			leftCount++;
			if(count+1 == n && leftCount > rightCount){
				return;
			}
			chs.add(first);
			addParen(chs, leftCount, rightCount, remain, count+1, n);
		}else{//')'
			if(leftCount <= rightCount){
				return;
			}
			rightCount++;
			if(count+1 == n && leftCount > rightCount){
				return;
			}
			chs.add(first);
			addParen(chs, leftCount, rightCount, remain, count+1, n);
		}
	}

编辑于 2016-05-22 11:57:37 回复(3)
import java.util.*;
/*
思路:左括号开始,右括号结束,两括号数目必须相等,而且过程中的左括号数目必须大于或等于右括号数目
另外:字符串为奇数必然不是合法的括号串,其实测试例子里还少了一个无括号的情况,我的程序也并没有能力辨别这个
*/
public class Parenthesis {
    public boolean chkParenthesis(String A, int n) {
        if(A.length()%2==1) return false;
        char c[] =A.toCharArray();
        int left =0;
        for(int i=0;i<c.length;i++){
			if(c[i]=='(') left++;
            if(c[i]==')') left--;
            if(left<0) return false;
        }
        if(left ==0) return true;
        return false;
        
    }
}
运行时间:26ms
占用内存:8476k

发表于 2017-06-29 20:21:02 回复(7)
import java.util.*;

public class Parenthesis {
    public boolean chkParenthesis(String A, int n) {
        // write code here
        if(A == null || n == 0){
            return false;
        }
        int flag = 0;
        for(int i = 0 ; i < A.length() ; i++){
            if(A.charAt(i) == '('){
                flag++;
            }else if(A.charAt(i) == ')'){
                flag--;
            }else{
                return false;
            }
            if(flag < 0){
                return false;
            }
        }
        if(flag == 0){
            return true;
        }
        return false;
    }
}

发表于 2018-09-10 18:39:58 回复(0)
class Parenthesis {
public:
    bool chkParenthesis(string A, int n) {
        // write code here
        if(n%2==1)//先排除奇数情况
            return false;
        stack<char> s1;
        for(int i=0;i<A.size();i++)
        {
            if(A[i]=='(')
                s1.push(A[i]);
            else if(A[i]==')')
            {
                if(s1.empty())
                    return false;
                s1.top();
            }
            else 
                return false;
        }
        if(s1.empty())
            return true;
    }
};
可以利用栈把左括号保存,每次遇见右括号就出栈一个,此时如果栈空就为false,遍历期间遇见不是括号也为false,直到遍历结束且栈为空就返回true
发表于 2019-11-12 20:03:05 回复(4)
class Parenthesis {
public:
    bool chkParenthesis(string A, int n) {
        if (n % 2) return false;
        stack<char> st;
        for (char c : A) {
            if ('(' == c) {
                st.push(c);
            } else if (')' == c){
                if (st.empty()) {
                    return false;
                } else {
                    st.pop();
                }
            } else {
                return false;
            }
        }
        return st.empty();
    }
};

运行时间:4ms

占用内存:484k


发表于 2018-12-18 23:40:56 回复(0)
import java.util.*;
/*
分别统计左右括号的数量,左括号++,右括号--,一旦出现负数 返回false
*/
public class Parenthesis {
    public boolean chkParenthesis(String A, int n) {
        // write code here
        int count = 0;
        for(int i= 0;i<n;i++){
            if(A.charAt(i)=='('){
                count++;
            }else if(A.charAt(i)==')'){
                if(count<=0)return false;
                count--;
            }
        }
        if(count==0)return true;
        return false;
    }
}

发表于 2020-06-16 19:34:52 回复(0)
各位大佬们,虽然代码过了但是我有个疑问,为什么我代码没考虑 )()( 这种情况却通过了呢。。。
 class Parenthesis {
public:
    bool chkParenthesis(string A, int n) {
        auto it = A.begin();
        
        //只要出现了除字符“(” 和字符 “)”以外的字符就返回false
        while (it != A.end())
        {
            if (*it != '(' && *it != ')')
            {
                return false;
            }
            it++;
        }
        
        //分别计算字符“(” 和字符 “)”的个数,相等则ture,不相等则false
        int count1 = 0;
        int count2 = 0;
        for (int i = 0; i < n; i++)
        {
            if (A[i] == '(')
            {
                count1++;
            }
            else
            {
                count2++;
            }
        }
        if (count1 == count2)
        {
            return true;
        }
        return false;
    }
};

发表于 2020-06-15 15:23:09 回复(0)
import java.util.*;
public class Parenthesis {
    public boolean chkParenthesis(String A, int n) {
        if(A.length()==0||n==0)return false;
        Stack<Character> line = new Stack<>();
        int i=0;
        while(i<n){
            if(!line.isEmpty()&&line.peek()=='('&&A.charAt(i)==')')
                line.pop();
            else
                line.push(A.charAt(i));
            i++;
        }
        return line.isEmpty();
    }
}

发表于 2019-06-05 20:59:19 回复(0)
//栈的典型应用

import java.util.*;
public class Parenthesis {
    public boolean chkParenthesis(String A, int n) {
        // write code here
        if(n%2!=0)
            return false;
        Stack<Character> stack=new Stack<>();
        for(int i=0;i<A.length();i++){
            if(A.charAt(i)=='('){
                stack.push(A.charAt(i));
                continue;
            }
            if((A.charAt(i)>='a' && A.charAt(i)<='z') || (A.charAt(i)>='A' && A.charAt(i)<='Z'))
                return false;
            if(A.charAt(i)==')' && !stack.isEmpty() && stack.peek()=='(')
                stack.pop();
            else
                return false;
        }
        return true;
    }
}
 
发表于 2019-05-26 23:47:43 回复(0)
class Parenthesis {
public:
    bool chkParenthesis(string A, int n) {
        int cnt = 0;
        for(int i=0;i<n;i++){
            if(A[i]=='(')
                cnt++;
            else if(A[i]==')'){
                if(cnt<=0)                     return false;                 cnt--;             }else{
                return false;             }         }         return true;             }
};

编辑于 2019-03-02 01:57:07 回复(0)
class Parenthesis {
public:
    bool chkParenthesis(string A, int n) {
        // write code here
        stack<char>s;
        for(int i=0;i<n;i++){
            if(A[i]=='(')s.push(A[i]);
            else if(A[i]==')'){
                if(s.empty())return false;
                s.pop();
            }
            else return false;
        }
        return s.empty();
    }
};
发表于 2018-10-28 19:47:59 回复(0)
import java.util.*;

public class Parenthesis {
    public boolean chkParenthesis(String A, int n) {
        // write code here
        Stack<Character> stack = new Stack<>();
        char[] chars = A.toCharArray();
        for (int i = 0; i < n; i++) {
            if (chars[i] == '(') {
                stack.push(chars[i]);
            } else if (chars[i] == ')') {
                if (stack.size() > 0) {
                    if (stack.peek() == '(') {
                        stack.pop();
                    }
                } else {
                    return false;
                }
            } else {
                return false;
            }
        }
        return stack.size() == 0;
    }
}
使用栈,出栈入栈规则如下:
  1. 遇到左括号'(',压入栈;
  2. 遇到右括号')',需要根据栈的情况判断:若栈为空或栈顶元素不是左括号'(',则返回false;否则将栈顶元素弹出;
  3. 遇到其他符号直接返回
  4. 遍历至最后,若最终栈为空,返回true,否则返回false

发表于 2018-05-17 14:22:35 回复(0)
public class Parenthesis {
    public boolean chkParenthesis(String A, int n) {
        // write code here
        if(n%2!=0){
return false;
}
if(A.charAt(0)!='('||A.charAt(n-1)!=')'){
return false;
}
for(int i=0;i<n;i++){
//System.out.println(A.charAt(i));
if(A.charAt(i)!='('&&A.charAt(i)!=')'){
return false;
}
}
return true;
    }
}
发表于 2017-05-02 18:15:30 回复(1)
一看到括号的匹配就想到了栈。想法很简单,就是遍历字符串,遇到')'时就入栈,遇到'('时就出栈
最后判断栈是否是空值,如果空,则返回true,否则返回false
import java.util.*;

public class Parenthesis {
    public boolean chkParenthesis(String A, int n) {
        // write code here
        Stack stack=new Stack();
        int i=0;
        while(i<n)
        {
            /* 左括号入栈 */
            if(A.charAt(i)=='(')
            {
                stack.push(A.charAt(i));                
            }
            /* 在栈不为空的情况下,匹配到右括号就将栈中的左括号出栈 */
            if(A.charAt(i)==')'&& !stack.isEmpty())
            {                
                stack.pop();
            }
            i++;
            /* 除去一种特殊情况,就是在栈为空时还匹配到右括号时,则直接判断其出错 */
            if(i<n-1 && A.charAt(i)==')' && stack.isEmpty())
            {
                return false;
            }   
        }
        return stack.isEmpty();
    }
}

编辑于 2016-08-30 10:25:35 回复(1)
递归版本: 弹出合法的括号对
# -*- coding:utf-8 -*-

class Parenthesis:
    def chkParenthesis(self, A, n):
        if n <= 0:
            return False

        a = list(A)
        left = a.count('(')
        right = a.count(')')
        if left != right or left + right != n:
            return False
        b = []
        
        def check(b):
            if not b:
                return True
            tmp = b[:]
            idx = 0
            flag = False
            for i, j in zip(tmp, tmp[1:]):
                if i == '(' and j == ')':
                    flag = True
                    b[idx] = ''
                    b[idx + 1] = ''
                idx += 1
            if flag == False:
                return False
            else:
                b = [i for i in b if i != '']
                return check(b)
        
        return check(b) 
非递归版本:使用栈,相当简单清晰
# -*- coding:utf-8 -*-

class Parenthesis:
    def chkParenthesis(self, A, n):
        a = list(A)
        
        stack = []
        for i in a:
            if i == '(':
                stack.append(i)
            elif i == ')':
                if not stack:
                    return False
                else:
                    stack.pop()
            else:
                return False
        
        return True

发表于 2016-08-05 11:41:03 回复(1)
public class Parenthesis {
    public boolean chkParenthesis(String A, int n) {
        // 用于记录左括号的个数
        int count  = 0;
        
        for (int i = 0; i < A.length(); i++) {
            if ('(' == A.charAt(i)) {
                //如果遇到左括号 count 加 1 
                count++;
            } else if(')' == A.charAt(i)) {
                //如果遇到右括号 count 减 1
                count--;
                //如果count < 0, 说明右括号多于左括号,不匹配
                if (count < 0) {
                    return false;
                }
            } else {
                //如果有其他字符,直接返回fasle
                return false;
            }
        }
        
        //检查最终结果
        if (count == 0) {
            return true;
        } else {
            return false;
        }
    }
}

发表于 2016-03-26 11:30:17 回复(1)
根据ASCII码判断
public boolean chkParenthesis(String A, int n) {
        // write code here
        if(n<2){
            return false;
        }
        int left = 0;
        int right = 0;
        for(int i=0;i<n;i++){
            if(A.charAt(i)==40){
                left++;
            }
            if(A.charAt(i)==41){
                right++;
            }
            if(A.charAt(i)!=40&&A.charAt(i)!=41){
                return false;
            }
        }
        if(left!=right){
            return false;
        }
        return true;
    }
发表于 2016-01-08 14:56:54 回复(3)

python solution

使用一个栈来做,每当遇到左括号就放到栈里面,每当遇到右括号,先判断栈里面有没有左括号,如果有,弹出一个,如果没有,直接返回false。最终判断这个栈是否为空,如果为空,返回true,否则返回false。


class Parenthesis:
    def chkParenthesis(self, A, n):
        # write code here
        stack=[]
        for i in A:
            if i=="(":
                stack.append("(")
            elif i==")":
                if not stack:return False
                stack.pop()
        return stack==[]
发表于 2017-10-31 16:31:09 回复(0)