如何检查括号是否平衡

Question

>编写一个名为 validBraces 的函数，该函数采用一串大括号，并确定大括号的顺序是否有效。 如果字符串有效，则大括号应返回 true，如果字符串无效，则返回 false。

所有输入字符串都将是非空的，并且仅由左括号(、右括号)、左括号[、]的右括号、左大括号{和闭大括号}组成。

什么被认为是有效的？

如果所有大括号都与正确的大括号匹配，则认为一串大括号有效。例如：

(){}[]和([{}])将被视为有效，而(}、[(])和[({})](]将被视为无效。

Specification
validBraces(braces)

检查大括号顺序是否有效

参数
大括号：字符串 - 大括号顺序的字符串表示形式

返回值
布尔值 - 如果大括号顺序有效，则返回 true

例子：

    Input   Output
validBraces( "(){}[]" )     true
validBraces( "(}" )         false
validBraces( "[(])" )       false
validBraces( "([{}])" )     true

Answer 1

这是一个非常简单的任务，你可以使用堆栈(即数组/列表(。然后，逐个迭代输入字符串字符，一旦检测到左括号((、<、{等(，您将该括号推到堆栈上(或附加到数组中，无关紧要(。当你遇到右括号()、>、}等(时，你会从堆栈中弹出最后一个元素。然后，您检查括号类型是否匹配，因此当您有>时，您应该从堆栈中弹出<，否则您将停止抱怨不匹配的括号(或其他什么(的进程。一旦你完成了迭代而没有任何错误，你的堆栈应该是空的。

<?php
declare(strict_types=1);
function validateBrackets(string $str): string {
    $map = [
        '(' => ')',
        '<' => '>',
        '{' => '}',
        '[' => ']',
    ];
    $stack = new SplStack();
    for($i = 0; $i < strlen($str); $i++) {
        if(array_key_exists($str[$i], $map)) {
            // Push both the bracket and its index into the stack
            $stack->push([$str[$i], $i]);
        } elseif(in_array($str[$i], $map)) {
            if($stack->isEmpty() || $map[$stack->top()[0]] != $str[$i]) {
                $expected = !$stack->isEmpty() ? $map[$stack->top()[0]] : '';
                return $expected !== ''
                    ? "Expecting '{$expected}' at pos. {$i}, found '{$str[$i]}'"
                    : "Unpaired bracket '{$str[$i]}' at pos. {$i}";
            }
            $stack->pop();
        }
    }
    // If the stack is not empty at the end, return the
    // first unpaired opening bracket and its position
    if (!$stack->isEmpty()) {
        $unpaired = $stack->top();
        return "Unpaired bracket '{$unpaired[0]}' at pos. {$unpaired[1]}";
    }
    return "OK";
}

和测试用例：

$tests = [
    "",
    "(<>)",
    "(<)",
    "<<",
    "<>{}()",
    "<>()}",
];
foreach($tests as $testStr) {
    printf("%-10s: %s" . PHP_EOL, $testStr, validateBrackets($testStr));
}

将输出

          : OK
(<>)      : OK
(<)       : Expecting '>' at pos. 2, found ')'
<<        : Unpaired bracket '<' at pos. 1
<>{}()    : OK
<>()}     : Unpaired bracket '}' at 4

Answer 2

使一个变量递增"("的数量，然后从该变量减少 -= 最后的每个"("，如果该变量 = 0，那么是的，括号是平衡的。对不同类型的支架重复相同的操作。