Infix, Prefix and Postfix conversion

[paulm]

Hello;

I would appreciate some help with a class assingment that deals with conversion from infix to prefix and postfix with stacks.

I found this thread already, but it was last replied to in 2003.

Here is some more detailed information about my current program:

Inputs:
- user's infix equation
- continue?

Outputs:
- prefix equation
- postfix equation
- binary tree

The program is based upon Algorithm's that we were given, but I am told that these algorithms are incorrect:

Algorithms:

Infix -> Prefix:
1. Reverse the input (read from right to left)
2. Examine the next element in the string
3. If it is an operand
a. Add it to the output
4. if it is an operator
a. if the stack is empty, push operator on stack
b. if stack is closing bracket, push operator on the stack
c. if the operator in the stack has the same or higher priority, push the operator on the stack
d. otherwise, pop the operate from the stack, and add it to the string or output
e. if opening bracket, pop the operators and add them to the output, until a closing bracket is encountered
5. Pop and discard brackets
6. Reverse the output

Infix -> Postfix:
1. Examine the next element in the input
2. if it is an operand, output it
3. If it is a parentheses, push it
a. If stack is empty, push operator on stack
b. If TOS is opening bracket, push operator on stack
c. If it is higher priority than TOS, push operator on stack.
d. Else pop the operator from stack and output-repeat step 4
4. If closing brackets, pop operators from stack and output until an opening bracket is encountered.
a. Pop and discard opening bracket
5. If there is more input, go to step 1
6. If no more input, pop operators to output

Binary Tree: (sometimes called an expression tree)

1. Reverse the prefix expression
2. Examine the next element in the input
3. If it is an operand
a. Create a leaf node ? (set left and right nodes to null first
b. Copy the operand to the data part
c. Push nodes address on stick
4. If it is an operator
a. Create a node
b. Copy the operator in the data part
c. Pop address of node from stack and assign it to the left node
d. Pop address of node from stack and assign it to right node
e. Push nodes address on stack
5. If there is more input go to step 2 If there is no more input pop addresses from stack, which is the address of the root node


I also have included my current program. The issue is that fixing one part of an equation such as putting all the operators from brackets before the operands in the prefix output, seems to break another! It's a deadly circle that I am having trouble escaping.

Can anybody help me diagnose what is going wrong here?