php - 递归(？)算法设计

Question

我需要允许我的最终用户像电子表格一样输入公式。我有一个这样的数组:

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

第一级数组键值始终与该数组中的 id 键值相同。

表格示例如下:

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

Quantity 和 Value 键表示引用 [id] 和 Quantity、Value 或 Cost 的公式。

成本是值(value)和数量的乘积。

我正在使用:

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

它为[1][Quantity] 输出一个数组:

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

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

)

使用类似于以下内容的方式遍历表格: $calcString = $table[1]['数量'];`

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

我可以获得要计算的字符串，并使用数学类进行求和。

例如

[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

基本上表中的变量是指同一个表中的其他[id]key。

但这是我的问题

我需要解决对表格其他部分的引用(它们本身可能是也可能不是公式)以填充空白。这超出了我的舒适范围，如果有任何建议(或更好的功能代码)能为我如何实现这一目标提供启发，我将不胜感激。

谢谢

Answer 1

在内心深处，您已经知道如何解决这个问题，您只是被任务吓倒了。

递归方法是立即扩展引用。例如，

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

一种迭代(非递归)方法是一次扩展一个引用并重复直到字符串中有未解析的引用。

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

通常，我更喜欢迭代解决方案，因为它们不太容易出现堆栈溢出。但是，递归解决方案通常更容易编写。

这是一个快速组合的递归计算器:https://gist.github.com/stulentsev/b270bce4be67bc1a96ae (虽然是用 ruby 写的)