-----------------------------------

paulm

Thu Apr 09, 2009 12:00 pm


Infix, Prefix and Postfix conversion

-----------------------------------

Hello;

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

I found  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?