DIY Programming Language #1: The Shunting Yard Algorithm

In this video I demonstrate how the Shunting Yard Algorithm works, and produce a simple implementatin to solve basic mathematical expressions like a calculator would.
Source: github.com/OneLoneCoder/Javid...
Patreon: / javidx9
KZbin: / javidx9
/ javidx9extra
Discord: / discord
Twitter: / javidx9
Twitch: / javidx9
GitHub: www.github.com/onelonecoder
Homepage: www.onelonecoder.com

[@javidx9]

So are you BODMAS, or PEDMAS, or something else?

[@samuelhulme8347]

I’m BIDMAS, taught that by a UK school.

[@irishbruse]

BIMDAS im from Ireland

[@stephenkamenar]

i've only ever heard PEMDAS

[@TheHackysack]

PEMDAS

[@mantictac]

BEDMAS (Ontario, Canada)

[@ModernVintageGamer]

i've been writing code for almost 30 years and im still learning new things. thank you so much

[@irishbruse]

Ah a man of culture nice to see you here

[@javidx9]

Im in the same boat, fancied trying to understand how the languages work for a bit, rather than just using them lol

[@stephenelliott7071]

@@javidx9 great idea for a series! 🙂

[@markuszeller_official]

Same to me! Still hungry for coding entertainment and algos.

[@jhfoleiss]

It's so awesome to see one of my favorite KZbinrs watch videos by another one of my favorite KZbinrs!

[@psodq]

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!

[@user-ov5nd1fb7s]

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.

[@TheSelfUnemployed]

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!

[@javidx9]

Thanks buddy!

[@Barnardrab]

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.

[@TheSelfUnemployed]

kids now learn PEMDAS as Please Excuse My Dope Ass Swag

[@YourMom-rg5jk]

​@@TheSelfUnemployedI really missed out

[@kplays_6000]

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!

[@BlastinRope]

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.

[@CJBurkey]

@@BlastinRope (division is multiplication by the reciprocal, I think that's what you're saying)

[@user-io4sr7vg1v]

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.

[@williamsquires3070]

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.

[@scottpageusmc]

​@@BlastinRope, wow! I'm 46 and have been working with numbers in programming for decades. Thank you for teaching this dog new tricks!

[@landmanland]

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.

[@catapillie]

programming language development on this channel, I'm all for it!!

[@SimGunther]

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!

[@antonpieper]

Custom programming languages are an interesting topic that plagued my mind for years! Great to see you covering this

[@Sam-hu3xt]

I love how eloquent you are explaining alien stuff like this.

[@GRAHAMAUS]

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).

[@jhfoleiss]

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!

[@tsol9097]

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.

[@scottpageusmc]

I've been programming since 1986, and probably have forgotten more languages than I remember now, but you somehow are able to teach this old dog something new in every video. I'm 46 now, and it is rare that I run across many people with the same background as I have, and you are in my top at least 3 favorite KZbinrs of all time! You're clear, concise, well structured, and brilliant. Thank you for doing what I wish I could do! Outstanding all around!

[@Z80Fan]

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.

[@AliceErishech]

I wonder if his implementation might have some errors somewhere due to prioritizing those differently.

[@javidx9]

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.

[@CharnelMouse]

@@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).

[@NickFegley]

​@@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)?

[@MrChannel42]

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.

[@ryanlarge6296]

This was a fantastic educational video! Thank you for your time with this one. Very excited to see what comes next in the series!

[@CediCore]

I love your lovely placed remarks, like the "system("pause")" one ❤

[@PabloSanchez-th5em]

Always, Aaalways I come back to Javid channel I learn something new! Thank you so much for all!

[@vitoralmeidasilva]

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:)

[@Olosann]

The best ever use case for kitchen table. Thanks!!!

[@angelstojanov2346]

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

[@FrancoSang]

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++

[@devpoodle]

Great vid! I never really knew where to start when it came to evaluating expressions.

[@GodofWar1515]

This is gonna be a real treat! Looking forward to your upcomming videos.

[@craigberry5713]

Dang I've missed these videos. You have a real gift for making the complex simple. Thank you!

[@pixelfingers]

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 👍🙂

[@coronelkittycannon]

Shoutous to the Stack Overflow answer that gave a fully functional recursive parser in Java! Really helped me in highschool!

[@Shineglow]

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!

[@SpringySpring04]

Where I'm from we learned "PEMDAS". A phrase we use is "please excuse my dear Aunt Sally"

[@xybersurfer]

nice explanation. i had heard about this algorithm but hadn't looked into it yet

[@Red-di7zb]

Thank you Javid for always amazing videos.

[@nikkehtine]

I've been looking into this for a while now, thanks so much for this video

[@MoritzWallis]

Love your videos! Going to implement this right now myself.

[@Andrew90046zero]

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.

[@mortenlund1418]

Thank you for sharing. Great explanation!

[@user-br6ku7jj6n]

thank you so much, I've long been wondering how parsing mathematical expression works

[@Adowrath]

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.

[@sossesam]

Love the way you explained the algorithm. Although i learnt C, i would like to learn C++ to follow along. Great job.

[@ThePandaGuitar]

Incredible explanation

[@rednibcoding3412]

This is awesome!

[@RoryBecker]

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 :)

[@c0smeticplagu3]

Best KZbin channel and it's not even close

[@sanderbos4243]

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 :)

[@cariyaputta]

New series to look forward to.

[@davep7176]

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.

[@jackpioneer3566]

great explanation!

[@JujuAdams]

woo! Looking forward to this series

[@v-for-victory]

Wow. So great, thanks!

[@strick9red]

Great lesson.

[@adam-n-modi]

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

[@Paulie68000]

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!

[@calcal6508]

quite the coincidence that you upload this a couple of days after I start looking into ebnf and making a programming language haha

[@wolpumba4099]

Amazing!

[@Sfaxx]

I'd love to see an algorithm for covering expression into Polish Notation (instead of RPN) as well :) Thanks for such an informative video! 😊

[@zxuiji]

I actually wanted to write my own C parser so this is very helpful :)

[@CrankViewer]

Great Vid. Thank you.

[@kemoxplus]

great video!

[@MatthewBishop64]

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.

[@whiskeyoo]

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 :)

[@mikefochtman7164]

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

[@brockormond4131]

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.

[@InfiniteCoder01]

I was used to making classic nested parsers and a tree-walking interpreter for that

[@jordixboy]

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.

[@bossgd100]

++

[@markuszeller_official]

That was great fun!!!

[@ocayaro]

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%.

[@liorean]

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.

[@chaeju106]

Since there is #1, i assume this is going to be a series to make a programming language, is it?

[@dixztube]

Pedmas > bodmas, math < maths

[@emjizone]

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.

[@terminallumbago5582]

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. 😂

[@nandomax3]

Amazing, I'll implement it with golang which is my main object of study nowadays

[@williamsquires3070]

(@1:59) don’t forget exponentiation! 😌

[@anthonydistel]

We learn it as "Please Excuse My Dear Aunt Sally" or PEMDAS.

[@user-kb2qz3gj6k]

Thank you teacher

[@valerii_bezhevets]

Perfect!!!

[@jakubfrei3757]

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

[@javidx9]

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.

[@nimcompoo]

We also learned BODMAS in India! Its quite funny because bodmas in bengali means 'brat' 😂

[@petermather3049]

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) ?

[@music4life467]

one of great of c++ because of the template where vector and list are standard lib in c++

[@Imm0rtal101]

bro's full metalhead mode

[@SoDamnMetal]

The best kind of mode

[@sg4644]

In India, we use BODMAS. I was confused when I first heard of PEMDAS when reading an American textbook!

[@Cmanorange]

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 :)

[@Cmanorange]

(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)

[@bronsonmagnan9055]

I am secretly hoping this adventure is the start of a 6502 compiler for the NES emulator project.

[@eeprom34]

Thinks for your eXcellent approche

[@christophfriedrich5092]

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.

[@bronsonmagnan9055]

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)

[@m4rt_]

PEMDAS Parenthesis Exponents Multiplication / Division (left to right) Addition / Subtraction (left to right)

[@m4rt_]

you could technically do (0-n) to do negative numbers, but it's probably better just to implement negative numbers in the input

[@ablonix]

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]

Same with multiplication and division

[@strayling1]

Uh oh, here be dragons!

[@YourMom-rg5jk]

based

[@luckybearthing1796]

Ironic I finish a course in Uni about this and you post the video after i am done lol

[@nulldmg27]

This would have been helpful when I was back in University, lol

[@darcgames6375]

Sneak peek to the olcLang? I hope so

[@kplays_6000]

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

[@iv3995]

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

[@TheMyHalo]

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

[@BudgiePanic]

In my school we learned BEDMAS (brackets, exponents, division, multiplication, addition, subtraction) so a weird mixing of different countries terms

[@LexStrat]

круто