c++ - 中缀表达式转成二叉树,多位数字如何处理?strcpy可以往节点内连续复制字符串吗?
PHPz
PHPz 2017-04-17 14:55:41
0
1
1086

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

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

PHPz
PHPz

学习是最好的投资!

répondre à tous(1)
PHPzhong

抛开算法不谈,你的数据结构明显有问题。key是一个char,你却用来strcpy。key至少要是一个char *,而且要分配好内存才能strcpy。
如果你只是想复制一个字符的话,直接=就好了

p->key = a[m]
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal