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 に答える