conversion from infix to prefix

Question

I am preparing for an exam where i couldn't understand the convertion of infix notation to polish notation for the below expression:

(a–b)/c*(d + e – f / g)

Can any one tell step by step how the given expression will be converted to prefix?

Answer 1

Algorithm ConvertInfixtoPrefix

Purpose: Convert an 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)
    endif

    // If it is a left parentheses or operator of higher precedence than the last, or the stack is empty,
    else if ( token is '(' or OperatorStack.IsEmpty() or OperatorHierarchy(token) > OperatorHierarchy(OperatorStack.Top()) )
    // push it to the operator stack
        OperatorStack.Push ( token )
    endif

    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)
    endif

    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
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

Answer 2

This algorithm will help you for better understanding .

Step 1. Push “)” onto STACK, and add “(“ to end of the A.

Step 2. Scan A from right to left and repeat step 3 to 6 for each element of A until the STACK is empty.

Step 3. If an operand is encountered add it to B.

Step 4. If a right parenthesis is encountered push it onto STACK.

Step 5. If an operator is encountered then: a. Repeatedly pop from STACK and add to B each operator (on the top of STACK) which has same or higher precedence than the operator. b. Add operator to STACK.

Step 6. If left parenthesis is encontered then a. Repeatedly pop from the STACK and add to B (each operator on top of stack until a left parenthesis is encounterd) b. Remove the left parenthesis.

Step 7. Exit