Data structures and Algorithms_Notations-1

Arithmetic notations in Algorithms

Explanation of infix, prefix and postfix notations along with Algorithm to convert Infix to Postfix

This is where maths stops mathing

You might think (like I did) , how can you change representation of basic mathematical functions and operations? A very simple answer to this question -

The data scientist decided to make a new way of representation to make it easier for the computer to deal with maths. (They definitely didn’t consider the issues it causes humans 🤣)

INFIX NOTATION

This is how we ,in daily life, represent mathematical expressions. The operator ( +, — , *) is placed in between the operands. Egs 5+6.

Similar to BODMAS used in maths, the order of precedence used in computer langauges are :-

Operation precedence

1. Exponentiation (^)
2. Multiplication (*) and Division (/)
3. Addition (+) and Subtraction(-)

In case of same level of precedence — we need to do the operation from left to right.

Okay, now easy part over. Let’s start the real game.

PREFIX NOTATION

This is also called Polish Notation. Here the operator is mentioned before the operand.

Examples of prefix notation

POSTFIX NOTATION

This is called Reverse Polish Expression. Here the operators are places after the operands.

Example of postfix

We generally prefer postfix notation because it leads to less number of scannings (less time wastage) by the computer. The computer generally scans from left to right, so having the variables (and assigning their values) first then performing operations is the most ideal situation which is achieved by post fix notation.

The computer generally computes in two steps

1. Convert the infix input into postfix
2. Compute the postfix output

Transforming Infix to Postfix Notation

Example :-

(A+B)*C/D

1. [AB+]*C/D
2. AB+C*/D
3. AB+C*D/

(Q/W+R)+(E+F)

1. [QW/+R]+[E+F]
2. [QW/R+]+[EF+]
3. QW/R+EF++

Algorithm

1. A general algorithm to convert an infix expression without parenthesis into post fix expression

Preference

• +,- (addition, subtraction) assigned 1
• *,/ ( multiplication, division) assigned 2
• a,b,c…(variables) assigned 3
• # (hash) assigned 4

What we want to do -

1. Intialise stack contents (the expression elements) to the special symbol # ( this helps start the process, the # symbol acts like a start point)
2. Scan the leftmost symbol in the given infix expression and denote it as the current input symbol ( assign the left most symbol to another variable called CIS — Current Input Symbol. )
3. Repeat through step 6 while current input symbol is not #
4. Remove an output of all stack symbols whose precedence values are greater than or equal to the precedence of current input symbol ( this line is slightly confusing ik, this will be explained in detail in an example)
5. Push the correct input symbol onto the stack
6. Scan the leftmost symbol in the infix expression and let it be the current input symbol. (takes us back to step 2)

In conclusion

1. PUSH (#)
2. Scan Left most symbol
3. If Current Input symbol != #
4. then check is preference scanned symbol ≥ preference of current input symbol
5. If yes then PUSH (Current input symbol)
6. SCAN Left most symbol ( this will bring you back to 2nd step)
7. Remove all elements from stack (in the end)

Example :-

source: pepinsta

Final Algorithm

1. [Initialise the stack, TOP is Top of stack ]

TOP = 1

S[TOP] = ‘#’

2. [Initialise output string POSTFIX and set rank count]

POSTFIX = ‘ ‘ // We don’t the exact elements in the output so leave it empty

RANK = 0

3. Get first input symbol (or CIS)

NEXT = NEXTCHAR(INFIX)

4. Repeat through step 6 when NEXT != #

5. Repeat while f(NEXT) ≤ f (S[TOP]) // Checks whether precedence of stack elements are more than the CIS — Step 5 in the before mentioned explanation

TEMP = POP (S,TOP) // If above statement is true then it pops (removes) the elements which higher precedence from stack and places it into TEMP (a temporary storage)

POSTFIX = POSTFIX + TEMP ( pushes it into the output stack)

RANK = RANK +r(TEMP)

If RANK <1 , then print “Invalid”

Exit

6. [Push current symbol into stack and move onto next symbol]

Call PUSH(S,TOP,NEXT)

NEXT = NEXTCHAR(INFIX)

7. [Remove remaining elements from stack]

// Now that all the major elements are pushed to output from the 5th step, Remaining elements which are present — might include the operators mostly) need to be pushed finally into the output stack

While S[TOP] != #

TEMP = POP(S,TOP)

POSTFIX = POSTFIX +TEMP

RANK = RANK +r(TEMP)

If RANK <1 , then print “Invalid”

Exit

8. [check if valid expression received]

If RANK = 1

Write “Valid”

Else write “Invalid”

— — — END — — —