表达式建树

sscanf(formula+ld, "%lf", opt[nodeN].k); treeL[nodeN]=treeR[nodeN]=0;//末端节点没有左右孩子 return nodeN;//返回当前所建节点编号 int pAS=-1, pMD=-1;//分别表示加减号， 乘除号所在的位置 int paren=0;//记录左括弧相对于右括弧出现的数目 for(i=ld; i ++i) switch(formula[i]) case (: ++paren; break; case ): --paren; break; //最后计算的运算符一定是在括弧的外边，不会包含在括弧里边 case +: case -: if(paren==0) pAS=i; break; case *: case /: if(paren==0) pMD=i; break; if(pAS 0) pAS=pMD; if(pAS 0) //说明没有找到括弧外边的运算符，则脱掉一对括弧重新寻找 return buildTree(ld+1, rd-1); int u=++nodeN; opt[u].flag=optr;//表示存储操作符 opt[u].ch=formula[pAS]; treeL[u]=buildTree(ld, pAS); treeR[u]=buildTree(pAS+1, rd); return u; void printTree(int cur)//中序输出表达式树 if(cur)//非末端节点 printTree(treeL[cur]); if(opt[cur].flag==optd) cout opt[cur].k " "; else cout opt[cur].ch " "; printTree(treeR[cur]); int main() while(cin formula) buildTree(0, strlen(formula)); printTree(1); return 0; //用链表实现树 #include iostream #include ctype.h #include cstring #define N 10000 #define optd 1 #define optr 2 using namespace std; class node public: node *lchild, *rchild; int flag;//区分当前节点是操作符还是操作数 double k; char ch; char formula[1000]; void buildTree(node* T, int ld, int rd) int i; for(i=ld; i ++i) if(!isdigit(formula[i])) break; if(i =rd)//最后全部为数字的时候 T=new node(); T- flag=optd; sscanf(formula+ld, "%lf", T- return ; int pAS=-1, pMD=-1;//分别表示加减号， 乘除号所在的位置 int paren=0;//记录左括弧相对于右括弧出现的数目 for(i=ld; i ++i) switch(formula[i]) case (: ++paren; break; case ): --paren; break; //最后计算的运算符一定是在括弧的外边，不会包含在括弧里边 case +: case -: if(paren==0) pAS=i; break; case *: case /: if(paren==0) pMD=i; break; if(pAS 0) pAS=pMD; if(pAS 0) //说明没有找到括弧外边的运算符，则脱掉一对括弧重新寻找 return buildTree(T, ld+1, rd-1); T=new node(); T- flag=optr;//表示存储操作符 T- ch=formula[pAS]; buildTree(T- lchild, ld, pAS); buildTree(T- rchild, pAS+1, rd); void printTree(node *T)//中序输出表达式树 if(T)//非末端节点 printTree(T- lchild); if(T- flag==optd) cout T- k " "; else cout T- ch " "; printTree(T- rchild); int main() while(cin formula) node *T=NULL; buildTree(T, 0, strlen(formula)); printTree(T); return 0; }
栈与队列——150. 逆波兰表达式求值 本专栏按照数组—链表—哈希—字符串—栈与队列—二叉树—回溯—贪心—动态规划—单调栈的顺序刷题，采用代码随想录所给的刷题顺序，一个正确的刷题顺序对算法学习是非常重要的，希望对大家有帮助