C++ Help with Infix to Prefix

[littletemple]

I am trying to find an algorithm to convert a infix notation to prefix notation. I can't seem to figure it out. Can someone please help me out????

 

[ViRGE]

Put the infix equation into a tree. Then read off the tree in the proper order for a prefix equation.

 

[cchen]

You could use stacks or queues (forget which) to do that

 

[safoo]

im pretty sure u can implement it with queues or a tree....the algorithm should be in any basic C++ text book. just look in the index.

otherwise search google...it has to be there.....

 

[littletemple]

i've been looking but the algorithm that i tried did not work. I'm trying to use a stack to get it to work.

 

[iamfried]

This should do you, it puts everything in postfix, the setupword method that it uses just converts operators like + and - to other things so you don't need that.
I also don't feel real bad about you not getting the full learning experience of doing it yourself because this is in C, but it should give you the basic idea.

long intopost (Stack * stack1) {
Stack * temp_stack;
char character;
long value;
long parenth_counter = 0;
long from_setupword;
temp_stack = new_Stack(CALCSTACKSIZE);
empty_Stack(stack1);
/* This loop calls the data entered and performs the appropriate
task on what was entered. It reads in numbers and
operators. */
while (1) {
character = getchar();
if (character == EOF){
delete_Stack(&temp_stack);
return EOF;
}
/* The '\n' signals the loop that the user is done
entering data and all things that are left on
temp_stack are moved onto stack1. */
if (character == '\n') {
while (! isempty_Stack(temp_stack)) {
pop(temp_stack, &value);
push(stack1, value);
}
break;
pop(temp_stack, &value);
if (CHARACTER(value) == '(') {
parenth_counter--;
break;
}
push (stack1, value);
}
continue;
}
/* This block takes care of all the other operators.
(ie. + - * / ^ !) */
else {
if (isempty_Stack(temp_stack))
push(temp_stack, setupword(character));
else {
from_setupword = setupword(character);
top(temp_stack, &value);
if(PRIORITY(from_setupword) > PRIORITY(value))
push(temp_stack, from_setupword);
else {
while (PRIORITY(from_setupword) <=
PRIORITY(value)) {
pop(temp_stack, &value);
push(stack1, value);
if(isempty_Stack(temp_stack))
break;
top(temp_stack, &value);
}
push(temp_stack, from_setupword);
}
}
}
}
delete_Stack(&temp_stack);
if (parenth_counter > 0) {
writeline("Extra close parenthesis found!");
if (parenth_counter > 0) {
writeline("Extra close parenthesis found!");
newline();
return 0;
}
if (parenth_counter < 0) {
parenth_counter *= -1; // Converts counter to pos num
decout(parenth_counter);
writeline(" unmatched open parenthesis found!");
newline();
return 0;
}
return 1;
}