Convert infix to prefix notation

A non-recurcive algorithm for converting infix notation to prefix notation.
excuse the lack of indentation.



Algorithm ConvertInfixtoPrefix

Purpose: Convert and infix expression into a prefix expression.
Begin // Create operand and operator stacks as empty stacks.
Create OperandStack

Create OperatorStack


// While input expression still remains, read and process the next token.

while( not an empty input expression )
read next token from the input expression


// Test if token is an operand or operator
if ( token is an operand )
// Push operand onto the operand stack.
OperandStack.Push (token)


else
// Token must be an operator.
if ( token is '(' or OperatorStack.IsEmpty() or OperatorHierarchy(token) > OperatorHierarchy(OperatorStack.Top()) )
// Push left parentheses onto the operator stack

OperatorStack.Push ( token )

else
if( token is ')' )
// Continue to pop operator and operand stacks, building
// prefix expressions until left parentheses is found.
// Each prefix expression is push back onto the operand
// stack as either a left or right operand for the next operator.
while( OperatorStack.Top() not equal '(' )
OperatorStack.Pop(operator)
OperandStack.Pop(RightOperand)
OperandStack.Pop(LeftOperand)
operand = operator + LeftOperand + RightOperand
OperandStack.Push(operand)
endwhile

// Pop the left parthenses from the operator stack.
OperatorStack.Pop(operator)

else
if( operator hierarchy of token is less than or equal to hierarchy of top of the operator stack )

// Continue to pop operator and operand stack, building prefix
// expressions until the stack is empty or until an operator at
// the top of the operator stack has a lower hierarchy than that
// of the token.
while( !OperatorStack.IsEmpty() and . OperatorHierarchy(token) lessThen Or Equal to OperatorHierarchy(OperatorStack.Top()) )
OperatorStack.Pop(operator)
OperandStack.Pop(RightOperand)
OperandStack.Pop(LeftOperand)
operand = operator + LeftOperand + RightOperand
OperandStack.Push(operand)

endwhile
// Push the lower precedence operator onto the stack
OperatorStack.Push(token)

endif

endif
endif
endif
endwhile
// If the stack is not empty, continue to pop operator and operand stacks building
// prefix expressions until the operator stack is empty.
while( !OperatorStack.IsEmpty() ) OperatorStack.Pop(operator)
OperandStack.Pop(RightOperand)
OperandStack.Pop(LeftOperand)
operand = operator + LeftOperand + RightOperand

OperandStack.Push(operand)
endwhile



// Save the prefix expression at the top of the operand stack followed by popping
// the operand stack.

print OperandStack.Top()

OperandStack.Pop()



End