基于图结构的计算分析和实现

这两天调研了下基于图结构的计算方式，并以图结构的方式实现了简单的算式计算，具体过程如下文。

图结构构成

1. 使用简单的将所有节点通过数组或链表进行管理起来
2. 使用二维数组将节点之间的关系进行管理。
3. 简单实现 BFS及DFS
4. 通过查找依赖关系来构成执行顺序图
   如下图：

数据存储表

其数据结构图如下图：

图结构

因此对于简单图结构来说，通过与节点等数量维度的二维数组能完整的描述图结构的所有关系。

执行图过程

对于计算使用的算式来说，算式中的加减优先级很重要，因此需要通过对优先级进行图的优化，如下为a + b * c 算式的优化过程图：

a + b * c 图优化过程

本文仅对图进行简单介绍及实现，详细请参见代码
上述的基本实现参考 Tanuki(狸)

如下是简单实现的样例代码：

GraphEngine engine = new GraphEngine();
engine.appendField("a", AnyObject.valueOf(2));
engine.appendField("b", AnyObject.valueOf(3));
engine.appendField("c", AnyObject.valueOf(4));
engine.appendField("d", AnyObject.valueOf(5));
engine.dumpFieldList();
String func = "a + b";
System.out.println(String.format("%s = %s", func, engine.exec(func)));
func = "a + b * c";
System.out.println(String.format("%s = %s", func, engine.exec(func)));
func = "( a + b ) * c";
System.out.println(String.format("%s = %s", func, engine.exec(func)));
func = "( ( a + b ) * c ) * d";
System.out.println(String.format("%s = %s", func, engine.exec(func)));