The Concept of Operator Precedence

Operator precedence is a fundamental concept in mathematics and computer science that determines the order in which operations are performed when multiple operators are present in an expression. In general, multiplication takes precedence over addition, meaning that in the expression "a + b × c," the multiplication operation is evaluated first, followed by the addition operation.

The Notation Used

A specific notation called Reverse Polish Notation (RPN) or Postfix Notation is used to represent expressions in a way that eliminates operator precedence issues. In RPN, operators are written after their operands, rather than before them. For example, the expression "a + b × c" would be represented as "(a b ×) + c," where the parentheses indicate the order of operations.

The Rule for Interpreting Reverse Polish Notation

When interpreting RPN expressions, a specific rule is applied: if an operator is encountered, the number of operands that operator requires must be determined. The operands are then removed from the expression in the order they were pushed onto the stack. Once the correct number of operands has been used, the operation is performed and the result is pushed back onto the stack.

In the example given, the expression "(a b ×) + c" would be interpreted as follows: the "×" operator requires two operands, so the operands C and B are removed from the stack and multiplied together. The result of this operation, which represents the value of B times C, is then pushed back onto the stack. Finally, the "+" operator requires one operand, which is A, to be added to the result of the previous operation.

The Role of Stacks

In RPN expressions, a stack plays a crucial role in evaluating the expression. The stack is used to temporarily store operands while they are being processed by operators. When an operator encounters an operand on top of the stack, it takes that operand off and uses it for the calculation. This ensures that each operation is performed using the correct number of operands.

The Example

To illustrate the concept of RPN further, let's consider an example expression: "(a b +) × c". In this case, there are two operands (A and B), so they are removed from the stack and added together. The result of this operation is then pushed back onto the stack, and the "×" operator requires one more operand (C). Therefore, C is removed from the stack, multiplied by the result of the previous operation, and the final answer is pushed back onto the stack.

Reverse Polish Notation and Its Relation to Stacks

The use of stacks in RPN expressions was a significant innovation in computer science. In the late 1940s and early 1950s, computer scientists were exploring new ways to represent and evaluate mathematical expressions. They realized that by using a stack to store operands, they could eliminate operator precedence issues entirely.

This approach related closely to another important concept in computer science: the stack data structure. A stack is a storage mechanism that consists of a set of elements, called items, which are added and removed from the top of the stack. In RPN expressions, each item on the stack represents an operand that has been pushed onto the stack by the current operator.

The Relation Between Reverse Polish Notation and Trees

Reverse Polish Notation is also closely related to tree data structures. A tree is a hierarchical structure consisting of nodes, where each node represents a value or an operation. In RPN expressions, the tree-like structure of the expression is reflected in the stack. Each item on the stack represents a leaf node in the tree, while operators represent internal nodes.

The Use of Disks to Visualize Stacks

To illustrate the concept of stacks more clearly, a set of disks are used to visualize the process of pushing and popping items onto the stack. The disks are labeled with different numbers, which correspond to different operands or intermediate results. This visual representation helps to make it clear how the stack operates.

The Rule for Interpreting Reverse Polish Notation on a Stack

To interpret RPN expressions using a stack, the following rule is applied: when an operator encounters an operand, it takes that operand off the stack and uses it for the calculation. Once the correct number of operands has been used, the operation is performed and the result is pushed back onto the stack.

The Example Using Disks

To illustrate this rule using disks, consider the expression "a + b × c". The disks are labeled with different numbers, which correspond to different operands or intermediate results. When the "+" operator encounters an operand on top of the stack, it takes that operand off and uses it for the calculation. In this case, the "+" operator takes the disk labeled "c" off the stack, multiplies it by the disk labeled "b", and pushes the result back onto the stack.

The Importance of Stacks in Reverse Polish Notation

In conclusion, stacks play a crucial role in evaluating RPN expressions. By using a stack to store operands while they are being processed by operators, operators can ensure that each operation is performed using the correct number of operands. This approach eliminates operator precedence issues entirely and provides a clear and efficient way to represent and evaluate mathematical expressions.

The Relation Between Reverse Polish Notation and Tree Data Structures

In addition to its role in evaluating expressions, RPN is also related to tree data structures. The hierarchical structure of the expression is reflected in the stack, with each item on the stack representing a leaf node in the tree. This relationship between RPN and trees highlights the importance of stacks as a fundamental data structure in computer science.

The Impact of Reverse Polish Notation on Computer Science

The development of RPN expressions had a significant impact on the field of computer science. It provided a new way to represent and evaluate mathematical expressions, which eliminated operator precedence issues entirely. This approach has been widely adopted in various areas of computer science, including compiler design, programming languages, and computational complexity theory.

In summary, reverse Polish notation is a fundamental concept in mathematics and computer science that uses a stack to evaluate expressions without operator precedence issues. The use of stacks to store operands while they are being processed by operators ensures that each operation is performed using the correct number of operands. This approach has had a significant impact on the field of computer science, providing a clear and efficient way to represent and evaluate mathematical expressions.

"WEBVTTKind: captionsLanguage: enWe want to talk in some depth about this language called Postscript and how important it isbut it's in the very nature of Postscript that it uses anotation called Postfix andthat in turnrelies for its executionrnvironment on this notion of a stack.Now we haven't covered stacks so far in computerphileSo before getting into postscript full-blown as it were I have got to tell you something about stacksAnd we may be in a position to put this out as a separate film in its own rightDoing a bit about stacks first of all mentioning postscript from time to timeBut it's important that you realize that stacks have a much wider applicationin computer science than just PostscriptA plus BWhat could be more commonplace than that in any language that you program then and that plus in the middle is an operatorIt takes in this case a couple of operands it combines them together it does the additionSo these of course things like plus minus multiply divide raise the power of our examples of arithmeticoperators, but they need theOperands to work onnotice that the operator the addition comes in between theOperands the a and the B and because it's inserted and inscribed inside the two operandsThat's why this is called an inner fixUse well, we're all very familiar with inner what we taught at high school and what we use most of the timeIt's perfectly possible to write like that using a prefix plus. say plus a bThat's prefix notationBasically if you read it out, you're saying add together a and Byeah, you're putting the plus at the start so it precedes the operands so it's prefix andJust to make it clear that this is something you are familiar with sometimes if you have a language that definesaddition not so much with an operator, but with afunction call you say add add a comma b and theArguments or the operands are in parentheses? What happens if you write it so that it comes?after the Operands ah we're here at last this is Postfix aGentleman who was a mathematical logician from poland called spelling right? think his name is pronounced on likebecause that becomes a faint soft w sound with the crossbar he was aMathematical Logician and what he said was do you know if I write stuff out like this as either?Prefix or PoStfixIt's so much easier me prove mathematical theorems with tell youNet result of all this was that people being unable to pronounce his name correctly and getting all the stresses and accents wrongDecided that rather than pronouncing what they found hard they would call thisPolish notationNow actually polish notation applies to using anything that isn't in fixed I've seen prefix notation being calledForward Polish notation I've seen this a B-Plusgiven its traditional name or ofreversePolish notationBut that's where it came from the gentleman who invented itsometimes this is evenAbbreviated to a thing you may also have seen reverse polish notationIt saves the interpreter or the compiler an awful lot of effort in actuallyExecuting the expressions that you write write down. Let's keep very simple again plus bIf write a plus bLike that and let's say, we'll see what the C language compiler would do to itWhat would they have to do to it? How would it translate it into binary?I don't want to do strings of meaning as binary with youBut I'll tell you what I will do I'll try and translate as if I was the C compiler into assembly codenow the assembly code will depend on whether on an arm chip and intel chip or whatever andSome of you will know the GCC compilergives a flag on there as well an option which says show me the assembler code that you would produce for this andHere goes. I'm making this up it might not correspond to any particular assembly you know, but I hope you'll get the ideaLoad register R1aThe compiler will store off the values of a and b in memory, but as you all know before they can be added togetherThey've got to be lifted into the central processor unit of the computerAnd then when they're added you call up the arithmetic unit inside the CPU load register commandRegister - this time with BaddWhat is in register - what is in register 2 and put the answer in Register 3?Roughly similar to the last assembler language. I taught which was for the arm chip don't castigate here forgot some of the details wrongBut I hope that's just to give you the ideaJust look at what it has to do it has to get a get bAnd do the additionYou have to do it that way because you can't do anything with something until you get them first and lift it into the cPUAnd put it in registersJust look at this what it does it gets a into a register it gets B into another register. It adds them together putsthe answer somewhere in the third register aB add a its Postfix notationFor even more complicated things it has to convert it into reverse polishexplicitly or implicitly in order to decide what code to generate andWhat the cache of it's really loved about this absolutely it was ace when he discovered it is the followingSuppose we now write a plus b. Star C. Which one of these addition or multiplicationoperators takes precedence answer it's the multiply the multiply must be done first everybody knows that andIf you don't want it to be done first you have toDeliberately force it to be done the other waySo let's be clear this one says multiply the b by CBecause multiply is more powerful than ad and when you've got the answer there add it to a this oneSays I want you to add a and B, and then multiply by C. What will cash of each said this is fantasticHe said in my proofsI hate parentheses they mess things upBut you realize that you don't have to parentheses because in reverse polishthis comes out to be a b cStar PlusWhereas this one comes out to be a b plus CStar telling you that a plusTimes C or to translate that in Postfix reverse Polish whatever you want to call itThe reason it does you've got to be careful hereLet me remind you of what will all have been taught at high schoolIs that multiply is a stronger operator than add?multiplication takes precedence as the phrase goesso in here to get the right answer you multiply b times C first of all andThen you do the add because it's of lower precedenceSo if all these are fives a being say they all represent the number 5 you get 5 times 5 is 2525 plus 5 is 30 way that this is represented in a reverse polish is as follows aand the way that this works is when you get an operator it is going to apply to the each fooimmediatelyPreceding operands because that's what those fix is all about the more you look at that the more you realizeAnd computer scientists when they looked at reverse polish notation in the late forties and early fiftiesJust thought all their christmases have come up once not only was this what we need did forCompiling stuff and getting use of usage of registers and cpus absolutely, right?But also, it related very much to a data structure that they're in the process of realizing its powerthe stackNow there's a lot of computer science depends on stackssometimes think that stacks and trees is just about all computer science is about but it's the first time we've mentioned themI think on computer file, so I'll try and go very very gently with you about this. This is a stackWhy is it a snack? It's a start because you can push things on itI'm going to push something else on to the top of the stackNotice that I can only access things by taking them off this RodSo therefore, it's a last thing in first thing outStorage mechanism, I'm going to push the lightAble to stack with three objects on itThe only easy one to get out is the top of the stack and if I take it off like that?That's called popping a stackSo you push it on the top and you pop the top of the stack like that?Let's be clear in all of this I shall be doing now with disks and stacksI'm using these disks here to be ofdifferent sizesSimply so you can see which is which on the stack. I'm producing. There's noImplication that the biggest disk represents the biggest integer or anything like thatI'll try and be clear as I as I go along as to which one represents a which one represents BWhich one represents C or maybe which one represents some partial?Intermediate result William multiplied two things together or whatever so don't get mesmerizedToo much by the size of these this is a case where size doesn't matter just got to remember which is whichWell if we're pushing and popping then how does that relate to this?reverse Polish this Postfix for that expression let's call this big one here the aAnd on to push a so the rule then for interpreting reverse polish notation is if it's an operand push it on the stackBe is that an operand yes, push it on the stackSee another operand push it on the stacknext onemultiply our well the rule about interpreting reverse polish on a stack is to say ifYou hit an operatorThink to yourself how many operands does this got then take them off the stack those two operands in this case?Do the operation and push the answer back so I take off C and I take off it BMultiply them together so I've got a b times C intermediate result now which I represent with this smaller one hereremember this one is the b times C sub of result andHaving done that multiply the rule is push the intermediate answer back on the stack?Coming to the end of the reverse polish string here. You'll see as a final plus. What does plus mean plus means it'sExpects two operands, and we're fortunate we've got it, rightThere's two things on the stack as our original a and as the intermediate result that we've pushed back on of doing BTimes C. So for the plus you take them both offYou do an ad like thatyou produce the final answer which is this very small disk here andIn postscript and in most of the systems when you've got the final answer you leave it at the top of the stack like thatso the answer for a plus b times C has beenevaluated using a stack and reverse polish and the final answer has appeared on top of the stack, sointerpreted languages with expressions of this sortreverse PolishPostfix is its other name don't forget and stacks. They just go together perfectlyThey were built in heaven for one another without a questionYou've got a third a third a third we have coped with thatWe've cope with that if you get a choice of either that pair or that pair of thirdsdoesn't matter which actually okay, so now we've got one sort of list\n"