PHP 括号配对判断及修正

 1 <?php
 2     #判断输入的括号序列是否合法
 3     #解决思路，如果在某一段出现了右括号数比左括号数大，则非法,否则到最后判断左括号和右括号是否相等即可
 4     define("LEFT", "(");
 5     define("RIGHT", ")");
 6 
 7     function validate($seq) {
 8         $len = strlen($seq);
 9         $left = 0;
10         $right = 0;
11 
12         for ($i = 0; $i < $len; $i++) {
13             if ($seq[$i] == LEFT) {
14                 $left++;
15             }
16             if ($seq[$i] == RIGHT) {
17                 $right++;
18             }
19 
20             #判断这一段是否合法
21             if($left < $right) {
22                 #左括号小于右括号，不合法
23                 return false;
24             }
25         }
26 
27         if ($left == $right) {
28             return true;
29         } else {
30             #排除左括号比右括号多的情况，例如"((())"
31             return false;
32         }
33     }
34 
35     #如果序列括号确实，统计出所差的括号最小数目
36     #解题思路，先将序列能配对的括号全都配对，剩下的不能配对的左右括号数就是最小需要的括号数
37     #这个方法也可以代替上面的方法用来判断序列是否合法，如果序列合法，返回0，不过效率第一点
38     function complete($seq) {
39         $seq = str_split($seq);        
40         $count = 0;
41 
42         $loop = true;
43 
44         #先把能配对的括号全部配对完毕
45         while ($loop) {
46             $loop = false;
47             $left = 0;
48             $right = 0;
49             for ($i = 0; $i < count($seq); $i++) {
50                 if ($seq[$i] == LEFT) {
51                     $left++;
52                 }
53                 if ($seq[$i] == RIGHT) {
54                     $right++;
55                 }
56 
57                 #配对一对括号
58                 if (isset($seq[$i - 1]) && $seq[$i - 1] == LEFT && $seq[$i] == RIGHT) {
59                     #如果还能够配对括号，则需要继续循环
60                     $loop = true;
61                     $left--;
62                     $right--;
63                     unset($seq[$i - 1]);
64                     unset($seq[$i]);
65                 }
66             }
67             #重置数组索引
68             $seq = array_values($seq);
69         }
70 
71         #剩下的肯定是不能配对的，将左右括号相加
72         #最后统计一次左右括号差值
73         $count += $left + $right;
74 
75         return $count;
76     }
77 
78     $seq = "(()))(()))";
79     $t = validate($seq);
80     $t2 = complete($seq);
81     var_dump($t, $t2);
82 ?>
更多相关文章

随机推荐
