Making a calculator from scratch - #SoME3

Disclaimer: This video is rather programming heavy at points. You are welcome to skip these parts, but do note you might miss some small detail somewhere. These sections have the "Code:" prefix in the timestamps.

Evaluating math expressions is not an easy problem to solve, despite seeming extremely simple.
This video is a step by step guide to doing so, taking you through the motivations behind these steps as well.

This is my entry for the Summer of Math Exposition, hosted by @LeiosLabs and @3blue1brown

Timestamps:
0:00 - Intro
1:15 - Lexer/Tokenizer
3:04 - Code: Lexer Implementation
4:33 - Beyond Lexing
5:46 - Structuring Math Expressions
7:03 - Code: Representing AST Nodes
7:46 - Evaluating an AST
9:44 - Code: Basic Parsing Structure
11:02 - Order of Operations
12:12 - A general expression
13:57 - Colouring expressions
16:19 - Code: Parse Expression function logic
19:14 - Parenthesized Expressions
19:57 - Code: Parsing "Terminal" expressions
21:51 - Finished the basic pipeline
22:06 - Code Bonus: Implicit Multiplication
23:14 - Recap and outro

Links:

Thanks to:
Garklein
Allen4th
IdkRandomTry
s m p l
Asher
GamesWithGabe
for your feedback

Music:
Somnia I - Reed Mathis
Interplanetary Alignment - NoMBe
Creeping Up on You - Godmode

#SoME3 #C #calculator
#MadeWithMotionCanvas

[voxelrifts]

Please note, this is *not* supposed to be the easiest way to make a calculator like this. As many have mentioned there are algorithms specifically for evaluating math expressions like shunting yard, which would probably be easier to implement. However this way of generating an AST has its own benefits:
1) This can be easily extended into an actual programming language
2) Since we get the full AST at the end, we can do some cool things with it if we just add an 'x' variable node. A few examples can be simplifying an AST by walking the tree and applying rules, or even creating an AST for the derivative of the given expression by analyzing the generated tree.

Really the opportunities are endless here.

[tomiivaswort]

I love how the word "AST", so as Abstract Syntax Tree, as the german word "Ast" translates to branch, wich is exactly what an AST is made out of

[cynical]

As a compiler author, I really enjoyed this. Great video!

[EmKonstantin]

The "loading" (or "waiting") animation on the tree nodes while evaluation works really well ! So visually simple, yet it clearly shows the order of operations.

[nevanjohn]

Thank you for taking the time to make a video on this topic :D I've been trying to get into low level programming and though I don't fully understand all the code and concepts in this video (on my first viewing), I hope to look into the stuff mentioned here and comeback later to help me implement my own version of this.

[albachteng]

This was a fantastic video. Well put together, clear and thorough without holding hands and filled with intuition. Great job!

[angeldude]

In a way, this entire calculator is essentially an interpreter for a very simple (non-Turing complete) programming language, so it's completely natural that it'd be similar to other interpreters. It's also possible to argue that the lexer and parser are essentially simple compilers in their own right, translating a source string into more usable data, and then transforming it again into _more_ usable data. Really, the only difference between a compiler and an interpreter is that interpreters reduce their input to the final output on its own while compilers serialize the data it transformed the source to into a format the CPU and OS can understand. Most modern compilers just transform the input into something a more established compiler framework (usually LLVM) can understand and then pass that to said framework, at which point it can apply its own transformations to simplify the data so that the final serialization is smaller and/or faster. (You could even argue that a CPU is just an interpreter implemented in hardware. Modern CPUs also have hardware implemented _compilers_ too to transform the machine code even further into micro-operations that _then_ get interpreted.)

I remember implementing a simple calculator with the Shunting Yard algorithm outputing RPN, which is basically just a flattened representation of the syntax tree, in, _of all things, DCPU-16 assembly. Gosh_ that was a long time ago...

[hectormejia]

This channel is criminally under rated. I feel bad watching this for free, great work!

[odomobo]

I was expecting you to talk about left- vs right-associativity, since exponentiation is right-associative. I think it's worth a mention at least.

[Apple-vmgc]

This video is very useful for the compiler design course.

[gameofpj]

This is explained really well! I really like the part about the recursion and coloring :D Really makes this click for me!

[Isaac-zydo]

Nice! I think this approach (pratt parser) is the best way for building up towards writing a conventional programming language, but if you wanted to make a stack based language like dc or forth, or a s-expression lang like lisp, you could get a similar level of usability with a much simpler parser (don't need operator precedence in those languages). A neat trick for implementing operator precedence if you need it that i saw on wikipedia is to add brackets around the operators based on their precedence level, e.g. + -> ))+((, * -> )*(, (-> (((, )-> ))) and surround the whole expression in (()). Apparently this was done in early fortran compilers.

[SimGunther]

Chidi Williams has neat writeups on parsing where he uses recursive descent for statements while pratt parsing is used for expressions. The code he uses is in TypeScript, but the concepts apply nicely in C as well.

[brummi]

I feel your pain, I've been trying off and on for half a year now to program my own calculator/CAS program, and my last iteration (before i stupidly decided to restart from scratch) somehow manages to evaluate Sums, integrals and derivatives analytically (so not just approximations with Riemann sums) and other stuff, but shits itself and dies (crashes my arduino) if it is asked to add 3 decimal numbers. It is very difficult to avoid technical debt, and program functions... in such a general way that you don't have to manually program in every interaction, but so concretely that they still do what you want them to

[wChris_]

Take a look at reverse polish notation! Transforming a token stream into this format makes evaluation trivial, as you can use a stack. Numbers will be pushed onto it and operators will take the top 2 numbers and apply the operation and push the result on the stack. The value on the stack after everything has been evaluated is the result.

[fantasypvp]

I did this in rust a few months ago and it was such a fun project, recently I've been working on adding support for functions so you can use sin(), ln() and other stuff

[laujimmy]

I really learned a lot from this video. I have no idea that's how a calculator works, now i will look into it. ❤❤❤

[palpytine]

For a simple expression language like this, parsing straight to reverse polish notation is simpler, faster, and uses significantly less memory. The AST approach is better suited to a more complex language with multiple expressions where you're also adding a symbol table into the mix. It arguably does a better job of reporting errors in the expression.

[vitorschroederdosanjos]

That sounds very interesting for working in non usual fields (rings, groups) pretty nice!!

[abdigex]

You did this so radically different to me. Who knew there were so many ways to make a calculator.