Infix notation is a type of notation in which arithmetic expressions are normally written.
Prefix notation is a type of notation in which arithmetic expressions are written in a manner such that the operands appear after their operators.
Flowchart for converting Infix to Prefix notation
Algorithm for conversion of Infix to Prefix notation:
Step 1: Start
Step 2: Reverse the infix expression
Step 3: Obtain the postfix form
3.1:Start reading the infix expression from left to right.
3.2: Repeat Step 3.3 to 3.6 for each element until the Stack is empty.
3.3: If we scan a operand we output it, print it.
3.4.1: If the scanned operator is greater in precedence than the
operator in the stack or if the stack is empty or the stack
contains a "(", push it.
Pop all the operators having greater or equal precedenc
that of the scanned operator. After doing that Push
the scanned operator to the stack. In case there is a
parenthesis while popping then stop and push the scanned
operator in the stack.
3.5: If a '(' is encountered, push it onto Stack.
3.6: If a ')' is encountered, repeatedly pop from Stack and output it
until a '(' is encountered.3.7: The output is printed in postfix
Step 4: The expression formed is in postfix form, reverse it and print it,
this is the prefix form
Step 9: Stop
Let's take an example to understand a*(b+c),
- Reverse string :(c+b)*a
- Postfix form is obtained: cb+a*
- Reverse the postfix result: *a+bc
You might be interested in this too.:
Our Quiz prepared by Experts Helps you identify your knowledge in Algorithms. Everyone should atleast attempt this Quiz Once.