Just as a callout to people who learn alternatives such as PEMDAS and BIDMAS - the order of multiplication and division doesn't matter - they have the same precedence and are just done from left to right together. The same with addition and subtraction. You can swap M/D and A/S if you feel more comfortable that way, but these are within the scope of this video the only pairs that are interchangeable as of right now!
To add more context, division is just multiplication with a number between -1 and 1, just like subtraction is just addition with a number that is less than 0.
This is good but those rules are kind of arbitrary. It would be better to have an order of precedence list that can be 'modified' as per the grammar/language requirements, otherwise you get this monolithic structure which isn't easy to extend.
Exactly, and I would lump exponentiation in with other functions (or their equivalent symbology, such as |x| to means abs(x), or x! to mean factorial(x)), so that e^x-2 is exp(e, x)-2, but e^(x-2) would be exp(e, x-2); this makes sense in terms of computer programming where these are often in a library, like in C/C++. So the order of precedence becomes; parentheses, functions, multiplication/division in order from left to right, then finally addition/subtraction in order from left to right.
In school, we were taught "Please Excuse My Dear Aunt Sally" as the acronym for the order of operations. Also, another word for value is operand. For instance, in 4 + 5, the "+" is the operator and "4" and "5" are the operands.
My mind was blown when I combined Recursive Descent statement parsing and Pratt expression parsing constructed with compile time curried functions. Great analysis of this expression parsing algorithm!
I never knew that it was called the shunting yard algorithm. I still remember that creating a calculator was one of the first programs I had to write while studying 35 years ago.
25:50 The answer is 2 but not for the reason given: multiplication and division have the same priority so they are evaluated left-to-right, so: 1x(2+4)/3 = 1x6/3 = 6/3 = 2. The same for addition and subtraction.
Not yet, but it could. I've not mentioned "associativity" once in the video, and for good reason, it does introduce complexity to what is otherwise a very approachable algorithm. However we can't escape associativity should we need more interesting operators, which potentially disrupt the natural left to right bias of the solution stack. Interestingly, negation unary operator is contrary to this, but because we know it's the unary operator it's actually handled differently anyway during solving, but that might not always be the case moving forward.
@@AliceErishech You can see an error appearing at 15:22, where 1 + 2*4 - 3 + 5/6 * 2 + 6 - 1 - 4 + 7 is effectively parsed as 1 + 2*4 - (3 + 5/6 * 2 + 6) - 1 - (4 + 7) More simply, 1 - 2 + 3 would be computed to be -4 rather than 2, since it's parsed as 1 - (2 + 3).
@@javidx9Doesn't it already fail for 2 - 1 + 3 which should evaluate to (2 - 1) + 3 = 4, but instead evaluates to 2 - (1 + 3) = -2 because + has a higher precedence than -? Or am I not understanding something (a distinct and likely possibility)?
Powers are an interesting exception here though as they're evaluated right to left (or at least that's what I was taught - wikipedia and google's built in maths evaluation function seem to agree). So 2^2^3 = 2^(2^3) = 2^8 = 256, whereas if you go left to right you would get 64.
This video is priceless, thank you. A few observations- the brackets have higher precedence (i.e.3 plus) therefore the precedence of the subtraction operator becomes 3 plus by association with the brackets. You do not need to assume the bracket is 0... The brackets are made redundant at the point of output as no longer needed, as the order of the solve stack clarifies the order of operation at this point.
The master has returned. Always good to see amazing content with value from you and the community. Keep it up javid, and congratulations on X10 growing health:)
Familiar algorithm, well explained -- good job! One thing you might have added is why it's called the "shunting yard algorithm", because it can be explained by analogy to shunting railway wagons in a yard in such a way as to build a train in the necessary order. In that analogy, only one stack is generally used (though another is needed for evaluating the solution, though in fact it can be the same stack with a bit of cunning).
I teach this algorithm in an introductory data structures course. It's a fun algorithm that makes students "get" the importance of using appropriate data structures to solve problems (in this case, the stack). Great explanation, btw!
We called this postfix notation when I was learning compiler design - there's also a prefix way to do it. I believe we used an operator stack and a literal stack, but essentially the same process.
I once read about the shunting algorithm but couldn’t work out what was going on. Being able to visualise it with bits of paper is such a good way of explaining it - I get it now - thank you. Brilliant video 👍🙂
Thank you so much for this video, I've been really looking into how to create a programming language and this has helped me tremendously. Please do a whole series on how to lex, parse, compile/solve/interpret a language, really looking forward to this
I love your videos, but there is one thing getting me stuck from time to time - naming conventions. Could you please describe why do they differ so much? Once you create a variable using camelCase (e.g. stkHolding), then you create some other variable using snake_case (new_op), and also the operator struct is called sOperator (afaik structs are usually called with UpperCamelCase). Also, is there any reason of shortening variable/constant names? imo "stkHolding" is not as user-friendly as "stackHolding", especially if you watch the video in parts :)
Maybe I misunderstood the code but at 10:00 if '+' has higher precedence than '-' then wouldn't 1 - 2 + 3 be evaluated as 1 - (2 + 3)? That would be unusual, IME. Plus and minus normally have the same precedence and would be evaluated left-to-right.
@@vitoswat I think the problem exist only for addition and subtraction. Because in the case of 1-2+3 the minus can be translated (by humans) as unary minus and become 1+(-2)+3 and if we calculate now -2+3 first the rsult is correct. In division and multiplication there is no "sign" problem. Hence: 18*3/2 = 18*(3/2) = (18*3)/2 = 27 I think that operators (-) and (+) and should be labeled with the same precedence level, and the rule of popping operator in case that it is with higher precedence should be applied even on the same precedence. I would also mark (/) and (*) with the same precedence level.
Great work mate. If I had existed 10 years ago I would have had an easier time writing my compiler in college. I’m glad creators like yourself are out there.
Thanks for this. I have always used recursive descent when playing with parsing. I really enjoyed learning the shunting yard algorithm. I implemented this in Python using a regex tokenizer and output RiscV assembly instead on interpreting. So, where you made an interpreter with a compiler, I made a compiler with an interpreter.
A neat detail with the arity check could be to track, whenever either a constant gets pushed to the output stack or an operator gets flushed onto it, you'd be able to track the amount of "available" values there are lower in the stack -- thus the error could be localized better too.
Nice to see you again and thanks for the video. I've been studying splines not so long ago and was trying to make an extension for the unity editor to change values on the fly and immediately see the result in runtime. But the order of operations became something I couldn't overcome. My solution was very close to what you showed though. Thank you very much!
Amazing explanation as always, thanks a lot But a side note, without considering left-to-right evaluation unpredictable results will occur `1+1-1` & `1-1+1` Also waiting your approach for multiple digits numbers
I am really impressed with the teaching style and choice of difficult but important topics. Any chance you will try automatic differentiation (mainly applied in neural network training)? This is also kind of difficult but also interesting.
Great video! I used Recursive Descent rather than the Shunting Yard Algorithm to parse my programming language, as Recursive Descent was a bit simpler for me to implement in C and wrap my head around, since it just uses the function call stack :)
Absolutely facinating. As per usual @javidx9, I love the combination of your cool-as-a-cucumber delivery and exceptionally clear explanations. Your videos always distract from other side-projects I might be involved in, but it's always such a pleasure, I couldn't possibly complain :)
I love your channel and glad to see you again haven't seen in a while.... one thing though when I was in school (a long time ago now lol) I was taught the multiplication would only be done first if it was in a bracket. So 1+2*4-3 is actually the same as 3*4-3. I guess I was taught wrong and so for 30-40 years I would have just been giving the wrong answer if I was ever asked. The weird part is that hasn't really hurt me when making computer programs. I suppose this is why when I write code, I use the brackets a lot more than necessary.
I am wondering: for the unary operators you used the pass counter variable. Why not change the type of the initial value of the last symbol variable to unknown? That way your code would have been worked from the beginning without the pass counter variable.
I learned RPN when tinkering with the Jupiter Ace with its inbuilt FORTH programming language back in the eighties! A doomed computer if ever there was one!
When I learned to do this, I don't think I was told what it was called. Our assignment was to make a roman numerical calculator so we had an addition layer to tokenize roman numerials and calculate their value. It was fun, the teacher didn't require 'correct' roman numeral notation (i.e. VIIII counted as 9 rather than IX for 9), but I made it work both ways.
Sick dude. I implemented a "Countdown solver", you know, like TV show. It could solve the numbers game in Countdown. Implemented as an expression tree. I didn't use this shunting algorithm, but it would have worked great.
It would be much more fun to start solving what can be solved before you finish writing the stack, thus preventing it from growing larger than necessary. It also saves you the trouble of double-checking whether a symbol is an operator or not.
You can identify if it's opening or closing by the placement of before or after the operator. Separate case is identifying the unary minus like in your example.
35:55 Why not just initialize it with an open bracket? The initial value only matters in this one situation, the type shouldn't matter for the rest of the implementation, so just make it easier for this case?
@@mrseanbob Actually everything that can be at the start of an expression also can follow an opening parenthesis, with the exact same meaning. Therefore an opening parenthesis makes perfect sense here, even if other cases are added where the previous token matters. Indeed, you could simply put the total expression into a pair of parentheses, and remove all special handling of either beginning or end (if the expression is valid, the extra final parenthesis will cause the hold stack to be completely flushed, just as otherwise at the end of the expression).
@@__christopher__ yes it does work, but a parenthesis is not the same thing as the beginning of the expression. There might be some future case where you're interested in applying logic only at the beginning, or only on a real parenthesis. I don't see any reason not to distinguish between the two.
When I was an intern, many years ago now, I had to write a basic scientific calculator. This is what I used. Was fun. I wrote it in Java. Brings back memories. 😂
rather than setting the params to 1 and implementing a special case in the solver, can we just up the precedence and push a '0'? And rather than tracking whether the number of passes is 0, can we not just initialise previous symbol to "Unknown"? We also need to be careful if we're differentiating + and - in precedence - if you do so, 1 - 2 + 3 would first do 2 + 3, then 1 - 5, which is incorrect - I hope we fix this next episode by either giving them equal precedence or checking if we're making an addition before a subtraction
As a self taught software engineer, with deep interests in computer science, if you want to build up a computer from nand gates, write an assembler, a compiler and an OS for that hardware, I highly suggest you to take the courses nand2tetris and nand2tetris2.
Had to write a parser for expressions that included logical operators. Much the same, of course the logical operators also had a '!' which was also uniary. Then we created uniary 'conversion' operators that would take logical and return '1' or '0' for true or false and similar conversion for returning 't' or 'f' for 0 and ==0. Writing this sort of 'mini language' was actually kind of fun. Of course the users had trouble because they just never bothered to read my documentation. lol
Great video - thanks. I hope you will extend this further. I'm interested in the treatment of functions e.g. sqrt() - probably easy, but what about functions with more than one argument e.g. atan2(x,y) ?
Would interpreting every subtraction as “+0-“ work, so you don’t have to keep track of the previous character? Im interested to know if this would be faster, since code would only run when i sees a ‘-‘ instead of every character
We each had to create a compiler for honors project in Computer Science in the 90s. Tokens, lexical analysis, etc. In retrospect it was the hardest thing I ever did. I somehow scored 90%.
Hi there mate, i really enjoyed your video about math for game devs. I wanted to ask if you considerd to do some series for it, i would really appreciate that, you have gift for teaching
Thanks! I've no plans specifically as it's just regular maths! Instead I try to approach it from the gamedev angle by exploring those topics and the maths required to do those things at that time.
Can you already tell what kind of programming language? Ive written a stack machine myself once, would love to see a video about register machines like LUA uses
The real problem is the division sign if used as an infix operator instead of as a horizontal line with one expression above and one below. In school I learned that a slash was to be considered a horizontal line slanted and everything on the left to be considered above the line, everything on the right to be considered below the line, while the ÷ sign is to be considered like a multiplication, so they would be handled differently.
I'm almost certainly under-thinking this, but for the unary negative operator, wouldn't it just be a lot simpler to detect it, then just add a zero numeric literal to the stack in the right place to turn it into a zero minus number operation?
to alleviate issue of the unary negate and unary plus having the same symbol as addition and subtraction, i like how some languages have moved to ` for negate. easy to carry to written notation too, just superscript your dash. looks clear and is "backwards compatible" with external brains who don't do it :)
30:40, Simple solution, if a - follows a - just add a 0 to the output stack before adding anything else **Edit:** What to do with math like N-- - --N though?
I'm also from the UK and ive never referred to subtraction as take. I'd normally pronounce it minus. Also, on BODMAS. I learned that, but my younger sister was taught PEMDAS. At first I was confused because M and D had swapped place. Turns out they have the same precedence so it doesn't matter.
There is a problem with PEDMAS/PEMDAS. While explicit multiplication and division do have the same precedence, implicit multiplication must always be computed first. This is the source of the trolling on facebook with order of operations. Those are specific expressions that exploit the corner case of implicit multiplication. Pemdas only: 8/2(2+2) = 8/2(4) = 4(4) = 16 Pemdas with implicit multiplication acknowledged 8/2(2+2) = 8/2(4) = 8/8 = 1 (this is the correct answer)
We don't - add and sub have equal precedence, but when you have multiple additions and subtractions in an expression, it doesn't matter what order you do them in. You do however need to be careful as this program doesn't take into account 1 - 2 + 3, where technically you're adding 3 to -2, this program would add 3 to 2, which would be a mistake
So if there are 5 apples and take 3 apples I have 3 apples, However if there are 5 apples and I substract 3 apples, I have 2 apples. Got you there Brits.
Nice video as always! Thanks!! 33:24 This is why I hate auto (and every other programming language feature of this sort): the compiler knows the type, the editor knows the type, heck, even the writer knows the type most of the time. The only one who doesn't know the type is the reader. All because the writer wanted to save something very small (like pressing ctrl . or similar in the IDE or using 10 characters worth of display real-estate). I really don't see the point..
Sorry for not being complete: I think you specifically did it to aid in the explanation, avoiding complexity until it was necessary, as a great teacher would do! I was talking about auto's use in production code, not here!
So are you BODMAS, or PEDMAS, or something else?
I’m BIDMAS, taught that by a UK school.
BIMDAS im from Ireland
i've only ever heard PEMDAS
PEMDAS
BEDMAS (Ontario, Canada)
i've been writing code for almost 30 years and im still learning new things. thank you so much
Ah a man of culture nice to see you here
Im in the same boat, fancied trying to understand how the languages work for a bit, rather than just using them lol
@@javidx9 great idea for a series! 🙂
Same to me! Still hungry for coding entertainment and algos.
It's so awesome to see one of my favorite UA-camrs watch videos by another one of my favorite UA-camrs!
Dude, I started following your stuff when I was a junior dev. Almost 10 years have passed, nice to see you still make great content.
During the first 8 minutes I was thinking: You know he is a programmer when he does not need a computer to program! Thumbs up!
Just as a callout to people who learn alternatives such as PEMDAS and BIDMAS - the order of multiplication and division doesn't matter - they have the same precedence and are just done from left to right together. The same with addition and subtraction. You can swap M/D and A/S if you feel more comfortable that way, but these are within the scope of this video the only pairs that are interchangeable as of right now!
To add more context, division is just multiplication with a number between -1 and 1, just like subtraction is just addition with a number that is less than 0.
@@BlastinRope (division is multiplication by the reciprocal, I think that's what you're saying)
This is good but those rules are kind of arbitrary. It would be better to have an order of precedence list that can be 'modified' as per the grammar/language requirements, otherwise you get this monolithic structure which isn't easy to extend.
Exactly, and I would lump exponentiation in with other functions (or their equivalent symbology, such as |x| to means abs(x), or x! to mean factorial(x)), so that e^x-2 is exp(e, x)-2, but e^(x-2) would be exp(e, x-2); this makes sense in terms of computer programming where these are often in a library, like in C/C++. So the order of precedence becomes; parentheses, functions, multiplication/division in order from left to right, then finally addition/subtraction in order from left to right.
PE(MD)(AS)
In school, we were taught "Please Excuse My Dear Aunt Sally" as the acronym for the order of operations.
Also, another word for value is operand. For instance, in 4 + 5, the "+" is the operator and "4" and "5" are the operands.
kids now learn PEMDAS as Please Excuse My Dope Ass Swag
@@TheSelfUnemployedI really missed out
Just got into the Pixel Game Engine and happy to see you still making content! Thanks for everything you do for the community, you are appreciated!
Thanks buddy!
My mind was blown when I combined Recursive Descent statement parsing and Pratt expression parsing constructed with compile time curried functions. Great analysis of this expression parsing algorithm!
programming language development on this channel, I'm all for it!!
Custom programming languages are an interesting topic that plagued my mind for years! Great to see you covering this
I never knew that it was called the shunting yard algorithm. I still remember that creating a calculator was one of the first programs I had to write while studying 35 years ago.
25:50 The answer is 2 but not for the reason given: multiplication and division have the same priority so they are evaluated left-to-right, so: 1x(2+4)/3 = 1x6/3 = 6/3 = 2. The same for addition and subtraction.
I wonder if his implementation might have some errors somewhere due to prioritizing those differently.
Not yet, but it could. I've not mentioned "associativity" once in the video, and for good reason, it does introduce complexity to what is otherwise a very approachable algorithm. However we can't escape associativity should we need more interesting operators, which potentially disrupt the natural left to right bias of the solution stack. Interestingly, negation unary operator is contrary to this, but because we know it's the unary operator it's actually handled differently anyway during solving, but that might not always be the case moving forward.
@@AliceErishech You can see an error appearing at 15:22, where
1 + 2*4 - 3 + 5/6 * 2 + 6 - 1 - 4 + 7
is effectively parsed as
1 + 2*4 - (3 + 5/6 * 2 + 6) - 1 - (4 + 7)
More simply, 1 - 2 + 3 would be computed to be -4 rather than 2, since it's parsed as 1 - (2 + 3).
@@javidx9Doesn't it already fail for 2 - 1 + 3 which should evaluate to (2 - 1) + 3 = 4, but instead evaluates to 2 - (1 + 3) = -2 because + has a higher precedence than -? Or am I not understanding something (a distinct and likely possibility)?
Powers are an interesting exception here though as they're evaluated right to left (or at least that's what I was taught - wikipedia and google's built in maths evaluation function seem to agree). So 2^2^3 = 2^(2^3) = 2^8 = 256, whereas if you go left to right you would get 64.
Always, Aaalways I come back to Javid channel I learn something new! Thank you so much for all!
Always a fun time.
This video is priceless, thank you. A few observations- the brackets have higher precedence (i.e.3 plus) therefore the precedence of the subtraction operator becomes 3 plus by association with the brackets. You do not need to assume the bracket is 0... The brackets are made redundant at the point of output as no longer needed, as the order of the solve stack clarifies the order of operation at this point.
The master has returned. Always good to see amazing content with value from you and the community.
Keep it up javid, and congratulations on X10 growing health:)
We always find a way of meeting the right people "by accident".
This was a fantastic educational video! Thank you for your time with this one. Very excited to see what comes next in the series!
I love how eloquent you are explaining alien stuff like this.
I love your lovely placed remarks, like the "system("pause")" one ❤
Shoutous to the Stack Overflow answer that gave a fully functional recursive parser in Java! Really helped me in highschool!
Familiar algorithm, well explained -- good job! One thing you might have added is why it's called the "shunting yard algorithm", because it can be explained by analogy to shunting railway wagons in a yard in such a way as to build a train in the necessary order. In that analogy, only one stack is generally used (though another is needed for evaluating the solution, though in fact it can be the same stack with a bit of cunning).
Great vid! I never really knew where to start when it came to evaluating expressions.
It has been a while since I last watched one of your videos, it feels like meeting with an old friend after a long time.
Now I miss programming c++
I teach this algorithm in an introductory data structures course. It's a fun algorithm that makes students "get" the importance of using appropriate data structures to solve problems (in this case, the stack). Great explanation, btw!
We called this postfix notation when I was learning compiler design - there's also a prefix way to do it. I believe we used an operator stack and a literal stack, but essentially the same process.
I once read about the shunting algorithm but couldn’t work out what was going on. Being able to visualise it with bits of paper is such a good way of explaining it - I get it now - thank you. Brilliant video 👍🙂
Thank you so much for this video, I've been really looking into how to create a programming language and this has helped me tremendously. Please do a whole series on how to lex, parse, compile/solve/interpret a language, really looking forward to this
I love your videos, but there is one thing getting me stuck from time to time - naming conventions. Could you please describe why do they differ so much? Once you create a variable using camelCase (e.g. stkHolding), then you create some other variable using snake_case (new_op), and also the operator struct is called sOperator (afaik structs are usually called with UpperCamelCase). Also, is there any reason of shortening variable/constant names? imo "stkHolding" is not as user-friendly as "stackHolding", especially if you watch the video in parts :)
Maybe I misunderstood the code but at 10:00 if '+' has higher precedence than '-' then wouldn't 1 - 2 + 3 be evaluated as 1 - (2 + 3)? That would be unusual, IME. Plus and minus normally have the same precedence and would be evaluated left-to-right.
Same with multiplication and division
@@vitoswat
I think the problem exist only for addition and subtraction. Because in the case of 1-2+3 the minus can be translated (by humans) as unary minus and become 1+(-2)+3 and if we calculate now -2+3 first the rsult is correct.
In division and multiplication there is no "sign" problem. Hence:
18*3/2 = 18*(3/2) = (18*3)/2 = 27
I think that operators (-) and (+) and should be labeled with the same precedence level, and the rule of popping operator in case that it is with higher precedence should be applied even on the same precedence.
I would also mark (/) and (*) with the same precedence level.
The best ever use case for kitchen table. Thanks!!!
Great work mate.
If I had existed 10 years ago I would have had an easier time writing my compiler in college. I’m glad creators like yourself are out there.
Are you less than 10 years old or there is a typo?
I hope this series gets into tokenization and other related topics.
A while ago I tried to make an assembly parser, and only got so far, lol.
Thanks for this. I have always used recursive descent when playing with parsing. I really enjoyed learning the shunting yard algorithm. I implemented this in Python using a regex tokenizer and output RiscV assembly instead on interpreting. So, where you made an interpreter with a compiler, I made a compiler with an interpreter.
Dang I've missed these videos. You have a real gift for making the complex simple. Thank you!
A neat detail with the arity check could be to track, whenever either a constant gets pushed to the output stack or an operator gets flushed onto it, you'd be able to track the amount of "available" values there are lower in the stack -- thus the error could be localized better too.
Nice to see you again and thanks for the video. I've been studying splines not so long ago and was trying to make an extension for the unity editor to change values on the fly and immediately see the result in runtime. But the order of operations became something I couldn't overcome. My solution was very close to what you showed though. Thank you very much!
Amazing explanation as always, thanks a lot
But a side note, without considering left-to-right evaluation unpredictable results will occur `1+1-1` & `1-1+1`
Also waiting your approach for multiple digits numbers
I am really impressed with the teaching style and choice of difficult but important topics.
Any chance you will try automatic differentiation (mainly applied in neural network training)? This is also kind of difficult but also interesting.
Great video! I used Recursive Descent rather than the Shunting Yard Algorithm to parse my programming language, as Recursive Descent was a bit simpler for me to implement in C and wrap my head around, since it just uses the function call stack :)
Love the way you explained the algorithm. Although i learnt C, i would like to learn C++ to follow along. Great job.
This is gonna be a real treat! Looking forward to your upcomming videos.
Absolutely facinating.
As per usual @javidx9, I love the combination of your cool-as-a-cucumber delivery and exceptionally clear explanations.
Your videos always distract from other side-projects I might be involved in, but it's always such a pleasure, I couldn't possibly complain :)
nice explanation. i had heard about this algorithm but hadn't looked into it yet
I love your channel and glad to see you again haven't seen in a while.... one thing though when I was in school (a long time ago now lol) I was taught the multiplication would only be done first if it was in a bracket. So 1+2*4-3 is actually the same as 3*4-3. I guess I was taught wrong and so for 30-40 years I would have just been giving the wrong answer if I was ever asked. The weird part is that hasn't really hurt me when making computer programs. I suppose this is why when I write code, I use the brackets a lot more than necessary.
I am wondering: for the unary operators you used the pass counter variable. Why not change the type of the initial value of the last symbol variable to unknown? That way your code would have been worked from the beginning without the pass counter variable.
I learned RPN when tinkering with the Jupiter Ace with its inbuilt FORTH programming language back in the eighties! A doomed computer if ever there was one!
When I learned to do this, I don't think I was told what it was called. Our assignment was to make a roman numerical calculator so we had an addition layer to tokenize roman numerials and calculate their value. It was fun, the teacher didn't require 'correct' roman numeral notation (i.e. VIIII counted as 9 rather than IX for 9), but I made it work both ways.
Sick dude. I implemented a "Countdown solver", you know, like TV show. It could solve the numbers game in Countdown. Implemented as an expression tree. I didn't use this shunting algorithm, but it would have worked great.
35:52 Rather than using a pass variable, couldn't you have just initialized the symPrevious with an operator or parenthesis?
It would be much more fun to start solving what can be solved before you finish writing the stack, thus preventing it from growing larger than necessary. It also saves you the trouble of double-checking whether a symbol is an operator or not.
21:15 what if open parenthesis and close parenthesis are same token like in absolute value expression?
|-3-4|*-|6| result should be -42
You can identify if it's opening or closing by the placement of before or after the operator. Separate case is identifying the unary minus like in your example.
35:55 Why not just initialize it with an open bracket? The initial value only matters in this one situation, the type shouldn't matter for the rest of the implementation, so just make it easier for this case?
Or, make an actual symbol type for the beginning of an expression. Remove the ambiguity and make it more readable.
We could also just initialise to Unknown
@@mrseanbob Actually everything that can be at the start of an expression also can follow an opening parenthesis, with the exact same meaning. Therefore an opening parenthesis makes perfect sense here, even if other cases are added where the previous token matters. Indeed, you could simply put the total expression into a pair of parentheses, and remove all special handling of either beginning or end (if the expression is valid, the extra final parenthesis will cause the hold stack to be completely flushed, just as otherwise at the end of the expression).
@@__christopher__ yes it does work, but a parenthesis is not the same thing as the beginning of the expression. There might be some future case where you're interested in applying logic only at the beginning, or only on a real parenthesis. I don't see any reason not to distinguish between the two.
I've been looking into this for a while now, thanks so much for this video
When I was an intern, many years ago now, I had to write a basic scientific calculator. This is what I used. Was fun. I wrote it in Java. Brings back memories. 😂
rather than setting the params to 1 and implementing a special case in the solver, can we just up the precedence and push a '0'? And rather than tracking whether the number of passes is 0, can we not just initialise previous symbol to "Unknown"?
We also need to be careful if we're differentiating + and - in precedence - if you do so, 1 - 2 + 3 would first do 2 + 3, then 1 - 5, which is incorrect - I hope we fix this next episode by either giving them equal precedence or checking if we're making an addition before a subtraction
Since there is #1, i assume this is going to be a series to make a programming language, is it?
I'd love to see an algorithm for covering expression into Polish Notation (instead of RPN) as well :)
Thanks for such an informative video! 😊
As a self taught software engineer, with deep interests in computer science, if you want to build up a computer from nand gates, write an assembler, a compiler and an OS for that hardware, I highly suggest you to take the courses nand2tetris and nand2tetris2.
++
Had to write a parser for expressions that included logical operators. Much the same, of course the logical operators also had a '!' which was also uniary. Then we created uniary 'conversion' operators that would take logical and return '1' or '0' for true or false and similar conversion for returning 't' or 'f' for 0 and ==0.
Writing this sort of 'mini language' was actually kind of fun. Of course the users had trouble because they just never bothered to read my documentation. lol
Great video - thanks. I hope you will extend this further. I'm interested in the treatment of functions e.g. sqrt() - probably easy, but what about functions with more than one argument e.g. atan2(x,y) ?
Would interpreting every subtraction as “+0-“ work, so you don’t have to keep track of the previous character? Im interested to know if this would be faster, since code would only run when i sees a ‘-‘ instead of every character
New series to look forward to.
Love your videos! Going to implement this right now myself.
quite the coincidence that you upload this a couple of days after I start looking into ebnf and making a programming language haha
I like the way lisp does it (+ 1 2), aka polish notation. no ambiguity with precedence at all.
We each had to create a compiler for honors project in Computer Science in the 90s. Tokens, lexical analysis, etc. In retrospect it was the hardest thing I ever did. I somehow scored 90%.
Hi there mate, i really enjoyed your video about math for game devs. I wanted to ask if you considerd to do some series for it, i would really appreciate that, you have gift for teaching
Thanks! I've no plans specifically as it's just regular maths! Instead I try to approach it from the gamedev angle by exploring those topics and the maths required to do those things at that time.
Can you already tell what kind of programming language? Ive written a stack machine myself once, would love to see a video about register machines like LUA uses
I actually wanted to write my own C parser so this is very helpful :)
Best UA-cam channel and it's not even close
太好了，这是我一直等待的教程。感谢
The real problem is the division sign if used as an infix operator instead of as a horizontal line with one expression above and one below. In school I learned that a slash was to be considered a horizontal line slanted and everything on the left to be considered above the line, everything on the right to be considered below the line, while the ÷ sign is to be considered like a multiplication, so they would be handled differently.
I was used to making classic nested parsers and a tree-walking interpreter for that
Amazing, I'll implement it with golang which is my main object of study nowadays
I'm almost certainly under-thinking this, but for the unary negative operator, wouldn't it just be a lot simpler to detect it, then just add a zero numeric literal to the stack in the right place to turn it into a zero minus number operation?
Thank you for sharing. Great explanation!
Thank you Javid for always amazing videos.
to alleviate issue of the unary negate and unary plus having the same symbol as addition and subtraction, i like how some languages have moved to ` for negate. easy to carry to written notation too, just superscript your dash. looks clear and is "backwards compatible" with external brains who don't do it :)
(i wasn't able to find a nice way to differentiate unary plus other than to ignore it lol. it's the no-op of math)
30:40, Simple solution, if a - follows a - just add a 0 to the output stack before adding anything else
**Edit:** What to do with math like N-- - --N though?
What happens when there is a negative number in the solving stack. Another stack?
The solving stack by that time stores values not tokens, so its just computed as normal
I'm also from the UK and ive never referred to subtraction as take. I'd normally pronounce it minus.
Also, on BODMAS. I learned that, but my younger sister was taught PEMDAS. At first I was confused because M and D had swapped place. Turns out they have the same precedence so it doesn't matter.
(@1:59) don’t forget exponentiation! 😌
Does anyone know if parsing expressions like "- (5-15)" returns a valid RPN? Or more complex ones like "5 * - (5-15)"?
It's valid if the RPN format you use supports unary operator
@@javidx9 Do you have the RPN for the second expression? Also, thanks for answering my question ;)
5 5 15 - - * but that second - is unary
BODMAS is famous in India, it stands for Brackets Open, Divide, Multiply, Add, Subtract.
bro's full metalhead mode
The best kind of mode
Pedmas > bodmas, math < maths
Where I'm from we learned "PEMDAS". A phrase we use is "please excuse my dear Aunt Sally"
I am secretly hoping this adventure is the start of a 6502 compiler for the NES emulator project.
There is a problem with PEDMAS/PEMDAS. While explicit multiplication and division do have the same precedence, implicit multiplication must always be computed first. This is the source of the trolling on facebook with order of operations. Those are specific expressions that exploit the corner case of implicit multiplication.
Pemdas only: 8/2(2+2) = 8/2(4) = 4(4) = 16
Pemdas with implicit multiplication acknowledged 8/2(2+2) = 8/2(4) = 8/8 = 1 (this is the correct answer)
You guys differentiate between sub/add? For us its the same and we then just read left to right...
We don't - add and sub have equal precedence, but when you have multiple additions and subtractions in an expression, it doesn't matter what order you do them in. You do however need to be careful as this program doesn't take into account 1 - 2 + 3, where technically you're adding 3 to -2, this program would add 3 to 2, which would be a mistake
In India, we use BODMAS. I was confused when I first heard of PEMDAS when reading an American textbook!
Incredible explanation
So if there are 5 apples and take 3 apples I have 3 apples, However if there are 5 apples and I substract 3 apples, I have 2 apples. Got you there Brits.
Take as in take away.
If you take away 3 of the 5 apples from your fruit basket, you have 2 apples left
it's how many are left over not how many you have
We also learned BODMAS in India! Its quite funny because bodmas in bengali means 'brat' 😂
woo! Looking forward to this series
Nice video as always! Thanks!!
33:24 This is why I hate auto (and every other programming language feature of this sort): the compiler knows the type, the editor knows the type, heck, even the writer knows the type most of the time. The only one who doesn't know the type is the reader. All because the writer wanted to save something very small (like pressing ctrl . or similar in the IDE or using 10 characters worth of display real-estate).
I really don't see the point..
Sorry for not being complete: I think you specifically did it to aid in the explanation, avoiding complexity until it was necessary, as a great teacher would do!
I was talking about auto's use in production code, not here!
one of great of c++ because of the template where vector and list are standard lib in c++
Great stuff as always. 👍
Ironic I finish a course in Uni about this and you post the video after i am done lol
We learn it as "Please Excuse My Dear Aunt Sally" or PEMDAS.
GNU Bison or Recursive Descent?