Блог

Я наткнулся Decode string problem на то, что дается закодированная строка s, расшифруйте ее с помощью правила:
N[encoded] => encoded*N .

Примеры:

 $input = "4[abc]";
// output: abcabcabcabc

$input = "ac3[ab]d";
// output: acabababd

$input = "a2[b3[cd]]";
// output: abcdcdcdbcdcdcd
 

Я попытался решить эту проблему, используя манипуляцию строками с условиями if, она работает только для двух входов, однако в конце концов она завершается неудачей, когда данный вход содержит несколько закодированных строк.

 $output = '';
$arr = str_split($input);
for ($i=0; $i < count($arr); $i  ) { 
    $char = $arr[$i];//current character
    if($char == '['){
        $closed = strpos($input, ']');
        $len = $closed - ($i 1);
        $output .= str_repeat(substr($input, $i 1, $len), $prev);
        $i = strpos($input, ']');
    }elseif(ctype_digit($char)){
        $prev = $char;
    }else{
        $output .= $char;
    }
}
echo $output;
 

Есть ли какие-либо способы ее решения с использованием того или иного подхода. Или это можно решить только с помощью стека?
Спасибо за любую идею, которая может помочь решить эту проблему!

Чтобы решить вложенный [], вы должны расшифровать его изнутри. Решение использует preg_replace_callback до тех пор, пока не останется ничего, что можно было бы заменить.

 function fkdecode($str){
  while(true){
  $newStr = preg_replace_callback('~(d )[([^[]] )]~',
    function($m){
      return str_repeat($m[2],(int)$m[1]);
    },
    $str);
   if($newStr == $str) break;
   $str = $newStr;
  }
  return $str;
}

//test
$inputs = ["4[abc]", // output: abcabcabcabc
 "ac3[ab]d", // output: acabababd
 "a2[b3[cd]]", // output: abcdcdcdbcdcdcd
];

foreach($inputs as $input){
  echo $input.' := '. fkdecode($input)."<br>n";
}
 

Выход:

 4[abc] := abcabcabcabc
ac3[ab]d := acabababd
a2[b3[cd]] := abcdcdcdbcdcdcd
 

Используйте strpos() со смещением ( $i в вашем случае), указанным для декодирования нескольких закодированных строк.

Вы могли бы использовать strlen вместо count. Это делается для того, чтобы избежать ошибки преобразования массива в строку. Кроме того, вы должны принять во внимание случай, когда N > 9.

 $output = '';

for ($i = 0; $i < strlen($input); $i  ) { 
    $char = $input[$i];//current character
    if($char == '['){
        $closed = strpos($input, ']', $i);
        $len = $closed - ($i 1);
        $output .= str_repeat(substr($input, $i 1, $len), $prev);
        $i = strpos($input, ']', $i);
    }elseif(ctype_digit($char)){
        $end = strpos($input, '[', $i);
        $len = $end - $i;
        $prev = substr($input, $i, $len);
        $i = strpos($input, '[', $i) - 1;
    }else{
        $output .= $char;
    }
}

echo $output;
?>
 

Кстати, это не решает проблему вложенности [] . Вы могли бы использовать стек, чтобы решить эту проблему. Подсказка: Проверьте, есть ли [ «до $closed «. Или используйте этот подход, не связанный с O(n).