<?php
$input = 'RA(B(CCC)B(CC))PA(BB(C))D';
abstract class Component
{
public $letter;
public function __construct($letter)
{
$this->letter = $letter;
}
public function dump($level = 0)
{
echo str_repeat(" ", $level).$this->letter."\n";
}
}
class Leaf extends Component {}
class Node extends Component
{
/** @var Component[] */
private $items = [];
private static function findComponentsFromInput($input)
{
$numOpenBrackets = false;
$numClosedBrackets = false;
$trimPositions = [];
$lastTrimPosition = 0;
for ($currentCharNumber = 0, $strLen = strlen($input); $currentCharNumber < $strLen; $currentCharNumber++) {
if ($input{$currentCharNumber} == '(') {
$numOpenBrackets = (int)$numOpenBrackets + 1;
} elseif ($input{$currentCharNumber} == ')') {
$numClosedBrackets = (int)$numClosedBrackets + 1;
}
$isLeaf = $numOpenBrackets === false && $numClosedBrackets === false && (!isset($input{$currentCharNumber + 1}) || $input{$currentCharNumber + 1} != '(');
if ($isLeaf) {
$trimPositions[] = [
"type" => 'leaf',
"start_trim" => $lastTrimPosition,
"trim_length" => $currentCharNumber - $lastTrimPosition + 1
];
$lastTrimPosition = $currentCharNumber + 1;
}
$isNode = is_int($numOpenBrackets) && is_int($numClosedBrackets) && $numOpenBrackets - $numClosedBrackets == 0;
if ($isNode) {
$numOpenBrackets = false;
$numClosedBrackets = false;
$trimPositions[] = [
"type" => "node",
"start_trim" => $lastTrimPosition,
"trim_length" => $currentCharNumber - $lastTrimPosition + 1
];
$lastTrimPosition = $currentCharNumber + 1;
}
}
$resultComponents = [];
foreach ($trimPositions as $trimPosition) {
$resultComponents[] = [
"type" => $trimPosition["type"],
"data" => substr($input, $trimPosition["start_trim"], $trimPosition["trim_length"])
];
}
return $resultComponents;
}
public function createComponentsFromInput($dataString)
{
$components = self::findComponentsFromInput($dataString);
foreach($components as $component) {
if($component['type'] == 'leaf') {
$this->addItem(new Leaf($component['data']));
} elseif($component['type'] == 'node') {
preg_match('~(\w)*\((.+)\)~', $component['data'], $matches);
if(!isset($matches[1]) || !isset($matches[2])) {
echo "Wrong input format";
exit;
}
$newNode = new Node($matches[1]);
$newNode->createComponentsFromInput($matches[2]);
$this->addItem($newNode);
}
}
return $this;
}
public function addItem(Component $item)
{
$this->items[] = $item;
}
public function dump($level = 0)
{
if($this->letter == 'root') {
$newLevel = $level;
} else {
parent::dump($level);
$newLevel = $level + 1;
}
foreach($this->items as $item) {
$item->dump($newLevel);
}
return $this;
}
}
$root = new Node("root");
$root->createComponentsFromInput($input)->dump();
preferences:
57.03 ms | 402 KiB | 5 Q