921. Minimum additions to make parentheses valid

Address ：

Power button https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid/

subject ：

Given a by  '('  and  ')'  A string of parentheses S, We need to add at least parentheses （ '('  or  ')', Can be anywhere ）, To make the resulting parenthesis string valid .

In form , Only meet one of the following , Bracket strings are valid ：

It's an empty string , perhaps
It can be written as  AB （A  And  B  Connect ）, among  A and  B  Are valid strings , perhaps
It can be written  (A), among  A  Is a valid string .
Given a bracket string , Returns the minimum number of parentheses that must be added to make the result string valid .

Example 1：

Input ："())" Output ：1

Example 2：

Input ："(((" Output ：3

Example 3：

Input ："()" Output ：0

Example 4：

Input ："()))((" Output ：4

Tips ：

S.length <= 1000 S Contains only  '(' and  ')'  character .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas ：

The given string has only Left parenthesis , Right bracket , If the quantity matches, it doesn't mean the expected result

such as ：)))(((

Because I met Right bracket

         If there is no left parenthesis in front , You must add left parentheses to match

        If there is an open parenthesis in front , Then subtract one from the number of left parentheses

Meet the left bracket , We need the following characters to see if there is , So count the next number

Finally back to Left parenthesis , Right bracket （ We use it to calculate the new quantity ） The sum of

Method 1 、 Traversal Statistics

int minAddToMakeValid(char * s){
	int lnum = 0, rnum = 0;
	
	int i = 0;
	while(s[i])
	{
		if(s[i] == '(')
			lnum++;
		else
		{
			if(lnum > 0)
			{
				lnum--;
			}
			else
				rnum++;
		}
			
		i++;
	}
	
	return lnum + rnum;
}

See more brush notes