Infix to Prefix notation Algorithm and Flowchart

[11224 views]

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

Remove WaterMark from Above Flowchart

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: Else, 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. 3.4.2: Else, 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 notation. 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),