Recursive(?) algorithm design

Question

I have a requirement to allow my end users to input formula much like a spreadsheet. I have an array like this:

$table = array(
    1=>array(
            "id"=>1,
            "Name"=>"Regulating",
            "Quantity"=>"[2]Quantity+[3]Value",
            "Value"=>"[2]Cost"
        ),
...)

The first level array key is always the same value as the id key in that array.

A tabulated example follows:

id  Name        Quantity                Value
1   Regulating  [2]Quantity+[3]Value    [2]Cost
2   Kerbs       3                       6
3   Bricks      9                       7
4   Sausages    [3]Cost                 3
5   Bamboo      [4]Quantity             [7]Cost
6   Clams       [4]Quantity             NULL
7   Hardcore    [3]Quantity*0.5         12
8   Beetles     [6]Quantity*[4]Value    [2]Value

The Quantity and Value keys represent formula which reference the [id] and either Quantity, Value or Cost.

Cost is derived by multiplying the Value and Quantity.

I am using:

preg_match_all("/\[(.*?)\]([A-Z]*[a-z]*)/", $string, $matches, PREG_SET_ORDER);

which outputs an array like so for[1][Quantity]:

Array
(
    [0] => Array
        (
            [0] => [2]Quantity
            [1] => 2
            [2] => Quantity
        )

    [1] => Array
        (
            [0] => [3]Value
            [1] => 3
            [2] => Value
        )

)

Iterating through the table using something similar to: $calcString = $table[1]['Quantity'];`

foreach ($matches as $match) {
    $calcString = str_replace($match[0], $table[$match[1]][$match[2]], $calcString);
}

I can get the string to be calculated and am using a matheval class to do the sum.

For example

[1]Quantity = [2]Quantity + [3]Value
[2]Quantity = 3
[3]Value = 7 // [1]Quantity = 3 + 7 = 10

[1]Value = [2]Cost
[2]Cost = [2]Quantity * [2]Value // 3 * 6 = 18

Basically the variables in the table refer to other [id]key in the same table.

But here is my issue

I need to resolve references to other parts of the table (which may or may not themselves be formula) to fill in the blanks. This is outside my comfort zone and I would appreciate any advice (or even better functional code) which provides enlightenment on how I might be able to achieve this.

Thanks

Answer 1

Deep down, you already know how to solve this, you're just intimidated by the task.

A recursive approach would be to expand references instantly. For example,

expand('[1]Value') # returns '[2]Cost'
  expand('[2]Cost') # returns '[2]Quantity * [2]Value'
    expand('[2]Quantity') # returns 3
    expand('[2]Value') # returns 6
    eval('3 * 6')
    # returns 18
  # returns 18
# returns 18

An iterative (non-recursive) approach is to expand one reference at a time and repeat until there are unresolved references in the string.

expand('[1]Value') // returns '[2]Cost'
expand('[2]Cost')  // returns '[2]Quantity + [2]Value'
expand('[2]Quantity + [2]Value') // returns 3 for [2]Quantity
expand('3 * [2]Value')  // returns 6 for [2]Value
eval('3 * 6') 
# returns 18

Normally, I prefer iterative solutions, because they're much less prone to stack overflows. However, recursive solutions are usually easier to write.

Here's a quickly slapped-together recursive evaluator: https://gist.github.com/stulentsev/b270bce4be67bc1a96ae (written in ruby, though)

Answer 2

If calcString's are reasonably sized and you don't expect replacements to get too elaborate, you could use a while loop to simulate the recursion. Here's an example that outputs the string along the way as it is being modified:

$calcString = $table[8]['Quantity'];

preg_match_all("/\[(.*?)\]([A-Z]*[a-z]*)/", $calcString, $matches, PREG_SET_ORDER);

print_r($calcString . "\n");

while (!empty($matches)){
  foreach ($matches as $match) {
    preg_match_all("/\[(.*?)\](Cost)/", $match[0], $matchCost, PREG_SET_ORDER);

    if (!empty($matchCost)){
      $cost = $table[$matchCost[0][1]]['Quantity'] . "*" . $table[$matchCost[0][1]]['Value'];
      $calcString = str_replace($match[0], $cost, $calcString);
    } else {
      $calcString = str_replace($match[0], $table[$match[1]][$match[2]], $calcString);
    }

    print_r($calcString . "\n");

  }
  preg_match_all("/\[(.*?)\]([A-Z]*[a-z]*)/", $calcString, $matches, PREG_SET_ORDER);
}

Output:

[6]Quantity*[4]Value
[4]Quantity*[4]Value
[4]Quantity*3
[3]Cost*3
9*7*3

The table variable:

$table = array(
  1 => array(
         "id" => 1,
         "Name" => "Regulating",
         "Quantity" => "[2]Quantity+[3]Value",
         "Value" => "[2]Cost"
       ),
  2 => array(
         "id" => 2,
         "Name" => "Kerbs",
         "Quantity" => 3,
         "Value" => 6
       ),
  3 => array(
         "id" => 3,
         "Name"=>"Bricks",
         "Quantity"=> 9,
         "Value"=> 7
       ),
  4 => array(
         "id" => 2,
         "Name" => "Sausages",
         "Quantity" => "[3]Cost",
         "Value" => 3
       ),
  5 => array(
         "id" => 2,
         "Name" => "Bamboo",
         "Quantity" => "[4]Quantity",
         "Value" => "[7]Cost"
       ),
  6 => array(
         "id" => 2,
         "Name" => "Clams",
         "Quantity" => "[4]Quantity",
         "Value" => NULL
       ),
  7 => array(
         "id" => 2,
         "Name" => "Hardcore",
         "Quantity" => "[3]Quantity*0.5",
         "Value" => 12
       ),
  8 => array(
         "id" => 2,
         "Name" => "Beetles",
         "Quantity" => "[6]Quantity*[4]Value",
         "Value" => "[2]Value"
       )
);