Баланс скобок в выражении [закрыт]

26 сентября 2021, 00:00

Закрыт. На этот вопрос невозможно дать объективный ответ. Ответы на него в данный момент не принимаются.

Хотите улучшить этот вопрос? Переформулируйте вопрос так, чтобы на него можно было дать ответ, основанный на фактах и цитатах.

Закрыт 1 год назад.

Улучшить вопрос

Написать функцию, которая на входе принимает строку из скобок, и возвращает true если все открытые скобки закрыты, иначе - false. Возможные варианты скобок: ()[]{}.

Пример:

"(){}[]" => true

"([{}])" => true

"(}" => false

"[(])" => false

"[({})](]" => false

Мною было предложено следующее решение:

<?php
function isBracketsBalanced (string $input) : bool {
  $costs = [
    '[' =>  1, '(' =>  10, '{' =>  100,
    ']' => -1, ')' => -10, '}' => -100
  ];
  $brackets = str_split ($input);
  $opened = [- $costs [end ($brackets)]];
  $balance = 0;
  while (($bracket = array_pop ($brackets)) !== NULL) {
    $cost = $costs [$bracket];
    $balance += $cost;
    if ($cost < 0)
    
      $opened [] = - $cost;
      
    else if ($cost == end ($opened))
    
      array_pop ($opened);
    else
    
      return FALSE;
  }
  return $balance == 0;
}

https://repl.it/repls/SandyPriceyDevices

Резюме проверяющего: задача решена на хорошем, но недостаточно высоком уровне.

Может кто-нибудь объяснить что именно в предложенном мной решении на "недостаточно высоком уровне"?

Answer 1

Вот формально, зачем вообще у вас какой то баланс и эти значения 1,10,100 ? Вам вроде нужен стек, открывающая скобка - добавляете в стек. Закрывающая - смотрите на вершине парная или нет. Если парная то удаляете, иначе вообще выход. Таков алгоритм должен быть? Если да, то при чем тут вообще эти числа?

function checkBraces($input){
    $braces = str_split($input);       
    $map = [']' => '[', ')' => '(', '}' => '{'];
    $closing = array_keys($map);
    $stack = [];
    foreach($braces as $b){
        if(!in_array($b, $closing)){
            $stack[] = $b;
            continue;
        }
        if(end($stack) != $map[$b]) return false;
        array_pop($stack);
    }
    return count($stack)  == 0;
}

еще можно вот так решить :D

function check2($input){
    $repl = str_replace(["}", ")", "]"],["{r", "(r", "[r"], $input);
    $result = preg_replace('/([\[({])(?R)*\1r/', "", $repl);
    return mb_strlen($result) == 0;
}