c++ - 中缀表达式转成二叉树，多位数字如何处理？strcpy可以往节点内连续复制字符串吗？

在研究中缀表达式转换成二叉树的算法，发现网上的大多数代码都没办法处理二位及以上的数字，只能处理个位数。感觉如果转成前缀或者后缀表达式计算的话，数字之间加空格，一样可以处理多位数。所以改了一下代码，果然出现了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] == '/') && 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;
}

希望明白的前辈能指点一下~

PHPz2803 hari yang lalu1087

c++ - 中缀表达式转成二叉树，多位数字如何处理？strcpy可以往节点内连续复制字符串吗？

membalas semua(1)saya akan balas