Converting Infix to Prefix Using Stack
1. Understanding the Terms:
• Infix Expression: An expression where operators are placed between operands (e.g., A + B).
• Prefix Expression: An expression where operators are placed before operands (e.g., +AB).
• Stack: A data structure that follows the Last In, First Out (LIFO) principle. Used to help
manage the conversion.
Steps for Converting Infix to Prefix
1. Reverse the Infix Expression:
o Reverse the entire infix expression.
o Convert opening parentheses ( to closing ) and vice versa.
2. Convert the Reversed Infix Expression to Postfix:
o Use the standard method of converting an infix expression to postfix using a stack.
o During this step, handle operators, operands, and parentheses.
3. Reverse the Postfix Expression:
o The resulting postfix expression from Step 2 is reversed to give the required prefix
expression.
Operator Precedence and Associativity Table
Operator Precedence Associativity
+, - 1 Left to right
*, / 2 Left to right
^ 3 Right to left
Example: Convert Infix (A+B)*(C-D) to Prefix
Step Action Stack Output
Reverse Input: (A+B)*(C-D)
Expression becomes (D-C)*(B+A)
Scan: ( Push ( to stack (
Scan: D Add D to output ( D
Scan: - Push - to stack (- D
Scan: C Add C to output (- DC
Scan: ) Pop until ( is found DC-
Scan: * Push * to stack * DC-
Scan: ( Push ( to stack (*( DC-
Scan: B Add B to output (*( DC-B
Scan: + Push + to stack (*(+ DC-B
Scan: A Add A to output (*(+ DC-BA
DC-BA
Scan: ) Pop until ( is found *
+
End of Pop remaining operators DC-BA
Expression from stack +*
Reverse Reverse the output to get *+AB-
Output prefix CD
Thus, the prefix expression is *+AB-CD.
EXAMPLE 2:- Given Infix - ((a/b)+c)-(d+(e*f))
