Convert infix to prefix notation
What is infix notation?
An infix notation is a notation in which an expression is written in a usual or normal format. It is a notation in which the operators lie between the operands. The examples of infix notation are A+B, A*B, A/B, etc.
As we can see in the above examples, all the operators exist between the operands, so they are infix notations. Therefore, the syntax of infix notation can be written as:
<operand> <operator> <operand>
Parsing Infix expressions
In order to parse any expression, we need to take care of two things, i.e., Operator precedence and Associativity. Operator precedence means the precedence of any operator over another operator. For example:
A + B * C → A + (B * C)
As the multiplication operator has a higher precedence over the addition operator so B * C expression will be evaluated first. The result of the multiplication of B * C is added to the A.
Precedence order
|
Operators |
Symbols |
|
Parenthesis |
{ }, ( ), [ ] |
|
Exponential notation |
^ |
|
Multiplication and Division |
*, / |
|
Addition and Subtraction |
+, - |
Associativity means when the operators with the same precedence exist in the expression. For example, in the expression, i.e., A + B - C, '+' and '-' operators are having the same precedence, so they are evaluated with the help of associativity. Since both '+' and '-' are left-associative, they would be evaluated as (A + B) - C.
Associativity order
|
Operators |
Associativity |
|
^ |
Right to Left |
|
*, / |
Left to Right |
|
+, - |
Left to Right |
Let's understand the associativity through an example.
1 + 2*3 + 30/5
Since in the above expression, * and / have the same precedence, so we will apply the associativity rule. As we can observe in the above table that * and / operators have the left to right associativity, so we will scan from the leftmost operator. The operator that comes first will be evaluated first. The operator * appears before the / operator, and multiplication would be done first.
1+ (2*3) + (30/5)
1+6+6 = 13
What is Prefix notation?
A prefix notation is another form of expression but it does not require other information such as precedence and associativity, whereas an infix notation requires information of precedence and associativity. It is also known as polish notation. In prefix notation, an operator comes before the operands. The syntax of prefix notation is given below:
<operator> <operand> <operand>
For example, if the infix expression is 5+1, then the prefix expression corresponding to this infix expression is +51.
If the infix expression is:
a * b + c
↓
*ab+c
↓
+*abc (Prefix expression)
Consider another example:
A + B * C
First scan: In the above expression, multiplication operator has a higher precedence than the addition operator; the prefix notation of B*C would be (*BC).
A + *BC
Second scan: In the second scan, the prefix would be:
+A *BC
In the above expression, we use two scans to convert infix to prefix expression. If the expression is complex, then we require a greater number of scans. We need to use that method that requires only one scan, and provides the desired result. If we achieve the desired output through one scan, then the algorithm would be efficient. This is possible only by using a stack.
Conversion of Infix to Prefix using Stack
K + L - M * N + (O^P) * W/U/V * T + Q
If we are converting the expression from infix to prefix, we need first to reverse the expression.
The Reverse expression would be:
Q + T * V/U/W * ) P^O(+ N*M - L + K
To obtain the prefix expression, we have created a table that consists of three columns, i.e., input expression, stack, and prefix expression. When we encounter any symbol, we simply add it into the prefix expression. If we encounter the operator, we will push it into the stack.
|
Input expression |
Stack |
Prefix expression |
|
Q |
Q |
|
|
+ |
+ |
Q |
|
T |
+ |
QT |
|
* |
+* |
QT |
|
V |
+* |
QTV |
|
/ |
+*/ |
QTV |
|
U |
+*/ |
QTVU |
|
/ |
+*// |
QTVU |
|
W |
+*// |
QTVUW |
|
* |
+*//* |
QTVUW |
|
) |
+*//*) |
QTVUW |
|
P |
+*//*) |
QTVUWP |
|
^ |
+*//*)^ |
QTVUWP |
|
O |
+*//*)^ |
QTVUWPO |
|
( |
+*//* |
QTVUWPO^ |
|
+ |
++ |
QTVUWPO^*//* |
|
N |
++ |
QTVUWPO^*//*N |
|
* |
++* |
QTVUWPO^*//*N |
|
M |
++* |
QTVUWPO^*//*NM |
|
- |
++- |
QTVUWPO^*//*NM* |
|
L |
++- |
QTVUWPO^*//*NM*L |
|
+ |
++-+ |
QTVUWPO^*//*NM*L |
|
K |
++-+ |
QTVUWPO^*//*NM*LK |
|
QTVUWPO^*//*NM*LK+-++ |
The above expression, i.e., QTVUWPO^*//*NM*LK+-++, is not a final expression. We need to reverse this expression to obtain the prefix expression.
Rules for the conversion of infix to prefix expression:
- First, reverse the infix expression given in the problem.
- Scan the expression from left to right.
- Whenever the operands arrive, print them.
- If the operator arrives and the stack is found to be empty, then simply push the operator into the stack.
- If the incoming operator has higher precedence than the TOP of the stack, push the incoming operator into the stack.
- If the incoming operator has the same precedence with a TOP of the stack, push the incoming operator into the stack.
- If the incoming operator has lower precedence than the TOP of the stack, pop, and print the top of the stack. Test the incoming operator against the top of the stack again and pop the operator from the stack till it finds the operator of a lower precedence or same precedence.
- If the incoming operator has the same precedence with the top of the stack and the incoming operator is ^, then pop the top of the stack till the condition is true. If the condition is not true, push the ^ operator.
- When we reach the end of the expression, pop, and print all the operators from the top of the stack.
- If the operator is ')', then push it into the stack.
- If the operator is '(', then pop all the operators from the stack till it finds ) opening bracket in the stack.
- If the top of the stack is ')', push the operator on the stack.
- At the end, reverse the output.
Pseudocode of infix to prefix conversion
Function InfixtoPrefix( stack, infix)
infix = reverse(infix)
loop i = 0 to infix.length
if infix[i] is operand → prefix+= infix[i]
else if infix[i] is '(' → stack.push(infix[i])
else if infix[i] is ')' → pop and print the values of stack till the symbol ')' is not found
else if infix[i] is an operator(+, -, *, /, ^) →
if the stack is empty then push infix[i] on the top of the stack.
Else →
If precedence(infix[i] > precedence(stack.top))
→ Push infix[i] on the top of the stack
else if(infix[i] == precedence(stack.top) && infix[i] == '^')
→ Pop and print the top values of the stack till the condition is true
→ Push infix[i] into the stack
else if(infix[i] == precedence(stack.top))
→ Push infix[i] on to the stack
Else if(infix[i] < precedence(stack.top))
→ Pop the stack values and print them till the stack is not empty and infix[i] < precedence(stack.top)
→ Push infix[i] on to the stack
End loop
Pop and print the remaining elements of the stack
Prefix = reverse(prefix)
return
0 Comments