1

在我工作的时候，我发现了一个很好的谜题，它要求创建一个函数来正确匹配 {, (, [ 及其对应的大括号 ], ), }

他们提供的表达式示例如下：

$expressions = array(")(){}","[]({})","([])","{()[]}","([)]");

必须返回的值是：

0
1
1
1
0

他们提供的约束条件是字符串的最大长度为 100，并且数组可以携带至少 50,000 个元素。鉴于这些情况，他们希望该功能在不到 2 秒的时间内解决问题。

我试着写点东西，可以在这里找到（它不完整，因为我觉得整个 if/else 方法太麻烦了——换句话说，解决问题肯定需要 2 秒以上） ：

https://gist.github.com/adibbehjat/6387415

<?php

function check_braces($expressions) {

    for($x = 0; $x < count($expressions); $x++)
    {
        $open = array("{", "[", "(");
        $close = array("}", "]", ")");
        $key = array("{" => "}", "[" => "]", "(" => ")");
        $string = $expressions[$x];
        echo $string."<br>";

        //First item should open a brace, else fail
        if((in_array($string[0], $close)) && (strlen($string) % 2))
        {
            echo 0;
            echo '<br>';  
        }
        else
        {
            $bank_o = array();
            $bank_c = array();
            $element = array();

            for($y = 0; $y < strlen($string); $y++)
            {
                $element = $string[$y];

                if(in_array($element, $open))
                {
                    array_push($bank_o, $element);
                }
                else
                {
                    array_push($bank_c, $element);
                }

                $arraycounter = array_merge($bank_o, $bank_c);

                $y++;

                if(!empty($bank_c) && !empty($bank_o))
                {
                    $num = count($bank_o);
                    if($bank_c[0] == $key[$bank_o[$num - 1]])
                    {
                        array_shift($bank_c);
                        array_pop($bank_o);
                    }
                }
                elseif (empty($bank_c) && empty($bank_o)) {
                    echo 1 . "<br>";
                }
                else
                {

                }

            }
        }
    }
}

//$expressions = array(")(){}","[]({})","([])","{()[]}","([)]");

$expressions = array("([])","([)]");

check_braces($expressions);

?>

我是自学 PHP 的，感觉自己在确定解决此类问题的最佳算法方面缺乏很多技能。并且很想知道还有哪些其他替代方法是可能的。

4

3 回答 3

3 
<?php

function checkMatchingBraces($expression) {
    static $braces = [
        '(' => ')',
        '{' => '}',
        '[' => ']'
    ];
    $stack = [];
    $state = null;  // $state is only used for efficiency,
                    // would need to call end($stack) a lot otherwise

    for ($i = 0, $length = strlen($expression); $i < $length; $i++) {
        $char = $expression[$i];

        if (isset($braces[$char])) {
            // opening brace, pushing onto stack
            $stack[] = $state = $char;
        } else if ($state && $char == $braces[$state]) {
            // matching closing brace to current state, popping stack
            array_pop($stack);
            $state = end($stack);
        } else {
            // non-matching brace
            return false;
        }
    }

    // expecting stack to be reduced back to 0 here, otherwise fail
    return count($stack) == 0;
}

$expressions = array(")(){}","[]({})","([])","{()[]}","([)]");

var_dump(array_map('checkMatchingBraces', $expressions));
于 2013-08-30T08:41:45.620 回答
0 
function validBraces($braces) {
    if (!is_string($braces))
        return 0;

        if (trim($braces, '(){}[]') !== '')
            return 0;

            $pile = array();

            for ($i = 0; $i < strlen($braces); $i++) {
                //App possible Closures
                if ($braces[$i] === ')' || $braces[$i] === ']' || $braces[$i] === '}') {
                    $last = array_pop($pile);
                    if ($braces[$i] === ')' && $last !== '(' || $braces[$i] === '}' && $last !== '{' || $braces[$i] === ']' && $last !== '[')
                        return 0;
                } else
                    $pile[] = $braces[$i];
            }
            return !$pile;
}

从代码审查返回 1 如果为真，如果为假则返回 0

于 2018-08-20T00:59:38.383 回答
0

功能 #1 - 如果您不喜欢正则表达式（演示）

function is_valid($string) {
    do {
        $string = str_replace(['()', '{}', '[]'], '', $string, $count);
    } while ($count);
    return (int)!$string;
}

功能 #2 - 如果递归模式的想法吓到你（演示）

function is_valid($string) {
    while (($string = preg_replace('~(?:\(\)|\{}|\[])+~', '', $string, -1, $count)) && $count);
    return (int)!$string;
}

功能 #3 - Casimir et Hippolyte非常聪明的递归模式（演示）

function is_valid($string) {
    return preg_match('~(\((?1)*+\)|\[(?1)*+]|{(?1)*+})*\z~A', $string);
}

以下是一些示例输入和迭代函数调用：

$expressions = array(")(){}", "[]({})", "([])", "{()[]}", "([)]", "{()[]}{()[]}{()[]}{()[]}{()[]}");
foreach ($expressions as $expression) {
    echo "$expression is " , is_valid($expression) , "\n";
}

全部输出：

)(){} is 0
[]({}) is 1
([]) is 1
{()[]} is 1
([)] is 0
{()[]}{()[]}{()[]}{()[]}{()[]} is 1
于 2018-11-05T14:39:09.297 回答