在研究中缀表达式转换成二叉树的算法,发现网上的大多数代码都没办法处理二位及以上的数字,只能处理个位数。感觉如果转成前缀或者后缀表达式计算的话,数字之间加空格,一样可以处理多位数。所以改了一下代码,果然出现了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 a
int 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] == '//m.sbmmt.com/m/') && isInBrackets == 0 && amExist == 0)
{
tag = i;
}
}
return tag;
}
//build the binary tree
Node * 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;
}
希望明白的前辈能指点一下~
PHPzhong2017-04-17 14:57:41
抛开算法不谈,你的数据结构明显有问题。key是一个char,你却用来strcpy。key至少要是一个char *,而且要分配好内存才能strcpy。
如果你只是想复制一个字符的话,直接=就好了
p->key = a[m]