“This is the 18th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

How do I validate valid parentheses

A stack is a very simple data structure with only two operations, push and push. Last come out, first come out, that’s the stack structure.

Although the scope of use of the stack is relatively small, but this problem with the stack thinking is the most appropriate.

The implementation process

The left and right sides must be parentheses of the same type, and they must be closed sequentially.

No matter how the three types of parentheses are arranged, as long as they conform to the closing rule, there must be an open parenthesis before a close parenthesis. If it is a regular string of closed parentheses, then no matter how many parentheses are in the middle of any set of closed parentheses, the three forms (),{},[] must be in the middle of the transition, starting with the open parenthesis and ending with the close parenthesis.

If you divide them down the middle, you will find that they are all symmetrical.

We’re going to follow the stack idea, we’re going to push when we see an open parenthesis, we’re going to push when we see a close parenthesis and we’re going to check until we get to zero. This results in a closed parenthesis string that matches the rule.

Here is the complete code:

Line 189-192 checks the length of the string. If the length is less than or equal to 1, or if it is singular, because closing parentheses must be even, then singular length is not consistent with the rule and returns an error.

Line 194-198 defines an array with close parentheses for keys and open parentheses for values. You can find the corresponding open parenthesis based on the close parenthesis.

Lines 200-201 define an array representing the stack structure. $flag indicates the position at the top of the stack, which elements need to be removed at any time. You can also use the count function to calculate the length of the array each time, so that the logic is simple and does not care about the key changes after the element leaves the stack.

Lines 202-214 iterate over the string based on its length.

In line 203-205, we need to stack any left parenthesis we encounter first, since the left parenthesis must appear first. There are three types of open parentheses (,{,[). First increment $flag by one, then place a single character in the array according to $flag.

At line 207-209, we encounter the closing parenthesis. If there is no data in the array $arr when a close parenthesis is encountered, it is not a rule to declare a string, because a close parenthesis must have an open parenthesis.

We then need to determine whether the currently encountered closing bracket can be combined with the bracket at the top of the stack to give the closing bracket. $s[$I]; $s[$I]; $s[$I]; $arr[$flag] = $arr[$flag] = $arr[$flag] If they are consistent, you can continue traversing. If not, the string is not closed. Return an error directly.

At this point, if the judgment is consistent, as stated above, the parentheses appear in the three forms (),{},[].

In line 211-212, by checking that the parentheses can be closed, we need to remove the parentheses at the top of the stack, and next time we need to check whether the parentheses on the next element at the top of the stack are closed. Because an element is removed from the array, the key value $flag needs to be reduced by one.

Line 216, it’s a little bit more confusing to write it like this, but if I were to write it like this, it would make a lot more sense.

if(!empty($arr)) {return false;
}
return true;
Copy the code

If no parentheses are found that do not match the closing rule after iterating through the string, then we need to check whether there are any elements in the array (i.e. the stack). If there are any, we need to check whether there are any closed parentheses, so we return an error. Otherwise returns success, which is a closed parenthesis string that complies with the rule.

The execution result

Some case analysis, why add such code

Lines 207-209 in the figure above can also be written as follows with the $map array mapping parentheses.

if($s[$i] = =') ' && $arr[$flag] != '(') {return false;
}
if($s[$i] = ='] ' && $arr[$flag] != '[') {return false;
}
if($s[$i] = ='} ' && $arr[$flag] != '{') {return false;
}
Copy the code

We also determined that

count($arr) == 0
Copy the code

$arr: $arr: $arr: $arr: $arr: $arr: $arr: $arr: $arr: $arr: $arr: $arr: $arr: $arr: $arr

So that’s a valid parenthesis validation idea.