递归（？）的算法设计 [英] Recursive(?) algorithm design
问题描述
我有一个要求，让我的最终用户输入公式很像是preadsheet。我有一个这样的数组：
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"
),
...)
第一级阵列密钥总是相同的值作为该数组中的id键
The first level array key is always the same value as the id key in that array.
一个表格的例子如下：
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
的数量和价值键重新present公式引用[ID]，要么数量，价值或成本。
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.
我使用的：
preg_match_all("/\[(.*?)\]([A-Z]*[a-z]*)/", $string, $matches, PREG_SET_ORDER);
它输出这样一个数组的 [1] [数量] ：
Array
(
[0] => Array
(
[0] => [2]Quantity
[1] => 2
[2] => Quantity
)
[1] => Array
(
[0] => [3]Value
[1] => 3
[2] => Value
)
)
通过迭代使用了类似于表： $ calcString = $表[1] ['数量'];`
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);
}
我可以要计算的字符串，并正在使用matheval类做的总和。
I can get the string to be calculated and am using a matheval class to do the sum.
例如
[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]键在同一个表。
我需要解决的引用表中的其它部分（其可以是或不是本身可以是式），以填空。这是超出了我的安乐窝，我会AP preciate任何建议（甚至更好的功能code），它提供了启示，我怎么可能能够做到这一点。
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.
感谢
推荐答案
一个危险简单，和你的，针对具体情况精心performable解决方案！
A dangerously easy, and your-situation-specific well-performable solution!
<?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();
下面是输出：
这篇关于递归（？）的算法设计的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
