[day_070425] legal bracket sequence judgment

Legal bracket sequence judgment

Title source

Cattle from ： Legal bracket sequence judgment

Title Description

Given a string A And its length n, Please return one bool The value represents whether it is a legal string of parentheses （ Can only consist of parentheses ）.

Example 1

Input

“(()())”,6

return

true

Example 2

Input

“()a()()”,7

return

false

Example 3

Input

“()(()()”,7

return

false

Thought analysis

• According to the stack, in and out 、 Last in first out feature to save the sequence of parentheses
• Traversal string , When encountering the left parenthesis, perform the stack operation , The right bracket is used to stack , Finally, if the stack is empty, the sequence is legal
• If there are other characters when traversing the string , Or the current character is a right parenthesis but the stack is empty , Description sequence is illegal , Go straight back to false

Code display

class Parenthesis {
    
public:
    bool chkParenthesis(string A, int n) {
    
        stack<char> mystack;
        for (int i = 0; i < n; i++)
        {
    
            if (A[i] == '(')
            {
    
                mystack.push('(');// Push 
            }
            else if (A[i] == ')')
            {
    
                // When the current character is a right parenthesis , First determine whether there are brackets in the stack 
                if (mystack.empty())
                {
    
                    return false;
                }
                mystack.pop();// Out of the stack 
            }
            else
            {
    
                return false;
            }
        }
        if (mystack.empty())
        {
    
            return true;
        }
        return false;
    }
};