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.
Achieve better academic results with professional writing support tailored to your needs. Whether you're facing tight deadlines or challenging assignments, our expert writers deliver high-quality, original, and well-researched coursework across various subjects. Coursework writing service Canada is trusted by students for timely delivery, affordable pricing, and plagiarism-free content that meets university standards. Improve your grades with reliable assistance, personalized solutions, and dedicated customer support designed to make your academic journey easier and more successful.
ReplyDelete