各位PHP朋友请求一个PHP的算法

飘雪公子
  • 148

数字N代表生产括号的对数,请你设计一个函数?用于能够生产所有可能的并且有效括号组合!
示例1:
输入: N=3
输出:["((()))","(()())","(())()","()(())","()()()"]

示例2:
输入: N=2
输出:["(())","()()"]

示例3:
输入: N=1
输出:["()"]

回复
阅读 673
1 个回答
✓ 已被采纳

其实很简单,解题思路就是用数据结构---栈,去判断括号是不是合法。

(入栈,)出栈,如果合法,最后栈刚好出完了,不会有剩余。

<?php

function generate($n)
{
    $bit = $n * 2;
    $maxData = pow(2, $bit) - 1;
    
    for ($i=0;$i<$maxData; $i++) {
        $bin = decbin($i);
        $bin = str_pad($bin, $bit, 0, STR_PAD_LEFT);
        $arr = [];
        
        $length = strlen($bin);
        for ($j=0;$j<$length;$j++) {
            if ($bin[$j] == '0') {
                array_push($arr, 1);
            } else {
                if (is_null(array_pop($arr))) {
                    continue 2;
                }
            }
        }
        
        if (count($arr) > 0) {
            continue;
        }
        
        echo str_replace(['0', '1'], ['(', ')'], $bin) . PHP_EOL;
    }
}

generate($argv[1]);

在终端命令输入。

 php test.php 3
宣传栏