Infix notation is a type of notation in which arithmetic expressions are normally written.
Postfix notation is a type of notation in which arithmetic expressions are written in a manner such that the operands appear before their operators. Postfix notation is a notation used in the system and is implemented using stacks. There is often a need to convert Infix to Postfix notation, so let's understand how the conversion is done.
Flowchart for converting Infix to Postfix Notation:
Algorithm for conversion of Infix to Postfix Notation:
Step 1: Start
Step 2: Start reading the infix expression from left to right.
Step 3: Repeat Step 4 to 7 for each element until the Stack is empty.
Step 4: If we scan a operand we output it, print it.
Step 5: Else,
5.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 "(",
Pop all the operators having greater or equal precedence
than 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.
Step 6: If a '(' is encountered, push it onto Stack.
Step 7: If a ')' is encountered, repeatedly pop from Stack and output it
until a '(' is encountered
Step 8: The output is printed in postfix notation
Step 9: Stop
Let's take an example to understand a*(b+c),
- 'a' being an operand is scanned and printed.
- Then * is added to the stack. Again '(' is encountered and pushed in the stack.
- 'b' being an operand is scanned and printed.
- '+' being an operator is pushed into the stack.
- 'c' being an operand is scanned and printed.
- An ')' is encountered operator + is popped.
- Then, again top is popped and we print * and here, popping ends as the stack is empty.