Infix

The document discusses infix and postfix notations for expressions. It explains that infix notation uses operators between operands, like 7+9, while postfix notation evaluates operators after operands. It then discusses rules for evaluating expressions based on operator precedence and provides examples of converting infix to postfix. Finally, it briefly explains the Tower of Hanoi puzzle and a recursive algorithm to solve it by dividing the disks into two parts and moving them in steps.

Uploaded by

AARAV KUMAR

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

19 views17 pages

Infix

Uploaded by

AARAV KUMAR

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

You are on page 1/ 17

INFIX & POSTFIX

Convert Infix to Postfix notation

• An infix and postfix are the expressions. An expression consists of
constants, variables, and symbols.
• Symbols can be operators or parenthesis.
• All these components must be arranged according to a set of rules so that
all these expressions can be evaluated using the set of rules.
Examples of expressions are:
7+9, A – B, (P * 5)
All the above expressions have a common structure, i.e., we have an
operator between the two operands.
An Operand is an object or a value on which the operation is to be
performed.
In the above expressions, 7, 9 are the operands while '+', '-', and '*' are the
operators.
(p + q) * (r + s)
• In the above expression, there are three operators.
• The operands for the first plus operator are p and q, the operands for
the second plus operator are r and s.
• While performing the operations on the expression, we need to
follow some set of rules to evaluate the result.
• In the above expression, addition operation would be performed on
the two expressions, i.e., p+q and r+s, and then the multiplication
operation would be performed.
Syntax of infix notation is given below:
• <operand> <operator> <operand>
• If there is only one operator in the expression, we do not require applying
any rule. For example, 5 + 2; in this expression, addition operation can be
performed between the two operands (5 and 2), and the result of the
operation would be 7.
• If the expression is :- 4 + 6 * 2
• If the plus operator is evaluated first, then the expression would look like:
10 * 2 = 20.
• If the multiplication operator is evaluated first, then the expression would
look like: 4 + 12 = 16
• The above problem can be resolved by following the operator precedence
rules.
• In the algebraic expression, the order of the operator precedence is given
in the table:
Evaluation of Postfix Expression

• The Postfix notation is used to represent algebraic expressions.

• The expressions written in postfix form are evaluated faster compared
to infix notation as parenthesis are not required in postfix.
Complexity :
• Time complexity : O(N) as we need to traverse N times.
• Space : O(N) as we are having n elements in stack data structure
There are the following limitations of the above implementation.

1) It supports only 4 binary operators ‘+’, ‘*’, ‘-‘ and ‘/’. It can be
extended for more operators by adding more switch cases.

2) The allowed operands are only single-digit operands. The program

can be extended for multiple digits by adding a separator-like space
between all elements (operators and operands) of the given
expression.
Tower of Hanoi
• Tower of Hanoi puzzle with n disks can be solved in minimum 2n−1
steps.
• This presentation shows that a puzzle with 3 disks has taken 23 - 1 = 7
steps
• So now, we can design an algorithm for Tower of Hanoi with more
than two disks.
• Divide the stack of disks in two parts.
• The largest disk (nth disk) is in one part and
• All other (n-1) disks are in the second part.
• The ultimate aim is to move disk n from source to destination and
then put all other (n-1) disks onto it.
• Now, apply the same in a recursive way for all given set of disks.
• The steps to follow are :-
• Step 1 − Move n-1 disks from source to aux.
• Step 2 − Move nth disk from source to dest.
• Step 3 − Move n-1 disks from aux to dest.