【每日一题】合法括号序列判断

迈不过友情╰ 2022-12-26 10:14 159阅读 0赞

**题目来源**  
牛客网  
链接：[合法括号序列判断][Link 1]

**题目描述**  
给定一个字符串A和其长度n，请返回一个bool值代表它是否为一个合法的括号串（只能由括号组成）。

测试用例：

> “(()())”,6

> 返回：true

测试用例：

> “()a()()”,7

> 返回：false

测试用例：

> “()(()()”,7

> 返回：f

**解题思路1**  
用栈结构实现，栈中存放左括号，当遇到右括号之后，检查栈中是否有左括号，如果有则出栈，如果没有，则说明不匹配。

**代码展示1**

class Parenthesis
    {
        
    public:
    	bool chkparenthesis(string A, int n)
    	{
        
    		stack<char> sc;
    		for(auto ele : A)
    		{
        
    			switch(ele)
    			{
        
    				case '(':
    					sc.push(ele);
    					break;
    				case ')':
    					{
        
    						if(sc.empty() || sc.top() != '(')
    					        return false;
    					    else
    					    	sc.pop();
    					 }
    					 break;
    			    default:
    				    return false;
    			}
    		}
    		return true;
    	}
    };

**解题思路2**  
用left记录左括号出现次数，right记录右括号出现次数，m记录left-right的值，如果n小于0，说明左右括号未匹配成功。遇到其他字符直接返回false。

**代码展示2**

class Parenthesis
    {
        
    public:
    	bool chkparenthesis(string A, int n)
    	{
        
    		int left = 0,right = 0,m = 0;
    		for(int i = 0;i < A.size();++i)
    		{
        
    			if(A[i] == '(')
    			{
        
    				++left;
    				m = left;
    			}
    			else if(A[i] == ')')
    			{
        
    				++right;
    				m = left - right;
    				if(m < 0)
    					return false;
    			}
    			else
    				return false;
    		}
    		if(m != 0)
    			return false;
    		return true;
    	}
    };

[Link 1]: https://www.nowcoder.com/practice/d8acfa0619814b2d98f12c071aef20d4?tpId=8&&tqId=11039&rp=1&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking