conversion from infix to prefix

Question

HAi

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.

thank you

Answer 1

Maybe you're talking about the Reverse Polish Notation? If yes you can find on wikipedia a very detailed step-to-step example for the conversion; if not I have no idea what you're asking :(

You might also want to read my answer to another question where I provided such an implementation: http://stackoverflow.com/questions/1933970/c-simple-operations-evaluation-class/1933976#1933976

Answer 2

simple google search came up with this. Doubt anyone can explain this any simpler. But I guess after an edit, I can try to bring forward the concepts so that you can answer your own question.

Hint :

Study for exam, hard, you must. Predict you, grade get high, I do :D

Explanation :

It's all about the way operations are associated with operands. each notation type has its own rules. You just need to break down and remember these rules. If I told you I wrote (2*2)/3 as [* /] (2,2,3) all you need to do is learn how to turn the latter notation in the former notation.

My custom notation says that take the first two operands and multiple them, then the resulting operand should be divided by the third. Get it ? They are trying to teach you three things.

1. To become comfortable with different notations. The example I gave is what you will find in assembly languages. operands (which you act on) and operations (what you want to do to the operands).
2. Precedence rules in computing do not necessarily need to follow those found in mathematics.
3. Evaluation: How a machine perceives programs, and how it might order them at run-time.

Answer 3

If there's something about what infix and prefix mean that you don't quite understand, I'd highly suggest you reread that section of your textbook. You aren't doing yourself any favors if you come out of this with the right answer for this one problem, but still don't understand the concept.

Algorithm-wise, its pretty darn simple. You just act like a computer yourself a bit. Start by puting parens around every calculation in the order it would be calculated. Then (again in order from first calculation to last) just move the operator in front of the expression on its left hand side. After that, you can simplify by removing parens.

Answer 4

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

Prefix notation (reverse polish has the operator last, it is unclear which one you meant, but the principle will be exactly the same):

1. (/ f g)
2. (+ d e)
3. (- (+ d e) (/ f g))
4. (* c (- (+ d e) (/ f g)))
5. (/ (- a b) (* c (- (+ d e) (/ f g))))

Please specify exactly which steps are troubling you.

Answer 5

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