This post is completed by 1 user

  • 0
 Add to List
Medium

371. Convert Infix to Prefix Expression

Objective: Given an Infix expression, write an algorithm to convert it into Prefix expression.

Example:

Input: Infix expression - A + B
Output: Prefix expression- +AB

Input: Infix expression - A+B*(C^D-E)
Output: Prefix expression- +A*B-^CDE

Approach: Use Stack

  • Operator stack: This stack will be used to keep operations (+, -, *, /, ^)

Order of precedence of operations-

  1. ^ (Exponential)
  2. / *
  3. + -

Note: brackets ( ) are used to override these rules.

Algorithm:

  • Reverse the given infix expression. ( Note: do another reversal only for brackets).
  • Do Infix to postfix expression and get the result.
  • Reverse the result to get the final expression. (prefix expression) .

please click here to read about Infix expression to postfix expression.

Please see the walkthrough of an example below for more understanding.

Output:

Infix Expression: A+B*(C^D-E)
Prefix Expression: +A*B-^CDE

Related Problems: