11

我在徘徊，如果有人擅长 PHP 可以建议如何验证表达式字符串中的括号，如下所示：

    ( 5 * 3 [ 6 ) - 6]

这是错误的表达。我需要一个函数来做到这一点。这是我到目前为止所尝试的：

<?php
function hasMatchedParenthesis($string) {

$counter1 = 0;
$counter2 = 0;

$length = strlen($string);

for ($i = 0;$i < $length; $i++) {
    $char = $string[$i];
    if( $char == '(' ) {
        $counter1 ++;
    } elseif( $char == ')' ) {
        $counter1 --;
    }

        for($j =0;$j < $length; $j++) {
            $char = $string[$j];
            if( $char == '[' ) {
                $counter2 ++;
        } elseif( $char == ']' ) {
                $counter2 --;
        }

        }


    if( $counter1 < 0 || $counter2 < 0) {
        return false;
    }

}

echo 'ok';;

}


hasMatchedParenthesis('[5] * 3 - ( 4 - 7 * [3-6])'); // this is ok!

hasMatchedParenthesis('( 5 * 3 [ 6 ) - 6]'); // this returns as TRUE, but it is not!

?>

请帮我解决“[6]”的验证问题！我不知道该怎么做:(

4

3 回答 3

12

我想到的第一个想法是使用堆栈。PHP 提供了两个函数来将数组视为堆栈：array_push和array_pop. 我们可以使用它们创建一个堆栈0（我们在一个开头(）和1（我们在一个里面[），并检查右括号是否与我们插入的最后一个值匹配：

function hasMatchedParenthesis($string) {
    $len = strlen($string);
    $stack = array;
    for ($i = 0; $i < $len; $i++) {
        switch ($string[$i]) {
            case '(': array_push($stack, 0); break;
            case ')': 
                if (array_pop($stack) !== 0)
                    return false;
            break;
            case '[': array_push($stack, 1); break;
            case ']': 
                if (array_pop($stack) !== 1)
                    return false;
            break;
            default: break;
        }
    }
    return (empty($stack));
}

请注意，您可以将其扩展到任何其他字符对，包括{and }：

case '{': array_push($stack, 2); break;
case '}': 
    if (array_pop($stack) !== 2)
        return false;
break;
于 2013-03-31T10:58:17.647 回答
1

验证此类语法规则的常用方法是使用上下文无关语法- 查看示例，您会发现您正在尝试做的确切示例:-) 您可以通过使用来应用此类语法的规则Mark Ba​​ker 指出的词法分析器。
在您的代码中，您只需要确保左括号的数量与右括号的数量相匹配，这就是缺陷。同样正如我在评论中指出的那样，您的最后一个条件应该是 

if ($counter1 != 0 || $counter2 != 0){
    return false;
}

在您当前的情况下true，当任何计数器为 时将返回>=0。尝试一个简单的 case ，即使它是错误的hasMatchedParenthesis('[5] * 3 - ( 4 - 7 * [3-6');也会返回。true

于 2013-03-31T10:48:56.527 回答
0

我写了以下实现。

function check_brackets_balance($string, $bracket_map = false) {
    $bracket_map = $bracket_map ?: [ '[' => ']', '{' => '}', '(' => ')' ];
    $bracket_map_flipped = array_flip($bracket_map);
    $length = mb_strlen($string);
    $brackets_stack = [];
    for ($i = 0; $i < $length; $i++) {
        $current_char = $string[$i];
        if (isset($bracket_map[$current_char])) {
            $brackets_stack[] = $bracket_map[$current_char];
        } else if (isset($bracket_map_flipped[$current_char])) {
            $expected = array_pop($brackets_stack);
            if (($expected === NULL) || ($current_char != $expected)) {
                return false;
            }
        }
    }
    return empty($brackets_stack);
}

它也使用堆栈，但需要的代码更少，并且为您自己的括号集提供了额外的参数。

check_brackets_balance('[5] * 3 - ( 4 - 7 * [3-6])'); // true
check_brackets_balance('( 5 * 3 [ 6 ) - 6]')); // false
于 2017-06-20T05:38:01.467 回答