Infix ,prefix and postfix notation in DSA with C

 1. Infix Notation

Definition:

In infix notation, the operator is placed between the operands. This is the most commonly used

notation in arithmetic expressions.

Example:

• A + B

• A * (B + C)

Order of Operations:

• Operators are evaluated according to their precedence (e.g., multiplication before addition).

• Parentheses () are used to change the order of evaluation.

Basic Example:

In the expression A + B * C:

• According to the operator precedence, multiplication is done before addition, so it's

equivalent to A + (B * C).

Conversion of Infix to Postfix/Prefix:

Infix expressions must be converted to either postfix or prefix notation for easier computation by

computers.

2. Prefix Notation (Polish Notation)

Definition:

In prefix notation, the operator is placed before the operands.

Example:

• + A B (Equivalent to A + B in infix)

• * + A B C (Equivalent to (A + B) * C in infix)

Order of Operations:

• The operator appears before its operands.

• This means the operator is evaluated first, followed by its operands.

Conversion of Infix to Prefix:

The rules for converting infix to prefix are:

• Reverse the expression (reverse the order of operands and operators).

• Convert the reversed expression to postfix.

• Reverse the postfix expression to obtain the prefix.

Example Program:

Here’s an example in Python to convert an infix expression to prefix:

def precedence(c):

if c == '+' or c == '-':

return 1

elif c == '*' or c == '/':

return 2

elif c == '^':

return 3

return 0

def infix_to_prefix(expression):

expression = expression[::-1]

stack = []

output = []

for char in expression:

if char.isalnum():

output.append(char)

elif char == ')':

stack.append(char)

elif char == '(':

while stack and stack[-1] != ')':

output.append(stack.pop())

stack.pop()

else:

while (stack and precedence(char) < precedence(stack[-1])):

output.append(stack.pop())

stack.append(char)

while stack:

output.append(stack.pop())

return ''.join(output[::-1])

# Test the function

expression = "(A-B/C)*(A/K-L)"

print("Prefix expression: ", infix_to_prefix(expression))

3. Postfix Notation (Reverse Polish Notation)

Definition:

In postfix notation, the operator is placed after the operands.

Example:

• A B + (Equivalent to A + B in infix)

• A B C + * (Equivalent to A * (B + C) in infix)

Order of Operations:

• Operands are followed by operators.

• Each operator operates on the operands that appear immediately before it.

Conversion of Infix to Postfix:

The rules for converting infix to postfix are:

• If the current token is an operand, add it to the postfix expression.

• If the current token is an operator, pop operators from the stack to the output until you find

an operator with lower precedence or a left parenthesis. Then push the operator onto the

stack.

• If the current token is a left parenthesis (, push it onto the stack.

• If the current token is a right parenthesis ), pop operators from the stack until you encounter

a left parenthesis, which is discarded.

Example Program:

Here’s an example in Python to convert an infix expression to postfix:

def precedence(c):

if c == '+' or c == '-':

return 1

elif c == '*' or c == '/':

return 2

elif c == '^':

return 3

return 0

def infix_to_postfix(expression):

stack = []

output = []

for char in expression:

if char.isalnum():

output.append(char)

elif char == '(':

stack.append(char)

elif char == ')':

while stack and stack[-1] != '(':

output.append(stack.pop())

stack.pop()

else:

while stack and precedence(char) <= precedence(stack[-1]):

output.append(stack.pop())

stack.append(char)

while stack:

output.append(stack.pop())

return ''.join(output)

# Test the function

expression = "(A-B/C)*(A/K-L)"

print("Postfix expression: ", infix_to_postfix(expression))

Comparison of Infix, Prefix, and Postfix

Notation Example Order of Operations Parentheses

Needed? Advantages

Infix A + B *

C

Operators are evaluated

based on precedence Yes (for clarity) Most commonly used and

understood

Prefix + A * B

C

Operators appear first,

followed by operands No

No parentheses needed, easier

for compilers

Postfix A B C *

+

Operators appear after

operands No

No parentheses, easier for

machine evaluation

Applications:

1. Prefix and Postfix are easier for computers to evaluate:

o Computers don't need to worry about operator precedence or parentheses in these

notations.

o Commonly used in stack-based algorithms (evaluating expressions).

2. Postfix notation is used in various calculators:

o Reverse Polish Notation (RPN) is used in many calculators and some programming

languages for arithmetic expression evaluation.

3. Prefix notation is useful in certain compilers:

o Prefix expressions simplify parsing in compilers, where the operators precede

operands.