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