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;
}```

15 thoughts on “Prefix to Postfix using Binary Tree”

1. Md. Mahbubul Hasan says:

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 )

thanks for this constructive comment.

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.

again will say “will add it as soon as possible”

3. hamid tabani says:

your program does not work correctly !
+*abc*a/cd

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.

5. Poulami says:

your program does not work correctly !

6. Poulami says:

i will be very happy if u please send me the test cases where this code is not working.

8. surjeet says:

dear friend your code is not working with the prefix
+++a/*bcc%fcc
whose postfix is
a+b*c/c+fc%+c+

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

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.

by the way where do you study i am the student of uet lahore department of computer engineering