Infix, Prefix and Postfix

Infix, Prefix and Postfix

Infix, Prefix and Postfix

See complete series on data structures here:
   • Data structures  

In this lesson, we have described Infix , Prefix and Postfix notations which are ways of writing arithmetic and logical expressions. Infix notation is the most common way of writing expressions. Prefix and Postfix notations are other two ways that are good for machines because they can be parsed and evaluated easily. This is one important topic in computer science where we find application of stack data structure.

For practice problems and more, visit: http://www.mycodeschool.com

Like us on Facebook: https://www.facebook.com/MyCodeSchool

Follow us on twitter: https://twitter.com/mycodeschool


Content

0.28 -> Hello everyone. In this lesson we're going to talk about one important and
4.279 -> really interesting topic in computer science where we find application of
8.26 -> stack data structure,
9.65 -> and this topic is evaluation of arithmetic and logical expressions.
14.71 -> So how do we write an expression. I have written some simple arithmetic
19.09 -> expressions here.
20.08 -> An expression can have constants, variables
23.529 -> and symbols that can be operators or
26.65 -> paranthesis and all these components must be arranged
30.49 -> according to a set of rules, according to up grammer
34.13 -> and we should be able to parse and evaluate expression according to this
38.53 -> grammer
39.21 -> All these expressions that I had written here have
42.28 -> a common structure. We have an operator in between two operands.
47.11 -> Operand by definition is an object or value on which operation is performed.
52.17 -> In this expression 2+3, 2 and 3 are operands
56.39 -> and plus is operator, in the next expression
59.87 -> A and B are operands and - is operator,
63.02 -> in the third expression this asterisk is for multiplication operation so
68.27 -> so this is operator the first operand
71.78 -> P is a variable and a second operand 2
75.08 -> is a constant. This is the most common way of writing an expression,
79.82 -> but this is not the only way. This way of writing an expression in which we write
84.59 -> an operator in between operands is called
87.909 -> infix notation. Operand doesn't always have to be a constant or variable.
92.28 -> Operand can be an expression itself. In this fourth expression that I have written
97.479 -> here,
97.869 -> one of the operands of multiplication operator is an expression
102.14 -> itself, another operand is a constant We can have a further complex expression.
107.189 -> In this fifth expression that I have written here both the operands of
110.6 -> multiplication operator
112.009 -> are expressions. We have three operators in this expression here,
116.219 -> for this first plus operator P and Q these
119.79 -> variables P and Q are operands, for the second
124.13 -> plus operator we have R and S and for this multiplication operator
129.58 -> the first operand is this expression P + Q and the second operand
134.42 -> this expression R + S. While evaluating
138.28 -> expressions but multiple operators, operations will have to be performed in
142.709 -> certain order
143.83 -> like in the fourth example we will first have to perform
146.97 -> addition and then only we can perform multiplication. In this fifth expression
151.959 -> first we will have to perform these two additions and then we can perform the
155.58 -> multiplication.
156.42 -> We will come back to evaluation but if you can see in all these expressions
160.78 -> operator is placed in between operands.
163.93 -> This is the syntax that we are following. One thing that I must point out here.
168.84 -> Throughout this lesson, we're going to talk only about binary operators.
172.519 -> An operator that require exactly two operands is called
176.16 -> a binary operator. Technically we can have an operator that may require
180.12 -> just one operand or maybe more than two operands but we're talking only about
184.36 -> expressions with
185.33 -> binary operators. Okay so let's now see what are the rules we need to apply to
190.18 -> evaluate such expressions written in this syntax that we are calling
194.19 -> infix notation. For an expression with
197.409 -> just one operator there's no problem we can simply apply that operator.
201.76 -> For an expression with multiple operators and
204.76 -> no parenthesis like this, we need to decide an order
208.17 -> in which operator should be applied. In this expression
211.569 -> if we will perform the addition first then this expression
215.73 -> will reduced to 10 * 2 and will finally evaluate
220.09 -> as 20 but if we will perform the multiplication first
224.47 -> then this expression will reduce to
227.81 -> 4 + 12 and would finally evaluate to
231.04 -> 16. So basically, we can look at this expression in two ways.
235.43 -> We can say that operands for addition operator are 4 and 6
239.519 -> and operands for multiplication are this expression 4 + 6
244.209 -> and this constant 2 or we can say that all operands for multiplication are 6
249.959 -> and 2 and operands for addition operation are four and this expression
255.11 -> 6 * 2.
256.28 -> There is some ambiguity here but if you remember your high school mathematics
260.509 -> this problem is the resolved by following operator precedence rules
265.55 -> In an algebraic expression this is the precedence that we follow.
269.27 -> First preference is given to paranthesis or brackets,
272.79 -> next preference is given to exponents. I'm using this symbol for exponent
277.66 -> operator so if I have to write
279.479 -> 2^3, I'll be writing it something like this.
283.13 -> In case of multiple exponentiation operator,
286.33 -> we apply the operators from right to left,
289.44 -> so if I have something like this then first
292.75 -> this right most exponentiation operator will be applied.
296.009 -> So this will reduce to 512.
300.12 -> If you will apply the left operator first, then this will evaluate to 64.
304.94 -> After exponents, next preference is given to multiplication and division
308.979 -> and if it's between multiplication and division operators then
312.669 -> we should go from left to right. After multiplication and division we have
316.46 -> addition and subtraction
318.22 -> and here also we go from left to right. If we have an expression like this
322.889 -> with just addition and subtraction operators, then we will apply
326.63 -> leftmost operator first
328.52 -> because to precedence of these operators is same and this will evaluate to 3.
333.289 -> If you will apply the plus operator first this will evaluate
336.52 -> as 1 and that will be wrong.
339.18 -> In the second expression 4 + 6 * 2 that I had written here
342.7 -> if we will apply operator precedence then multiplication should be performed
347.03 -> first,
347.78 -> if we want to perform addition first then we need to write this
351.54 -> 4 + 6 within parenthesis and now adddition will be performed first
356.24 -> because
356.97 -> precedence of parenthesis is greater. I'll example of another complex
361.77 -> expression and try to evaluate it,
363.67 -> just to make things further clear. So I have an expression here. In this expression we
367.93 -> have four operators
369.31 -> one multiplication and one division one subtraction and one
372.6 -> addition. Multiplication and division have higher precedence
375.74 -> between these two multiplication and division
379.1 -> which have seen precedence, we will pick the left one first.
382.69 -> So we will first reduced this expression like this and now we will perform the
387.26 -> division
387.96 -> and now we have only subtraction and addition.
391.36 -> So we will go from left to right and this is what we will finally get.
395.43 -> This right to left and left to right rule that i have wriiten here
398.84 -> for operators with equal precedence is better termed as operator associativity.
404.13 -> If in case of multiple operators with equal
407.41 -> precedence we go from left to right then we say that operators are
411.44 -> left associative and if we go from right to left
415.29 -> we say that operators are right associative.
418.42 -> While evaluating an expression in infix form, we first need to look at
422.19 -> precedence
423.07 -> and then to resolve conflict among operator with equal precedence,
427.59 -> we need to see associativity. All in all you need to do so many things just to
432.66 -> parse and evaluate an
434.26 -> infix expression. The use of parenthesis becomes really important
437.77 -> because that's how we can control to order in which operation should be
441.68 -> performed.
442.3 -> Paranthesis add explicit intent that operations should be performed in this
446.78 -> order
447.32 -> and also improved readability of expression.
450.51 -> I have modified this third expression, we have some parenthesis here now,
454.72 -> and most often we write infix expressions like this only
458.82 -> using a lot of paranthesis. Even though infix notation is the most common
464.08 -> way of writing expressions.
465.51 -> It's not very easy to parse and evaluate an infix expression without ambiguity,
470.47 -> so mathematicians and logicians studied this problem
474.3 -> and came up with 2 other ways of writing expressions
477.89 -> that are paranthesis free and can be passed without ambiguity
482.3 -> without requiring to take care of any of these operator precedence or
486.46 -> associativity rules,
487.729 -> and these two ways are postfix and prefix notations.
491.729 -> Prefix notation was proposed earlier
494.96 -> in your 1924 by Polish logician.
498.31 -> Prefix notation is also known as polish notation.
501.76 -> In prefix notation, operator is placed before
505.33 -> operands. This expression 2 + 3 in
508.49 -> infix will be written as + 2 3 in prefix.
512.65 -> Plus operator will be placed before the two operands
515.979 -> 2 and 3. P - Q will be written as
519.26 -> - P Q. Once again just like infix notation, operand in prefix notation
523.8 -> doesn't always have to be a constant and variable,
527.93 -> operand can be a complex prefix notation itself.
531.3 -> This expression A + B * C in infix form
535.69 -> will be written like this in prefix form. I'll come back to how we can convert
540.21 -> infix expression to prefix.
541.79 -> First have a look at the third expression in prefix form,
544.81 -> for this multiplication operator the 2 operands are
548.63 -> variables B and C and the three elements are in prefix syntax.
553.589 -> First we have to operater and then we have the two operands. The operands for
557.74 -> addition operator are variable A and this prefix expression
562.61 -> asterisk B C. In infix expression, we need to use parenthesis because
567.839 -> and operands can possibly be associated with
571.16 -> 2 operators, like in this third expression in infix form B can be
575.55 -> associated with
576.5 -> both plus and multiplication.
579.7 -> To resolve this conflict we need to use operator precedence and associativity
584.02 -> rules,
585.24 -> or use parenthesis to explicitly specify
588.99 -> association but in prefix form and also in Postfix form that we will discuss in
594.37 -> some time.
595.17 -> An operand can be associated with only one operator
598.52 -> so we do not have this ambiguity, while parsing and evaluating
602.61 -> prefix and postfix expressions we do not need extra information
607.35 -> we do not need all the operator precedence and associativity rules.
611.49 -> I'll come back to how we can evaluate prefix notation. I'll first define postfix
615.79 -> notation.
617.41 -> Postfix notation is also known as reverse polish notation.
621.07 -> This syntax was proposed in 1950s by some computer scientists.
625.8 -> In postfix notation operator is placed after operands.
629.93 -> Programmatically, postfix expression is easiest to
633.06 -> parse and least costly in terms of time and memory
636.67 -> to evaluate, and that's why this was actually invented.
640.53 -> Prefix expression can also be evaluated in similar time and memory
644.93 -> but the algorithm to parse and evaluate postfix expression is
649.77 -> really straightforward and intuitive and that's why its preferred for computation
654.45 -> using machines.
655.86 -> I'm going to write postfix for these expressions that had written earlier
659.57 -> in other forms this first expression
662.7 -> 2 + 3 in Postfix will be 2 3 +.
666.37 -> Two separate the operands we can use a space or some other delimiter
670.48 -> like a comma, that's how you would typically store prefix or postfix
675.81 -> in a string When you'll have to write a program.
679.41 -> this second expression in postfix will be P Q -.
683.6 -> So as you can see in Postfix form we are placing the operator
687.01 -> after the operands. This third expression in Postfix will be
691.89 -> A B C * and then +.
694.95 -> For this multiplication operator, operands are variables B and C
699.64 -> and for this edition, operands are
702.93 -> variable A and this postfix expression B C *.
708.35 -> We will see efficient algorithms to convert infix to prefix or postfix
713.19 -> in later lessons. For now let's not bother how we will do
716.32 -> this in a program, let's quickly see how we can do this manually.
720.38 -> To convert an expression from infix to any of these other two forms,
724.38 -> we need to go step-by-step just a way we would go in evaluation
729.1 -> I have picked this expression A + B * C in
732.67 -> infix form. We should first convert the part that should be evaluated first,
737.35 -> so we should go in order of precedence. We can also first
741.12 -> put all the implicit parenthesis. So here we will first convert this B * C
747.02 -> so first we are doing this conversion for multiplication operator, and then
751.03 -> we will do this conversion for addition operator.
754.17 -> We will bring addition to the front, so this is how the
758.23 -> expression will transform. We can use parenthesis and
761.78 -> in intermediate steps and once we had done that all the steps
766.01 -> we can erased a parenthesis.
769.16 -> Let's now do the same thing for postfix, we will first do the conversion for
774.22 -> multiplication operator and then in next step
778.11 -> we will do it for addition and now we can get rid of
782.04 -> all the parenthesis. Parenthesis
785.16 -> surely adds readability to any of these expressions
789.079 -> to any of these forms but if we are not bothered about human readability,
793.87 -> then for a machine we are actually saving some memory
797.089 -> that would be used to store paranthesis information.
800.35 -> Infix expression definitely is most human readable,
803.5 -> but we prefix and postfix are good for machines.
807.11 -> So this is infix, prefix and postfix notation for you.
810.28 -> In next lesson, we will discuss evaluation of prefix and postfix
814.11 -> Notations.
815.089 -> This is it for this lesson. Thanks for watching.

Source: https://www.youtube.com/watch?v=jos1Flt21is