logo标签列表

递归算法设计

phpalgorithmrecursion
5

我有一个需求，需要允许我的终端用户输入类似于电子表格的公式。我有一个像这样的数组：

$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

数量和价值键代表引用[id]和数量、价值或成本的公式。

成本是通过将价值和数量相乘得出的。

我正在使用：

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]['Quantity'];

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

我可以获取需要计算的字符串，并使用matheval类来进行求和。
例如：
[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。

但这里有我的问题

我需要解决对表格其他部分（可能是公式，也可能不是）的引用，以填补空白。这超出了我的舒适区，我会感激任何提供启示的建议（或甚至更好的功能性代码），告诉我如何能够实现这一点。

谢谢

1
啊，我明白了。顺便说一下，将这个步骤添加到问题本身中。 - Sergio Tulentsev
"1]Cost = [2]Cost" - 你是不是想说 "[1]Value = [2]Cost"？ - Sergio Tulentsev
1
@tozjerimiah：我的 PHP 等于不存在，但我会用 Ruby 来尝试一下，只是为了好玩。让我们看看效果如何 :) - Sergio Tulentsev
@SergioTulentsev 是的，抱歉我在手机屏幕上打字。 - sidewaysglance
1
如果你成功处理了递归评估，下一个问题就是检测引用循环（例如“a = b; b = c; c = a”）。这也是一个有趣的问题要解决 :) - Sergio Tulentsev
显示剩余5条评论
3个回答
3

您已经知道如何解决这个问题，只是被任务所吓倒了。

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

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编写的）

你的评估可能是正确的。今晚我会坐下来认真琢磨一下。如果有任何问题，我会再回来的。感谢你的建议和信任。 - sidewaysglance
2
如果calcString的大小适中且您不希望替换过于复杂，您可以使用while循环来模拟递归。以下是一个示例，它在修改字符串时输出字符串：
$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);
}

输出：

[6]Quantity*[4]Value
[4]Quantity*[4]Value
[4]Quantity*3
[3]Cost*3
9*7*3
变量：
$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"
       )
);
1

一种危险地易于操作，且能够根据您的情况表现良好的解决方案！

<?php
class solver {
    private
            // The final output array
            $arr_evaled,
            // When a cell gains its final value, the corresponding entry in the following array gets marked as being done!
            $arr_done;

    private $solving_iterations_count;

    public function solver($array) {
        $this->arr_done = array();

        foreach($array as $k => $arr)
            $this->arr_done[$k] = array('Quantity' => false, 'Value' => false);

        // Firstly,expand all of the "[x]Cost"s to "([x]Quantity*[x]Value)"s!
        $this->arr_evaled = array_map(
            function($v){ return preg_replace('#\[(\d*?)\]Cost#', '([$1]Quantity*[$1]Value)', $v); },
            $array
        );

        $this->solving_iterations_count = 0;
        $this->solve();
    }

    private function isDone() {
        foreach($this->arr_done as $a)
            if($a['Quantity'] == false || $a['Value'] == false)
                return false;
        return true;
    }
    private function isCellDone($id, $fieldName) {
        return $this->arr_done[$id][$fieldName];
    }
    private function markCellAsDone($id, $fieldName, $evaluation) {
        $this->arr_done[$id][$fieldName] = true;
        $this->arr_evaled[$id][$fieldName] = $evaluation;
    }
    private function isEvaluable($str) {
        return preg_match('#^[0-9*+-\/\(\)\.]*$#', $str) == 1 || strtolower($str)=='null';
    }
    private function replace($from, $to) {
        foreach($this->arr_evaled as &$arr) {
            $arr['Quantity'] = str_replace($from, $to, $arr['Quantity']);
            $arr['Value'] = str_replace($from, $to, $arr['Value']);
        }
    }

    private function solve() {
        $isSolvable = true; // YOUR TODO: I believe coding this part is also fun!) (e.g: check for "reference cycles")
        if(!$isSolvable) return null;

        while( !$this->isDone() )
        {
            foreach($this->arr_evaled as $arr) {
                foreach(['Quantity', 'Value'] as $fieldName) {
                    if(!$this->isCellDone($arr['id'], $fieldName)) {
                        if($this->isEvaluable($arr[$fieldName])) {
                            $evaluation = eval("return {$arr[$fieldName]};");
                            $this->markCellAsDone($arr['id'], $fieldName, $evaluation);
                            $this->replace("[{$arr['id']}]$fieldName", "$evaluation");
                        }
                    }
                }
            }
            $this->solving_iterations_count++;
        }
        foreach($this->arr_evaled as &$row)
            $row['Cost'] = $row['Quantity'] * $row['Value'];
        return $this->arr_evaled;
    }

    public function print_tabulated() {
        echo "The count of solving iterations: {$this->solving_iterations_count}<br/><br/>";
        echo '<table border="1"><tr><th>id</th><th>Name</th><th>Quantity</th><th>Value</th><th>Cost</th></tr>';
        foreach($this->arr_evaled as $arr)
            echo "<tr><td>{$arr['id']}</td><td>{$arr['Name']}</td><td>{$arr['Quantity']}</td><td>{$arr['Value']}</td><td>{$arr['Cost']}</td></tr>";
        echo '</table>';
    }
}

// Testing
$arr = 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' => 4, 'Name' => 'Sausages',   'Quantity' => '[3]Cost',              'Value' => '3'        ),
    5 => array( 'id' => 5, 'Name' => 'Bamboo',     'Quantity' => '[4]Quantity',          'Value' => '[7]Cost'  ),
    6 => array( 'id' => 6, 'Name' => 'Clams',      'Quantity' => '[4]Quantity',          'Value' => 'NULL'     ),
    7 => array( 'id' => 7, 'Name' => 'Hardcore',   'Quantity' => '[3]Quantity*0.5',      'Value' => '12'       ),
    8 => array( 'id' => 8, 'Name' => 'Beetles',    'Quantity' => '[6]Quantity*[4]Value', 'Value' => '[2]Value' ),
);
echo '<pre>';
(new solver($arr))->print_tabulated();

这是输出内容：

The output of the code in https://dev59.com/mI_ea4cB1Zd3GeqPPIGn#32805259

1
高性能？你有数据支持吗？ :) - Sergio Tulentsev
1
@SergioTulentsev 嗯，实际上，这段代码还没有经过无数次的严格测试！也许“良好可执行性”是更好的替代词 :) - someOne
这很好，但我需要输出包括“成本”字段和结果。您能否修改您的答案，以便最终输出包含此内容？谢谢！ - sidewaysglance
1
@tozjerimiah 答案已更新以反映在上面的评论中宣布的新要求。 - someOne
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接