Visio-公式配置--二叉树

:

Author:Wilson e-Mail:[email protected] QQ:106365089 QQ http://wilsonwong88.cublog.cn http://wilsonsoft.taobao.com

:15267957

自动义公式方案简介：本方案主要利用二叉树设计自定义公式运算，其运算可为常用的数学公式、逻辑运 算和自定义函数，每一个公式的定义同时可以作为其他自定义公式的引用，本方案可用在KPI考核、工程 计算等方面，可以一个相对独立辅助工具实现，并可为其他系统提供编程接口。 问题需求： 客户通过工具构造任意复杂的计算公式，计算公式中的变量取自预先定义的公式表。公式表通过唯一性ID检索到所对应的 公式表达式。表达式可以为常量，或者另一个公式，或者函数调用格式。 公式计算如果成功，则返回计算的数值结果（如果结果为布尔型，可取以下值：true,false,0,非0数字），如果计算出错 则返回“err:错误描述”。 计算公式包含条件判断式类型：如 IF(条件，真值表达式，假值表达式). 解决方案： 二叉树和公式的对应关系如图所示，通过遍历二叉树可得到公式的表达式或计算公式的值。 二叉树是改造过的，除了左右两个结点外，还有一个结点用于IF表达式时的条件指针，条件指针指向另一个公式表达式。 二叉树结点分为两大类，一类是运算符，另一类为表达式。运算符分为两类，一类是算术运算符（+,-,*,/,>,>=,,>=,

2、删除一个结点 3、编辑一个结点 4、从公式生成二叉树 5、从二叉树生成公式 6、判断二叉树公式合法性 7、展开子树 8、隐蔽子树 9、移动二叉树 10、二叉树自动排序 11、计算公式 三、字典管理 1、添加字段 2、修改字段 3、删除字段 四、公式管理 1、添加公式 2、修改公式 3、删除公式

F=((F1+F2)*F3)-IF((((F1+F2)>F3) and (F5>F6)),F8,F9)

pHead * + F1 F2 F3 F8 Ne w F1 IF F9 + F2 > F3 F5 and > F6

Key----数据源ID 读取记录字段值（表名，关键字字段名，关键字字段值，值字段名） PKey---父节点 ReadRecord(TableName,FieldKeyName,FieldKeyVal,FieldValName) tag---标志位,可以作为分类方法的标识 字段值求和（表名，关键字字段名，关键字字段值，值字段名） Note--公式描述 SumRecords(TableName,FieldKeyName,FieldKeyVal,FieldValName) Val---值 字段值求平均值（表名，关键字字段名，关键字字段值，值字段名） 说明：公式表用来存放公式定义，Id唯一性标识公式定义，一 AvgRecords(TableName,FieldKeyName,FieldKeyVal,FieldValName) 个公式可以作为另一个公式定义的调用参数。二叉树叶子结点 Sql语句执行（Sql） Key。 ExecuteSql(Sql) ------------------------------------------------------Key PKey tag Note Val ------------------------------------------------------- 读取记录字段值（表名，关键字字段名，关键字字段值，值字段名） F1 0 -1 “” 2 DSTReadRecord(TableName,FieldKeyName,FieldKeyVal,FieldValNam F2 0 1 “” F1+3 e) F3 F1 1 “” F2+F1 字段值求和（表名，关键字字段名，关键字字段值，值字段名） F4 0 1 “” (F3*F1)-F2 DSTSumRecords(TableName,FieldKeyName,FieldKeyVal,FieldValNam F5 0 -1 “” ReadRecord(Table,”ID”,”D1",”Val”) e) F6 0 -1 “” SumRecords(Table,”PID”,”0",”Val”) 字段值求平均值（表名，关键字字段名，关键字字段值，值字段名） F7 0 -1 “” AvgRecords(Table,”PID”,”0",”Val”) DSTAvgRecords(TableName,FieldKeyName,FieldKeyVal,FieldValNam F8 0 -1 “” ExecuteSql(“select Val from Table e) where ID=’D1'”) ID----数据源ID F9 0 -1 “” IF(((F4>F5) and (F5,>=,D3) and (D5>D6)),D8,D9) tag ; //结点标志： // 1-算术符号,如+,-,*,/,>,>=, > }SNodeData ; 二叉树： D1 D2 Ne + D3 D5 D6 struct tagNode{ w tagNode *left ; //左指针 D1 D2 tagNode *right ; //右指针 tagNode *parent ; //父指针 tagNode *condition ; //条件指针，如果data.tag=2,则条件指针忽略 tagNodeData data ; //数据结构 }Snode; 公比为X（前提X不为0，为0这题就没什么意义了） ID-------------流水号 讨论公比的取值情况 TableName -----数据表名称; FieldKeyName---关键字字段名 （1）若X＝1，原式＝1＊999＝999 FieldValName---值字段名称 （2）若X不＝1，利用等比数列求和公式 Note-----------说明 S＝a1*(1-q^n)/(1-q) 可得 和为 S=[(x^2)*(1-x)^999]/(1-x) 说明： -------------------------------------------------------------ID TableName FieldKeyName FieldValName Note 二叉树头结点数据结构 -------------------------------------------------------------- struct tagTreeHead{ 1 Table ID Val int ForestID ; //森林ID

char *FormulaKey ; //公式表达式ID STreeNode *TreeRoot;//二叉树根结点 bool Display ; //显示状态（true:显示） }STreeHead ; //森林线性表 Vector vecForest ;

结点数据： struct tagNodeData{ KIndex ; //结点序号，唯一性标示结点 Key ; //关键字，叶子结点或扩展结点取值源数据表的ID，否则为空 Val ; //结点值， 如果结点为叶子结点，则取值Key对应的源数据表的Val 如果结点为非叶子结点，则取值于以下运算符之一： +,-,*,/,>,>=,,>=,

ID ----------森林ID FormulaKey---公式ID Note---------说明 ------------------ID FormulaKey Note --------------1 “F100” “”

F=((D1+D2)*D3)-IF((((D1+D2)>D3) and (D5>D6)),D8,D9) * + D1 D2 D3 D8 Ne w D1 IF D9 + D2 > D3 D5 and > D6

ID----------------二叉树结点ID PID---------------二叉树父结点，如果PID=0，则表示为根节点 LID---------------二叉树左结点ID RID---------------二叉树右结点ID IFID--------------IF表达式结点条件树根结点ID ForestID----------二叉树所属森林ID Key---------------二叉树结点Key Val---------------二叉树结点Val ValDisplayText----显示文本 DetailNote--------详细说明 IsExtern----------是否为扩展 tag---------------结点标志 x-----------------x坐标 y-----------------y坐标 zIndex------------z轴设置 --------------------------------------------------------ID PID LID RID IFID ForestID Key Val x y … --------------------------------------------------------1 3 0 0 0 1 D1 2 3 0 0 0 1 D2 3 5 1 2 0 1 “” + 4 5 0 0 0 1 D3 5 18 3 4 0 1 “” * 6 17 0 0 0 1 D8 7 17 0 0 0 1 D9 8 10 0 0 0 1 D1 9 10 0 0 0 1 D2 10 12 8 9 0 1 “” + 11 16 0 0 0 1 D3 12 16 10 11 0 1 “” > 13 15 0 0 0 1 D5 14 15 0 0 0 1 D6 15 16 13 14 0 1 “” > 16 17 12 15 0 1 “” and 17 18 6 7 16 1 “” IF 18 0 5 17 0 1 “” -

: CreateTree(FormulaStr) as SNode

公式三：Formula=(D3*D7)+D9

(

)

pNode=NULL

解析： 1、最小项–仅指本公式的最小表达式，不含查表 展开部分的公式。 2、IF表达式--IF(条件，真返回值，假返回值)

最小项

Y

pHead=创建节点(Formula) 公式计算缓冲表(最小粒度计算值): Formula(D1)=2 Formula(D2)=5 Formula(D3)=7 Formula(D7)=11.5 Formula(D4)=9 Formula(D5)=11 Formula(D8)=11 Formula(D9)=11

N

IF表达式 Y

N

公式三项分离并初始化结点信息 sOperatorNode=中间项 sLeftNode=左项 sRightNode=右项 pOperatorNode=创建结点(sOperatorNode) pLeftNode=CreateTree(sLeftNode) pRightNode=CreateTree(sRightNode)

公式三项分离并初始化结点信息 sOperatorNode=中间项 sCoditionNode=条件项 sLeftNode=真值项 sRightNode=假值项 pOperatorNode=创建结点(sOperatorNode) pCoditionNode=CreateTree(sOperatorNode) pLeftNode=CreateTree(sLeftNode) pRightNode=CreateTree(sRightNode) pOperatorNode.condition=pCondition pCondition.parent=pOperatorNode pOperatorNode.left=pLeftNode pLeftNode.parent=pOperatorNode pOperatorNode.right=pRightNode pRightNode.parent=pOperatorNode pNode=pOperatorNode

pOperatorNode.left=pLeftNode pLeftNode.parent=pOperatorNode pOperatorNode.right=pRightNode pRightNode.parent=pOperatorNode pNode=pOperatorNode

返回pNode

F=((F1+F2)*F3)-IF((((F1+F2)>F3) and (F5>F6)),F8,F9) DeleteTree(pCurNode)

pCurNode.left==null Y pCurNode.right==null Y pCurNode.condition==null Y pCurNode==pHead Y pHead=null N pCurNode==pCurNode.parent.left Y N N DeleteTree(pCurNode.condition) N DeleteTree(pCurNode.right) F1 + F2 N DeleteTree(pCurNode.left) * F3 F8 Ne w F1 IF F9 + F2 > F3 F5 and > F6

pCurNode.parent.right=null

pCurNode.parent.left=null

FreeNode(pCurNode)

返回

OutFormula(pNode) as string

sFormula=输入公式 sFormula=pNode.data.key

pNode为叶子结点 N IF表达式 N

Y

sFormulaLeft=OutFormula(pNode.left) sFormulaRight=OutFormula(pNode.Right) sFormula=”(“ + sFormulaLeft + pNode.key + sFormulaRight + “)”

Y

sFormulaLeft=OutFormula(pNode.left) sFormulaRight=OutFormula(pNode.Right) sCondition = OutFormula(pNode.condition) sFormula=”IF(“ + sCondition + “,” + sFormulaLeft + “,” + sFormulaRight + “)”

返回sFormula

二叉树表达式合法性判断规则： 1、pHead不能为空 2、叶子结点必须为可计算值的表达式 3、非叶子结点必须为算术运算符或IF表达符，如+,-,*,/,>,>=,

F=((D1+D2)*D3)-IF((((D1+D2)>D3) and (D5>D6)),D8,D9) pHead -

IsLeagalTree(pTree) as bool

pHead为空 N pCurNode=pTree Y bRet=false D1 +

* D3 D2 D8 Ne w

IF D9 + D1 D2 > D3

and > D5 D6

bRet=返回值 pCurNode为叶 子结点 N 是否运算符 N IsLeagalTree(pCurNode.left) and IsLeagalTree(pCurNode.right) Y bRet=true 可计算表达式 Y bRet=true N bRet=false bRet=false Y bRet=false 数据结构： struct tagNodeData{ DisplayText ; //结点显示文本 DetailNote ; //结点详细描述 SyntaxVal ; //结点语义值 CaculateVal ; //结点计算值 IsExtern ; //是否扩展结点（由父结点展开所得到的结点） tag ; //结点标志： // 1-算术符号,如+,-,*,/,>,>=,

Y

N

返回bRet

//pHead

InsertNode(pHead,pCurNode,pNewNode,InsertPos,PosOfNew) as Snode STreeHead.TreeRoot

F=((D1+D2)*D3)-IF((((D1+D2)>D3) and (D5>D6)),D8,D9) * + pHead为空 N 选择新结点插入位置 当前结点设为新 结点的左结点 (PosOfNew) N N 当前结点设为新结点的 左结点 (PosOfNew) pNewNode.right=pCurNode pHead=pNewNode Y pNewNode.left=pCurNode pNewNode.parent=pCurNode pCurNode.parent=pNewNode Y pHead=pNewNode D1 D2 D3 D8 Ne w D1 IF D9 + D2 > D3 D5 and > D6

pHead-头结点；pCurNode-当前选中结点；pNewNode-带插入结点 InsertPos--新结点插入当前结点的位置（上、左、右） PosOfNew–-（上）当前结点重新设为新结点的左右那个位置 或 （左、右）当前结点的原左（右）结点重新设为新结点的左右那个位置

上 (InsertPos)

Y

pHead=pCurNod e

Y

Y

pNewNode.left=pCurNode pHead=pNewNode

pCurNode==pCurNode.parent.left N N N

Y

pCurNode.parent.left=pNewNode

pCurNode.parent.right=pNewNode pNewNode.right=pCurNode pNewNode.parent=pCurNode pCurNode=pCurNode.parent.left N pCurNode.parent.right=pNewNode pCurNode.parent=pNewNode Y

pCurNode.parent=pNewNode

pCurNode.parent.left=pNewNode

左 (InsertPos) N （右） 当前结点右结点设 为新结点的左结点 (PosOfNew) N

Y

当前结点左结点设 为新结点的左结点 (PosOfNew) N pNewNode.right=pCurNode.left Y

Y

pNewNode.left=pCurNode.left

pNewNode.parent=pCurNode

pCurNode.left==null N pCurNode.left.parent=pNewNode Y

pNewNode.left=pCurNode.right

pNewNode.right=pCurNode.right

pNewNode.parent=pCurNode pCurNode.right==null N pCurNode.right.parent=pNewNode Y pCurNode.right=pNewNode

pCurNode.left=pNewNode

汇合点 结束

是否为头结点；是否为叶子结点；提升左结点还是右结点？留守结点作为提升结点的最左结点还是最右结点？ pHead=头结点 pDelNode=待删除结点 bUpLeftNode=是否提升左结点 bMoveToLeft=留守结点是否移到提升结点的最左边 pUpNode=提升结点 pStayNode=留守结点 bUpLeftNode==true Y D1 pUpNode=pDelNode.left pStayNode=pDelNode.right bMoveToLeft Y pTmpNode=GetLeftMostLeaf(pDelNode) pTmpNode==null N pTmpNode.left=pStayNode pTmpNode=GetRightMostLeaf(pDelNode) pTmpNode==nul l N pTmpNode.right=pStayNode N D2 Ne w D1 + D2 D3 D5 D6 N pUpNode=pDelNode.right pStayNode=pDelNode.left

F=((D1+D2)*D3)-IF((((D1+D2)>D3) and (D5>D6)),D8,D9) * + D3 D8 IF D9 > and >

pStayNode==null N pStayNode.parent=pTmpNode Y pDelNode==pHead Y Y pUpNode==null Y N pStayNode==null Y pHead=null pDelNode==pDelNode.parent.left N pUpNode==null Y Y pStayNode==null Y pDelNode.parent.right=null pUpNode==null Y pStayNode==null Y pDelNode.parent.left=null N pDelNode.parent.left=pStayNode pStayNode.parent=pDelNode.parent N pDelNode.parent.left=pUpNode pUpNode.parent=pDelNode.parent N pDelNode.parent.right=pStayNode pStayNode.parent=pDelNode.parent N pDelNode.parent.right=pUpNode pUpNode.parent=pDelNode.parent N pHead=pStayNode pStayNode.parent=pHead N pHead=pUpNode pUpNode.parent=pHead Y

pDelNode.left=null pDelNode.right=null FreeNode(pDelNode)

nRet=0 ;//返回值 nRet=0 ;//返回值 pCurNode.parent==pNewParent N pCurNode.parent==pHead Y nRelation=GetNodeRelation(pCurNode,pNewParent) nRelation==1 N nRelation==2 N nRet=0 ;//返回值 nRelation==3 Y N nRet=-1 Y pNewRoot=pCurNode.condition N pCurNode.right==pNewRight N pOldRight=pCurNode.right pCurNode.right=pNewRight pHead=pNewRoot Y 返回 nRet Y pNewRoot=pCurNode.right Y pNewRoot=pCurNode.left 返回 nRet pCurNode.left==pNewLeft N pOldLeft=pCurNode.left pCurNode.left=pNewLeft Y

pOldParent=pCurNode.parent pCurNode.parent=pNewParent 返回nRet

F=((D1+D2)*D3)-IF((((D1+D2)>D3) and (D5>D6)),D8,D9) nRet=0 ;//返回值 * pCurNode.condition==pNewCondition + N pOldCondition=pCurNode.condition pCurNode.condition=pNewCondition Y 返回 nRet D1 D2 Ne w D1 + D2 D3 D5 D6 D3 D8 D9 > > IF and

UpdateTreeParent(pHead,pCurNode,pNewParent,pOldParent

UpdateTreeLeft(pCurNode,pNewLeft,pOldLeft) UpdateTreeRight(pCurNode,pNewRight,pOldRight) UpdateTreeCondition(pCurNode,pNewCondition,pOldCondition) UpdateTreeData(pCurNode,pNewData,pOldData)

二叉树表达式合法性判断规则： 1、pHead不能为空 2、叶子结点必须为可计算值的表达式 3、非叶子结点必须为算术运算符或IF表达符，如+,-,*,/,>,>=,

函数： CaculateFormula(pTree):计算二叉树表达式的数值 CaculateMinUnit(SyntaxVal):计算最小粒度叶子结点的值 CaculateMath2(SyntaxVal,Condition,Val1,Val2):数学、逻辑运算, 如果SyntaxVal不为IF，Condition参数忽略 F=((D1+D2)*D3)-IF((((D1+D2)>D3) and (D5>D6)),D8,D9) pHead -

CaculateFormula(pTree) as float

pCurNode=pTree

fVal=0 pCurNode为叶 子结点 N fValLeft=CaculateFormula(pCurNode.left)

* + D1 D2 D3 D8 Ne w

IF D9 + D1 D2 > D3

and > D5 D6

fValRight=CaculateFormula(pCurNode.Right)

Y

pCurNode为IF结点

Y

bCondition=CaculateFormula(p CurNode.condition) N fVal=CaculateMinUnit(pCurN ode.data.Val) fVal=CatulateMath(pCurNode.data.Val,bCondition,f ValLeft,fValRight)

返回fVal

数据结构： struct tagNodeData{ DisplayText ; //结点显示文本 DetailNote ; //结点详细描述 SyntaxVal ; //结点语义值 CaculateVal ; //结点计算值 IsExtern ; //是否扩展结点（由父结点展开所得到的结点） tag ; //结点标志： // 1-算术符号,如+,-,*,/,>,>=,

CaculateMath(SyntaxVal,Condition,Val1,Val2) as float

fRet=返回值

SyntaxVal=”IF”

Y

Condition=true N

Y

fRet=Val1

N

fRet=Val2 Y fRet=Val1+Val2

+ N N * N / N > N >= N

Y

fRet=Val1-Val2

Y

fRet=Val1*Val2

Y

fRet=Val1/Val2

Y

fRet=(Val1>Val2)

Y

fRet=(Val1>=Val2)

Y

fRet=(Val1

Y

fRet=(Val1

Y

fRet=(Val1==Val2)

Y

fRet=(Val1!=Val2)

Formula(F)=err

返回fRet

/