Prefix to Postfix using Binary Tree

Recently we have given a online assignment to convert a prefix expression to postfix using binary tree. but it is very odd to say that we had learn tree only a day before. as a result only three or four of us among 30 could complete the code in 2 hours limited time. fortunately i was one of them. and for all of my friends who are struggling with it could see the following code.

This section is Updated later:

I wanted to explain a lot but i can’t because of time. have lots of thing to share. firstly i have made a power point slide that actually simulates how a binary expression tree is made from a prefix expression. hope this will at least help to understand the logic behind the conversion. click this link Prefix to Expression Tree Simulation

Updated section ends here

Here is the code of prefix to binary tree(arrayed implementation).


#include<iostream>
using namespace std;

#define MAX 100
int count=1;
char e[MAX],b[2*MAX];

bool isOperator(char ch){
    return ch=='+' || ch=='-' || ch == '*' ||
        ch == '/' || ch == '$' || ch == '%';
}

void left(char,int);
void right(char,int);

void left(char op,int i){

    if(isOperator(op)){

        b[2*i]=op;
        count++;
        left(e[count],2*i);
        right(e[count],2*i);
    }
    else
    {
        b[2*i]=op;
        count++;
    }
}

void right(char op,int i){

    if(isOperator(op)){

        b[2*i+1]=op;
        count++;
        left(e[count],2*i+1);
        right(e[count],2*i+1);
    }
    else
    {
        b[2*i+1]=op;
        count++;
    }
}

void postorder(int i){
    if(isOperator(b[i]))postorder(2*i);
    if(isOperator(b[i]))postorder(2*i+1);
    cout << b&#91;i&#93; ;

}

int main(){

    cout << "Enter a prefix : ";
    cin >> e;
    int len=strlen(e);

    count=0;
    b[1]=e[count];

    count++;
    left(e[count],1);
    right(e[count],1);

    postorder(1);

    return 0;
}
Advertisements

15 thoughts on “Prefix to Postfix using Binary Tree

  1. Nice solution using the array implementation of a BT. Why don’t you put up a brief explanation of your code for others (if other need)? [specially 2*i and 2*i+1, and also the meaning of i at the functions]

    Anyway, there is a demerit of this process. It may require a very deep BT and in that case it will be necessary to declare a very long array. And in that case link list implementation of BT or array representation of link list for BT may come into play. And it will be quite trouble some to code and i think our BUET teachers will never give such a disgusting task 🙂

    But if anyone is interested then you may try to do this task(not using BT explicitly but surely you need the idea of BT) more efficiently. ( Why dont you give it a try with stack :p )

  2. thanks for this constructive comment.

    about comment in code:
    will add it as soon as possible

    agree with you about the demerit. and i also hope BUET teachers will never give this type of inefficient algorithm or data structure to implement.

    and about the link list and stack implementation
    again will say “will add it as soon as possible”

  3. firstly asking apologias for late replay. i had semester final exam on “digital logic design” today (19 Nov 07).

    actually

    +*abc*a/cd

    is not a valid prefix expression.

    first +*abc this portion is valid prefix expression so program outputs

    ab*c+

    as the program does not checks that the hole experssion is correct or not, this problem occur. right now thinking to add a check on it.

    finally thanks for contacting.

  4. the expressions above are completely valid and are have been made by using stack method and by drawing binary tree as well

  5. the prefix is valid but if you look closely that I didn’t consider ‘%’ as an operator. adding in respect to u. and also I consider MAX 100 u may need more space to convert using binary tree usually it is 2^(depth of the binary tree+1) .

    and postfix of

    +++a/*bcc%fcc

    is

    abc*c/+fc%+c+

    carefully traverse the tree. you have to agree with me.

    finally thanks for informing me.

  6. Hi. would just like to ask, because everytime i try it on my Dev-C++, it tells us count is undeclared, even though i see that you have declared count.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s