问题描述
在研究中缀表达式转换成二叉树的算法，发现网上的大多数代码都没办法处理二位及以上的数字，只能处理个位数。感觉如果转成前缀或者后缀表达式计算的话，数字之间加空格，一样可以处理多位数。所以改了一下代码，果然出现了bug
我的想法是，找出优先级别最高的符号，记录下标为tag，填入根，然后递归填树。因为数字都是在叶子里的，最后不管剩的是二位数还是个位数，都只剩数，而search()函数是不处理数字的，所以tag是初始值-1，不变。所以在填数的时候，如果begin==end，说明是剩个个位数，直接填入。否则检测一下tag如果是-1就说明是多位数，for循环把剩下的字符串都strcpy到当前叶子里，如果不是-1，正常操作填入a[tag]值。
if(tag == -1){ for(int m = begin; m <= end; m++) strcpy(&p->key, &a[m]); }else{ p->key = a[tag];}
这是填数那段代码，我觉得可能是strcpy不能这样用？
以下是全部处理代码：
typedef struct Node{ char key; struct Node * left; struct Node * right;}Node;//search for the operator with the highest grade in aint search(char a[], int begin, int end){ int tag = -1; int isInBrackets = 0; if(a[begin] == ’(’ && a[end] == ’)’) {begin += 1;end -= 1; } int amExist = 0; for(int i = begin; i < end; i++) {if(a[i] == ’(’) isInBrackets++;if(a[i] == ’)’) isInBrackets--;if((a[i] == ’+’ || a[i] == ’-’) && isInBrackets == 0){ tag = i; amExist = 1;}if((a[i] == ’*’ || a[i] == ’/’) && isInBrackets == 0 && amExist == 0){ tag = i;} } return tag;}//build the binary treeNode * buildBinaryTree(char a[], int begin, int end){ Node * p = NULL; if(begin == end) {p = (Node *)malloc(sizeof(Node));p->key = a[begin];p->left = NULL;p->right = NULL; } else {int tag;tag = search(a,begin,end);p = (Node *)malloc(sizeof(Node));if(tag == -1){ for(int m = begin; m <= end; m++)strcpy(&p->key, &a[m]); //错误在这里}else{ p->key = a[tag];}if(a[begin] == ’(’ && a[end] == ’)’){ begin += 1; end -= 1;}p->left = buildBinaryTree(a, begin, tag - 1);p->right = buildBinaryTree(a, tag + 1, end ); } return p;}
希望明白的前辈能指点一下~
问题解答
回答1：抛开算法不谈，你的数据结构明显有问题。key是一个char，你却用来strcpy。key至少要是一个char *，而且要分配好内存才能strcpy。如果你只是想复制一个字符的话，直接=就好了
p->key = a[m]
