中缀表达式生成二叉树，大概应该有递规，迭代，和编译原理中的自顶向下的预测分析法等。
递规，迭代的思路每次读出一个数字，一个运算符，比较当前运算符和之前符号的优先级，进行相关的操作。
自顶向下的预测分析法，做了下，实在忘记的差不多了，先占个位。以后完成。
tree.c
#include "head.h" struct Node * CreateNodesetV(int number,char opr,int type) { struct nodeData db; db.numberValue=number; db.operatorValue=opr; db.symbolType=type; struct Node * myNode=malloc(sizeof(struct Node)); CreateNode(db,myNode); return myNode; }; void CreateNode(struct nodeData nd,struct Node * myN) { myN->NData.numberValue=nd.numberValue; myN->NData.operatorValue=nd.operatorValue; myN->NData.symbolType=nd.symbolType; myN->lchilden=' '; myN->rchilden=' '; }; char insertNode(struct Node * myNode,struct Node * father,char lr) { char result='Y'; if(lr=='L') { if(father->lchilden==' ') { father->lchilden=myNode; } else { result='N'; } } else { if(father->rchilden==' ') { father->rchilden=myNode; } else { result='N'; } } return result; } //原来树的遍历也就是递归.我去,我说自己怎么老是不得要领.根源在于没想明白递归函数. void visitTree(struct Node * Root) { if(Root->lchilden!=' ') { visitTree(Root->lchilden); } else { //终止递归的确定事件,是无事件. } if(Root->NData.symbolType==1) { printf("%d",Root->NData.numberValue); } else { printf("%c",Root->NData.operatorValue); } if(Root->rchilden!=' ') { visitTree(Root->rchilden); } else { //终止递归的确定事件,是无事件. } }
//所以如果用递归来做运算必须是后序遍历，要等左右树都有结果了，才用符号。 //其实我们的心算和笔算，也是后续遍历。 int visitTree_2(struct Node * Root) { int lvalue; int rvalue; int result; if(Root->lchilden!=' ') { lvalue=visitTree_2(Root->lchilden); } else { return Root->NData.numberValue; } if(Root->rchilden!=' ') { rvalue=visitTree_2(Root->rchilden); } else { return Root->NData.numberValue; } switch (Root->NData.operatorValue) { case '+': { result=lvalue+rvalue; break; } case '-': { result=lvalue-rvalue; break; } case '*': { result=lvalue*rvalue; break; } case '/': { result=lvalue/rvalue; break; } } return result; }
head.h
//tree struct nodeData { int symbolType; //1: number 2: operator int numberValue; char operatorValue; }; struct Node { struct nodeData NData; struct Node * lchilden; struct Node * rchilden; }; char insertNode(struct Node * myNode,struct Node * father,char lr); struct Node * CreateNodesetV(int number,char opr,int type); void CreateNode(struct nodeData nd,struct Node * myN); void visitTree(struct Node * Root);
1）迭代方法
main.c
基本思路就是我们手工画图的步骤。写成代码而已。
每次取一个数字和操作符，对比操作符和之前操作符的优先顺序。
状1，大于，则符号为之前树的右子树，数字为符号的左子树。
状2，小于，则数字为之前树的右字树，之前树为符号的左子树。
直至最后，只有一个数字符，此数字为之前符号的右子树，
int main() { char * expression="2+3*5-4/2"; //每次取一个数字和操作符，对比操作符和之前操作符的优先顺序。 //状1，大于，则符号为之前树的右子树，数字为符号的左子树。 //状2，小于，则数字为之前树的右字树，之前树为符号的左子树。 //直至最后，只有一个数字符，此数字为之前符号的右子树， char preOpe='#'; struct Node * PreNode=' '; struct Node * RootNode=' '; int i=0; int strLen=getStrLen(expression); while(i<strLen) { if(i==0)// { int cNumber=expression[i]-48; i++; char cOperator=expression[i]; i++; struct Node * LeftC=CreateNodesetV(cNumber,' ',1); struct Node * Root=CreateNodesetV(0,cOperator,2); insertNode(LeftC,Root,'L'); preOpe=cOperator; PreNode=Root; RootNode=Root; } else { if(i+2<strLen)//get a number and operator { int cNumber=expression[i]-48; i++; char cOperator=expression[i]; i++; if(lHeight(preOpe,cOperator)==1) { struct Node * numberNode=CreateNodesetV(cNumber,' ',1); struct Node * OpeNode=CreateNodesetV(0,cOperator,2); insertNode(OpeNode,PreNode,'R'); insertNode(numberNode,OpeNode,'L'); preOpe=cOperator; PreNode=OpeNode; } else if (lHeight(preOpe,cOperator)==0) { struct Node * numberNode=CreateNodesetV(cNumber,' ',1); struct Node * OpeNode=CreateNodesetV(0,cOperator,2); insertNode(RootNode,OpeNode,'L'); insertNode(numberNode,PreNode,'R'); preOpe=cOperator; PreNode=OpeNode; RootNode=OpeNode; } } else//last char { int cNumber=expression[i]-48; i++; struct Node * numberNode=CreateNodesetV(cNumber,' ',1); insertNode(numberNode,PreNode,'R'); } } } if(RootNode!=' ') { visitTree(RootNode); printf(" result:%d",visitTree_2(RootNode)); } return 0; } int getStrLen(char * c) { int i=0; while(c[i]!=' ') { i++; } return i; } int lHeight(char oldc,char newl) { if(oldc=='+'||oldc=='-') { if(newl=='*'||newl=='/') { return 1; } } else if(oldc=='#') { return 1; } return 0; }
2） 递规方式。
尾递规一般是可以用循环迭代来表示。所以这里递规其实并不是很体现优势。
只是可以锻炼下递规的思路，递规是：把问题难度逐层降低，以至到达某个层次（一般0或1），是个确定的操作不需要递规，那么这个层次的上层的操作也变成了确定操作。以至最终解决问题。
这里一样的思路：一个表达式很长，我只能解决一个数字，一个操作符，并把他放到之前的树上。剩下的表达式也就是遗留的问题让下层去做。下层能做的事和上面一样。以至到最后，只剩下一个数字，只能防到右叶，遗留的问题，到这里终结。
mian.c
void CreateTree(char * expression,struct Node * PreNode,char preOpe); struct Node * Root=' '; int main() { char * expression="2+3*5-4/2"; char preOpe='#'; struct Node * PreNode=' '; int strLen=getStrLen(expression); CreateTree(expression,PreNode,preOpe); if(Root!=' ') { visitTree(Root); printf(" result:%d",visitTree_2(Root)); } return 0; } void CreateTree(char * expression,struct Node * PreNode,char preOpe) { int strLen=getStrLen(expression); if(strLen>1) { int cNumber=expression[0]-48; char cOperator=expression[1]; if(lHeight(preOpe,cOperator)==1) { struct Node * numberNode=CreateNodesetV(cNumber,' ',1); struct Node * OpeNode=CreateNodesetV(0,cOperator,2); if(preOpe!='#') { insertNode(OpeNode,PreNode,'R'); insertNode(numberNode,OpeNode,'L'); preOpe=cOperator; PreNode=OpeNode; } else { insertNode(numberNode,OpeNode,'L'); preOpe=cOperator; PreNode=OpeNode; Root=OpeNode; } } else if (lHeight(preOpe,cOperator)==0) { struct Node * numberNode=CreateNodesetV(cNumber,' ',1); struct Node * OpeNode=CreateNodesetV(0,cOperator,2); insertNode(Root,OpeNode,'L'); insertNode(numberNode,PreNode,'R'); preOpe=cOperator; PreNode=OpeNode; Root=OpeNode; } CreateTree(expression+2,PreNode,preOpe); } else { int cNumber=expression[0]-48; struct Node * numberNode=CreateNodesetV(cNumber,' ',1); insertNode(numberNode,PreNode,'R'); } }
3）自顶向下的预测分析。
做了下，没出来。以后看看。