Notations

Types of Notations : 

• Infix notation

• Prefix notation

• Postfix notation

Consider the sum of A and B. We think of applying the operator “+” to the operands A and B to write the sum as A+B. This particular representation is called Infix notation. There are two alternate notations for expressing the sum of A and B using the symbols A, B and +. These are

+ A B Prefix notation
A B + Postfix notation

The prefixes “pre-“, “post-“ and “in-“ refer to the relative position of the operator with respect to the two operands.

In Prefix notation the operator precede the two operands,
In Postfix notation the operator follows the two operands and
In Infix notation the operator is between the two operands.

The evaluation of the expression A + B * C, as written in standard infix notation, requires knowledge of which of the two operations, + or *, is to be performed first. In the case of + and *, we “know” that multiplication is to be done before addition (in the absence of parenthesis to the contrary). Thus A+B*C is interpreted as A + ( B * C ) unless otherwise specified. We say that multiplication takes precedence over addition. Suppose that we want to rewrite A + B * C in postfix. Applying the rules of precedence, we first convert the portion of the expression that is evaluated first, namely the multiplication. By doing this conversion in stages, we obtain :

A + ( B * C ) Paranthesis for emphasis
A + ( BC* ) Convert the multiplication
A ( BC* ) + Convert the addition
ABC*+ Postfix form

The only rules to remember during the conversion process are that operations with highest precedence are converted first and that after a portion of the expression has been converted to postfix, it is to be treated as a single operand. Consider the same example with the precedence of operators reversed by the deliberate insertion of parenthesis.

( A + B ) * C Infix form
( AB+ ) * C Convert the addition
( AB+ ) C * Convert the multiplication
AB+C* Postfix form

In the above example the addition is converted before the multiplication because of the parenthesis. In going from ( A + B ) * C to ( AB+ ) * C, A and B are the operands and + is the operator. In going from ( AB+ ) * C to ( AB+ ) C *, ( AB+ ) and C are the operands and * is the operator. The rules for converting from infix to postfix are simple, providing that you know the order of precedence.

ALGORITHM : Infix to Postfix

STEP 1 : Read the given infix expression into string called infix.

STEP 2 : Read one character at a time and perform the following operations :

1. If the read character is an operand, then add the operand to the postfix string.

 2. If the read character is not an operand, then check
        If the stack is not empty and precedence of the top of the 
           stack operator is higher than the read operator,
        then pop the operator from stack and add this 
               operator to the postfix string. 
        Else push the operator onto the stack.

STEP 3 : Repeat STEP 2 till all characters are processed from the input string.

STEP 4 : If stack is not empty, then pop the operator from stack and add this operator to the postfix
               string.

STEP 5 : Repeat STEP 4 till all the operators are popped from the stack.

STEP 6 : Display the result of given infix expression or resultant postfix expression stored in a string
              called postfix from this algorithm.

Infix to postfix expression - SOURCE CODE

Infix to Prefix Expression :Algorithm

STEP 1 : Read the given infix expression into string called infix.

STEP 2 : Reverse the infix string and read one character at a time and perform the following operations :

If the read character is an operand, then add the operand to the prefix string.
     If the read character is not an operand, then check
        If the stack is not empty and precedence of the top of the 
           stack operator is higher than the read operator,
       then pop the operator from stack and add this 
              operator to the prefix string. 
       Else push the operator onto the stack.

STEP 3 : Repeat STEP 2 till all characters are processed from the input string.

STEP 4 : If stack is not empty, then pop the operator from stack and add this operator to the prefix string.

STEP 5 : Repeat STEP 4 till all the operators are popped from the stack.

STEP 6 : Reverse the prefix string and display the result of the given infix expression or the resultant
              prefix expression stored in a string called prefix from this algorithm.

Infix to prefix expression - SOURCE CODE

 Postfix Expression :Algorithm

STEP 1 : Read the given postfix expression into a string called postfix.

STEP 2 : Read one character at a time & perform the following operations :
              1. If the read character is an operand, then convert it to float and push it onto the stack.
              2. If the character is not an operand, then pop the operator from stack and assign to OP2. Similarly, pop one
                   more operator from stack and assign to OP1.
              3. Evaluate the result based on operator x.
              4. Push the result (based on operator x) onto the stack.

STEP 3 : Repeat STEP 2 till all characters are processed from the input string.
STEP 4 : Return the result from this procedure or algorithm and display the result in main program.

Evaluation of a postfix expression