Correct inorder transversal but wrong post order transversal for expression tree

Viewed 90

I am trying to write a program that outputs correct infix and postfix expressions given a prefix expression using an expression tree. My program however does not seem to print the correct post order transversal. Is there anything wrong with my algorithm?

    void createExpTree(BTNode** root,char* prefix)
{
    //Write your code here
    Stack s;
    s.head = NULL;
    s.size = 0;
    BTNode *temp;
    int intArray[SIZE];
    int theitem;
    int y = 0;
    char *x = prefix;
    char c;
    while(*x){
        if(isdigit(*x)){
            int val = (int)strtol(x,&x,10);           
            intArray[y++] = val;
        }else{
            x++;
        }
    }
    int ctr = strlen(prefix);
    int finalnum = 0;
    int i;
    for(i=ctr-1;i>=0;i--){
        c = prefix[i];
        if(c=='+'|| c=='-' || c=='*' || c=='/'){
            
            temp = malloc(sizeof(BTNode));
            temp->item = c;
            temp->left = peek(s);
            pop(&s);
            temp->right = peek(s);
            pop(&s);
            push(&s,temp);
        }else if(c!=' '){
            theitem = intArray[y-finalnum];
            temp = malloc(sizeof(BTNode));
            temp->item = theitem;
            finalnum++;
            temp->left = NULL;
            temp->right = NULL;
            push(&s,temp);
            i = i-intLen(theitem)+1;
            
        }
    }
    
    *root = peek(s);
    pop(&s);
}

edit: i tested it with the following input

prefix : + 99 * - 88 77 + / 66 - 55 44 33

the output was

infix: 99+ 88 - 77 * 66 / 55 - 44 + 33

postfix: 99 88 - 77 * 66 / 55 - 44 + 33 +

the postfix expression was wrong

edit2: the following code produces the output above

void printTree(BTNode *node){
    //Write your code here
    char ch;
    if(node==NULL) return;

    printTree(node->left);
    if(node->left==NULL && node->right==NULL){
        printf("%d ", node->item);
    }else{
        ch = (char)node->item;
        printf("%c ", ch);
    }

    printTree(node->right);
}


void printTreePostfix(BTNode *node){
   //Write your code here
    char ch;
    if(node==NULL) return;
    printTree(node->left);

    printTree(node->right);
    if(node->left==NULL && node->right==NULL){
        printf("%d ", node->item);
    }else{
        ch = (char)node->item;
        printf("%c ", ch);
    }



}
0 Answers
Related