Home

Algorithmic Advent: 24 – Value object stack parser (PHP)

Published on 24 Dec 2010. Tagged with php, algorithmicadvent.

<?php

/**
 * A simple value object (VO)
 *
 */
class MyVO
{
    // Section title
    public $title;

    // Array of key->value mappings
    public $data;
}

/**
 * Simple tree structure to hold arbitrary data
 *
 */
class TreeNode
{
    protected $_data;
    protected $_children;

    public function __construct()
    {
        $this->_children = array();
        $this->_data = array();
    }

    public function addChild(TreeNode $child)
    {
        $this->_children[] = $child;
    }

    public function getChildren()
    {
        return $this->_children;
    }

    public function setValue($key, $value)
    {
        $this->_data[$key] = $value;
    }

    public function getValue($key)
    {
        return (isset($this->_data[$key]) ? $this->_data[$key] : null);
    }
}

/**
 * Standard PHP doesn't seem to contain a peek function for arrays
 *
 * @param array $array
 * @return mixed Last element from the array
 */
function array_peek(array &$array)
{
    $o = array_pop($array);
    array_push($array, $o);
    return $o;
}

/**
 * Creates a tree structure from file content
 *
 * @param string $file File to parse
 * @return TreeNode Root element of created tree
 */
function parseFileIntoTree($file)
{
    $lines = file($file);
    $root = new TreeNode();

    // Stack of TreeNode instances
    $stack = array();

    array_push($stack, $root);

    foreach ($lines as $line) {
        $line = trim($line);

        // Skip empty lines
        if ($line == '') {
            continue;
        }

        switch (substr($line, 0, 1)) {
            case '{':
                // Functionality is implemented in default case; ignore
                break;
            case '}':
                // Pop stack
                array_pop($stack);
                break;
            case '"':
                // Add new entry to last section on stack
                $node = array_peek($stack);
                $vo = $node->getValue('data');
                $parts = explode(' ', $line);
                $parts[0] = substr($parts[0], 1, strlen($parts[0]) - 2);
                $parts[1] = substr($parts[1], 1, strlen($parts[1]) - 2);
                $vo->data[$parts[0]] = $parts[1];
                break;
            default:
                // Initialize new section
                $vo = new MyVO();
                $vo->title = $line;
                $node = new TreeNode();
                $node->setValue('data', $vo);

                // Add new section to tree structure
                $parent = array_peek($stack);
                $parent->addChild($node);

                // Push new section on stack
                array_push($stack, $node);
        }
    }

    return $root;
}

/**
 * Displays the content of a tree structure
 *
 * @param TreeNode $node Root element
 * @param int $depth Recursion depth
 */
function showRec(TreeNode $node, $depth = 0)
{
    foreach ($node->getChildren() as $child) {
        $vo = $child->getValue('data');
        echo str_repeat('    ', $depth) . $vo->title . "\n";

        if ($vo->data != null) {
            foreach ($vo->data as $key => $value) {
                echo str_repeat('    ', $depth) . '  ' . $key . ' => ' . $value . "\n";
            }
        }

        showRec($child, $depth + 1);
    }
}

$root = parseFileIntoTree('input.txt');

echo '<pre>';
showRec($root);
echo '</pre>';

Example input:

Text1
{
   Colours
   {
     "1" "red"
     "2" "yellow"
     "3" "green"
   }
   
   Animals
   {
      "6" "Cat"
      "3" "Dog"
   }

}

Output:

Text1
    Colours
      1 => red
      2 => yellow
      3 => green
    Animals
      6 => Cat
      3 => Dog