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

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 2

In Prefix expression operators comes first then operands : +ab[ oprator ab ]

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

---

Step 1: (a - b) = (- ab) [ '(' has highest priority ]

step 2: (d + e - f / g) = (d + e - / fg) [ '/' has highest priority ]

                       = (+ de - / fg )

          ['+','-' has same priority but left to right associativity]

                       = (- + de / fg)

Step 3: (-ab )/ c * (- + de / fg) = / - abc * (- + de / fg)

                                 = * / - abc - + de / fg 

Prefix : * / - abc - + de / fg

Answer 3

This is the algorithm using stack.
Just follow these simple steps.

1.Reverse the given infix expression.

2.Replace '(' with ')' and ')' with '(' in the reversed expression.

3.Now apply standard infix to postfix subroutine.

4.Reverse the founded postfix expression, this will give required prefix expression.

In case you find step 3 difficult consult http://scanftree.com/Data_Structure/infix-to-prefix where a worked out example is also given.

Answer 4

Infix to PostFix using Stack:

     Example: Infix-->         P-Q*R^S/T+U *V
     Postfix -->      PQRS^*T/-UV

     Rules:
    Operand ---> Add it to postfix
    "(" ---> Push it on the stack
    ")" ---> Pop and add to postfix all operators till 1st left parenthesis
   Operator ---> Pop and add to postfix those operators that have preceded 
          greater than or equal to the precedence of scanned operator.
          Push the scanned symbol operator on the stack

Answer 5

https://en.wikipedia.org/wiki/Shunting-yard_algorithm

The shunting yard algorithm can also be applied to produce prefix notation (also known as polish notation). To do this one would simply start from the end of a string of tokens to be parsed and work backwards, reverse the output queue (therefore making the output queue an output stack), and flip the left and right parenthesis behavior (remembering that the now-left parenthesis behavior should pop until it finds a now-right parenthesis).

from collections import deque
def convertToPN(expression):
    precedence = {}
    precedence["*"] = precedence["/"] = 3
    precedence["+"] = precedence["-"] = 2
    precedence[")"] = 1

    stack  = []
    result = deque([])
    for token in expression[::-1]:
        if token == ')':
            stack.append(token)
        elif token == '(':
            while stack:
                t = stack.pop()
                if t == ")": break
                result.appendleft(t)
        elif token not in precedence:
            result.appendleft(token)
        else:
            # XXX: associativity should be considered here
            # https://en.wikipedia.org/wiki/Operator_associativity
            while stack and precedence[stack[-1]] > precedence[token]:
                result.appendleft(stack.pop())
            stack.append(token)

    while stack:
        result.appendleft(stack.pop())

    return list(result)

expression = "(a - b) / c * (d + e - f / g)".replace(" ", "")
convertToPN(expression)

step through:

step 1 : token ) ; stack:[ ) ]
result:[  ]
step 2 : token g ; stack:[ ) ]
result:[ g ]
step 3 : token / ; stack:[ ) / ]
result:[ g ]
step 4 : token f ; stack:[ ) / ]
result:[ f g ]
step 5 : token - ; stack:[ ) - ]
result:[ / f g ]
step 6 : token e ; stack:[ ) - ]
result:[ e / f g ]
step 7 : token + ; stack:[ ) - + ]
result:[ e / f g ]
step 8 : token d ; stack:[ ) - + ]
result:[ d e / f g ]
step 9 : token ( ; stack:[  ]
result:[ - + d e / f g ]
step 10 : token * ; stack:[ * ]
result:[ - + d e / f g ]
step 11 : token c ; stack:[ * ]
result:[ c - + d e / f g ]
step 12 : token / ; stack:[ * / ]
result:[ c - + d e / f g ]
step 13 : token ) ; stack:[ * / ) ]
result:[ c - + d e / f g ]
step 14 : token b ; stack:[ * / ) ]
result:[ b c - + d e / f g ]
step 15 : token - ; stack:[ * / ) - ]
result:[ b c - + d e / f g ]
step 16 : token a ; stack:[ * / ) - ]
result:[ a b c - + d e / f g ]
step 17 : token ( ; stack:[ * / ]
result:[ - a b c - + d e / f g ]

# the final while
step 18 : token ( ; stack:[  ]
result:[ * / - a b c - + d e / f g ]

Answer 6

(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. (- a b)
5. (/ (- a b) c)
6. (* (/ (- a b) c) (- (+ d e) (/ f g)))