阿狸不是猫

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)

Howie59

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)

Python

华科平凡

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)

Java

lmz9509

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)

ID84848484

//栈的典型应用

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)

C/C++

nbgao

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)

我201810261507240

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)

Java

●﹍佐手〃|

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;
    }
}

使用栈，出栈入栈规则如下：

遇到左括号'('，压入栈；
遇到右括号')'，需要根据栈的情况判断：若栈为空或栈顶元素不是左括号'('，则返回false；否则将栈顶元素弹出；
遇到其他符号直接返回
遍历至最后，若最终栈为空，返回true，否则返回false

发表于 2018-05-17 14:22:35 回复(0)

hhhhhman

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)

Python

Yannyezixin

递归版本：弹出合法的括号对

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

Logic

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)

ajavastudent

根据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)

shizheng

class Parenthesis {
public:
    bool chkParenthesis(string A, int n) {
        int count=0;
        for (int i=0; A[i]; ++i) {
            if(A[i]=='(')
                count++;
            else if(A[i]==')')
                count--;
            else
                return false;
            if(count<0)
                return false;
        }
        return count==0;
    }
};

发表于 2016-04-12 23:09:08 回复(2)

Aurora1

    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

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

程序员耳东

这道题刚开始理解有问题，还以为是（（a））这样的形式才算过

其实是判断合法的括号串，出现了非括号的字符就算错

第二个测试例子有点误导

发表于 2016-05-20 19:45:42 回复(5)

小周好饿

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)

合法括号序列判断

python solution

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

问题信息

热门推荐

通过挑战的用户

相关试题