How do I convert an expression from infix to prefix?

user_16461254 0
Viewed 300

I am a class 12 student from ISC 2022 batch, and this is my first question on Stack Overflow.

Recently this problem has been confusing me a lot, and I am finding different answers in the internet.

How do we convert an expression from infix to prefix in Java? For example, if the expression is (X+Y)/(Z*W/V), what is it's equivalent prefix expression?

My doubt focuses on the question that if while scanning, if incoming operator is of SAME precedence as that of top of the stack (TOS), then should we push it?

Or should we pop the TOS and check incoming operator with next TOS?

My computer teacher has taught us the latter, whereas in several sources like geeksforgeeks and javatpoint, I am finding the former method.

Please could someone clarify my doubt once and for all?

data-structures java
1 Answers

For infix to prefix conversion, the following steps can be followed:

  1. Reverse the infix string.
  2. Convert the modified string to postfix. ( must be handled as ) & ) as (.
  3. Reverse the obtained expression to get the prefix expression.

But for infix to postfix conversion, when the current token is an operator, we keep appending the tokens to the postfix expression, while precedenceOf(currToken) <= precedenceOf(stack.peek()).
But for conversion to prefix expression, due to the reversal of the infix string, the left to right associativity gets disturbed.
So, to maintain the associativity, when the incoming character is of the same precedence order:
push it into the stack, rather than popping out the top element from the stack.
Example:

infix = (X + Y) / (Z * W / V)  
prefix = /+XY/*ZWV

(X+Y)/(Z*W/V) => (+XY) / ((*ZW)/V) => (+XY) / (/*ZWV) => / +XY /*ZWV
*Brackets are only for illustration.

user_138824250
Related