Swift 3 Fun Algorithms: Abstract Syntax Tree (Warning: Somewhat Difficult Recursion)

  Рет қаралды 20,915

Lets Build That App

Lets Build That App

7 жыл бұрын

Let's continue with our theme from last week and implement an even harder recursion algorithm this time. Today, I'll introduce to you something called an Abstract Syntax Tree which is typically used by compilers to figure out what kind of code you are writing.
Because this is a somewhat difficult challenge, it's useful to walk through each use case one step at a time. This way you can see clearly how the recursion should be performed.
Facebook Group
/ 1240636442694543
iOS Basic Training Course
www.letsbuildthatapp.com/basi...
Completed Source Code
www.letsbuildthatapp.com/cour...
Follow me on Twitter: / buildthatapp

Пікірлер: 68
@johnelsegood5744
@johnelsegood5744 7 жыл бұрын
Fantastic video Brian, appreciate all the hard work you put into your videos. Couldn't help myself in refactoring the evaluate method. func evaluate(node: Node) -> Float { if node.value != nil { return node.value! } func performBinaryOperation(operation: String) -> (Float, Float) -> Float { switch operation { case "+": return { $0 + $1 } case "-": return { $0 - $1 } case "*": return { $0 * $1 } case "/": return {(lhs: Float, rhs: Float) -> Float in if rhs == 0 { fatalError("Divide by zero") } else { return lhs / rhs } } default: fatalError("Invalid Operator: \"\(operation)\"") } } let performBinaryOperationOn = performBinaryOperation(operation: node.operation!) return performBinaryOperationOn(evaluate(node: node.leftChild!), evaluate(node: node.rightChild!)) } Not sure its any shorter, but I still had fun writing it.
@LetsBuildThatApp
@LetsBuildThatApp 7 жыл бұрын
This is excellent, really happy to hear you had fun rewriting it. Really like the functional approach of solving this challenge. I didn't even know you could write functions within functions like this...
@johnelsegood5744
@johnelsegood5744 7 жыл бұрын
Thanks for the feedback
@kryptoshi4706
@kryptoshi4706 7 жыл бұрын
You are a great teacher Brain ! Thank you for putting so much work in, swift is such a beautiful language. I remember during college programming this in C was a pain !!
@MThomasson88
@MThomasson88 7 жыл бұрын
Excellent video once again. I've learnt so much from you! Looking forward to next vid.
@LetsBuildThatApp
@LetsBuildThatApp 7 жыл бұрын
Great to hear the positive feedback Martin, next vid next week.
@stevenhans7669
@stevenhans7669 7 жыл бұрын
good video! as a computer science student this is a new source of learning how to code new languages and algorithms thank you very much, I found this very informative keep it up Brian, i'd like to see more videos like this in the future
@andreychirkov1904
@andreychirkov1904 7 жыл бұрын
Fantastic! Looking forward next Friday episode
@LetsBuildThatApp
@LetsBuildThatApp 7 жыл бұрын
Thanks Andrey.
@ProgrammerinToronto
@ProgrammerinToronto 7 жыл бұрын
Thank you for your awesome algorithm show! can't wait to see next time.
@LetsBuildThatApp
@LetsBuildThatApp 7 жыл бұрын
Excellent, much more to come this friday.
@xShorDz
@xShorDz 7 жыл бұрын
I think this is the best gift for my today's birthday, thank you Brian!
@LetsBuildThatApp
@LetsBuildThatApp 7 жыл бұрын
You're very welcome Andrea, I'll bring you another present next year.
@kav04
@kav04 6 жыл бұрын
Brian you killed it !
@rogerwprice
@rogerwprice 7 жыл бұрын
Wow. Really nice. Thanks. Roger
@LetsBuildThatApp
@LetsBuildThatApp 7 жыл бұрын
Hopefully this algorithm wasn't too difficult to follow. It's a pretty common problem set CS students go over and often a similar version of this problem is given during interviews. Hope you had fun with it Roger.
@depdoprogramming2750
@depdoprogramming2750 4 жыл бұрын
very nice explanation. thanks
@aleksejsigaj1373
@aleksejsigaj1373 22 күн бұрын
Much easier to weite the Node structure as let value: Value let leftCh... let rightCh... enum Value { case number(Int) vase operation(Operation) } enum Operation { case plus case minus case must case division case multiplication } And then use it with switch case ;)
@Jiawii
@Jiawii 3 жыл бұрын
The audio of this video is so good
@huslerbling
@huslerbling 7 жыл бұрын
gave it a thumbs up and subscribed.
@christophebugnon5155
@christophebugnon5155 5 жыл бұрын
You are my hero ! 😃
@yanxu9167
@yanxu9167 2 жыл бұрын
So clear! My professor is useless. Thank you.
@robertcharmers3264
@robertcharmers3264 7 жыл бұрын
Nice explanation, certainly refreshed my memory from uni days. Would be nice to see a video which addresses the substantially more complex task of producing the actual AST which must,at least in this case, take into account the order of operations (i.e BODMAS) since the algorithm you present here assumes the operations have been specified in the correct order.
@LetsBuildThatApp
@LetsBuildThatApp 7 жыл бұрын
Hi Robert, yeah I would like to get my hands on more complicated examples of trees. I've been out of college for quite some time and need to do some research on theory again.
@robertcharmers3264
@robertcharmers3264 7 жыл бұрын
Haha same here man, its amazing how easy it is for your memory to slip especially when your not actively writing these algorithms on a daily basis. Like I say, I think your implementation, which essentially *traverses* the tree, is perfectly adequate for production use as long as the algorithm that parses the raw expressions and tokens to *produce* the actual AST being traversed takes into account the order of operations. This is what I'm attempting to do at present for a project I'm working on; I need to be able to take a bunch of arbitrary arithmetic expressions and parse and order them (according to BODMAS) to produce a tree; once I've done that then an algorithm not to dissimilar to the one you present here may be used to traverse and process the resulting tree. Anyway, great video!!
@Seieukos
@Seieukos 7 жыл бұрын
Dang, this is extremely useful. In my Software Development class the AST was just introduced to us for our project to build a lexer. Thank you very much!
@LetsBuildThatApp
@LetsBuildThatApp 7 жыл бұрын
Excellent, AST is a very exciting problem set that allows you to understand recursion on another level.
@cesarcontreras8853
@cesarcontreras8853 7 жыл бұрын
hey, I would like to see a video about MVP pattern with Swift. Nice video tho, great job!
@thedrei24
@thedrei24 6 жыл бұрын
yeah, want more algo videos like this one
@kennygrandberry8590
@kennygrandberry8590 7 жыл бұрын
This was amazing!! Could you cover linklist, and Dictionary algorithms. I am currently going through cracking the coding interview book, and a couple of resources to learn algorithms. Its nice to finally see someone cover algorithms in swift without trying to convert the answers from Java, or C to swift.
@LetsBuildThatApp
@LetsBuildThatApp 7 жыл бұрын
I need to get my hands on that book to get a better idea on what kind of useful algorithms are covered. I feel like Swift is a very new language and I would like to cover more relevant iOS type of challenges.
@kennygrandberry8590
@kennygrandberry8590 7 жыл бұрын
Yea its pretty good it covers some of the basic algorithms(and some really hard ones), but I am not sure what kind you may have ran into during interviews. Its really hard for me to study for them because you may run into any type of problem, so I have to be good at all the datastructures. But your vids are helping alot!!
@thrb41
@thrb41 7 жыл бұрын
Thanks!
@jdetnat
@jdetnat 5 жыл бұрын
Gracias!!! tytyty
@PythonPlusPlus
@PythonPlusPlus 5 жыл бұрын
This can be solved beautifully with indirect enums: indirect enum ArithmeticStatement { case Add(ArithmeticStatement, ArithmeticStatement) case Subtract(ArithmeticStatement, ArithmeticStatement) case Multiply(ArithmeticStatement, ArithmeticStatement) case Divide(ArithmeticStatement, ArithmeticStatement) case Value(Float) } let calculation: ArithmeticStatement = .Add(.Multiply(.Value(25), .Value(6)), .Value(5)) func evaluate(_ statement: ArithmeticStatement) -> Float { switch statement { case .Add(let a, let b): return evaluate(a) + evaluate(b) case .Subtract(let a, let b): return evaluate(a) - evaluate(b) case .Multiply(let a, let b): return evaluate(a) * evaluate(b) case .Divide(let a, let b): return evaluate(a) / evaluate(b) case .Value(let value): return value } } print("25 * 6 + 5 = \(evaluate(calculation))") // 25 * 6 + 5 = 155.0
@geomichelon
@geomichelon 7 жыл бұрын
man..you are the best...i m watching all your videos in one wekeend .I m from Brazil and here is Carnival and i hate Carnival :-).Better pratice swift with you man... Do you think in create any tutorial with Core Data or Realm?
@ypaut
@ypaut 5 жыл бұрын
Greetings, what is the editor you are using? Thank you for the video.
@JeffKang84
@JeffKang84 Жыл бұрын
Which code editor feature puts those evaluation numbers on the right column? Thanks for the video.
@gozlanjeremy9951
@gozlanjeremy9951 7 жыл бұрын
hey Brian ! amazing videos , I have one big problem I cannot solve. I just added a button into a collection view cell, however my button is not clickable as well as not receiving actions even if I set him with a special action using add target , any clue?? he is not clickable at all!
@MuhammadAli-zv5vz
@MuhammadAli-zv5vz 7 жыл бұрын
Nice
@StunnerAlpha
@StunnerAlpha 7 жыл бұрын
Nice video but I have a question: Did you forget to handle the case of PEMDAS? (multiplication being processed before addition in the given example) The way you solved it would incorrectly solve the initial problem like so: 5 + 25 * 6 = 180 instead of the correct value of 155. Or am I mistaken?
@sunnylin8587
@sunnylin8587 3 ай бұрын
How can I transfer Abstract Syntax Tree which generated by OData to an API request parameter?
@rafaelrincon3109
@rafaelrincon3109 6 жыл бұрын
@3:40 that sounds like a challenge ;)
@MustafaSayimMK
@MustafaSayimMK 7 жыл бұрын
func evaluate(tree: Node) -> Double{ var leftNumber = 0.0 var rightNumber = 0.0 if tree.rightChild == nil && tree.leftChild == nil{ return (tree.value)! } if tree.leftChild != nil{ leftNumber = evaluate(tree: tree.leftChild!) } if tree.rightChild != nil{ rightNumber = evaluate(tree: tree.rightChild!) } switch (tree.operation!){ case "+": return leftNumber + rightNumber case "-": return leftNumber - rightNumber case "*": return leftNumber * rightNumber default: if rightNumber == 0{ print("error") exit(1) } else { return leftNumber / rightNumber } } } Not sure if this is a professional way in writing codes, but I would like to get a feedback if possible?
@glennmarkabalos6657
@glennmarkabalos6657 5 жыл бұрын
thank you for this but I have a question; how to implement the order of operation (mdas)?
@flutterwind7686
@flutterwind7686 5 жыл бұрын
This example was just about evaluating the tree, not making it. Making an AST is even more difficult. To put it simply you need to know a little about Finite Automata(kzfaq.info/get/bejne/iNB_drWKyc2cco0.html) and Compiler Design. There are many algorithms to create an AST Tree, most popular is Recursive Descent Parsing(kzfaq.info/get/bejne/m7ynn5OZ0K-WYY0.html). In the Recursive Descent Algorithm, you can specify rules for operations. These are the basics in Compiling code and Programming language design.
@federicoli6439
@federicoli6439 7 жыл бұрын
Hey Brian! We just deployed a new iOS app but we got many crashes related to parsing special characters. How can we best de-bug deployed apps? Any services you recommend? Using the built in crashlogs wasn't too useful because it only shows the function that crashed, without telling us which special characters actually caused the failure. :/
@StunnerAlpha
@StunnerAlpha 7 жыл бұрын
Crashlytics
@engen511
@engen511 7 жыл бұрын
Hi Brian, Are you planing to cover all the data structure and algorithms on friday episode?
@LetsBuildThatApp
@LetsBuildThatApp 7 жыл бұрын
Well, what kind of data structures/algorithms would you like to see?
@engen511
@engen511 7 жыл бұрын
well, i dont kow how to put this, like data structure inplementaion on App such Firebase chat where user can update their details on app like name, email address, or profile image from seetings.
@jincat3057
@jincat3057 7 жыл бұрын
Great lecture Brian! Easy to understand your recursion. Could you please include some solution about linkedList in the future? Since swift has no 'pointer' like C++ does, sometimes it is easy to get confused on how to get reference of an object in Swift, such as this problem in leetcode: leetcode.com/problems/min-stack/ Thank you so much! Looking forward to next Friday.
@donpaulpm
@donpaulpm 7 жыл бұрын
🙂 how will I build my own calender with collection view... u should have 1 day for giving working ideas like above..😀 on our questions..too... it will be great... to see ans from u ... so I can avoid librarys as much as possible...
@LetsBuildThatApp
@LetsBuildThatApp 7 жыл бұрын
Can you tell me your implementation of the calendar? I'm curious what you've attempted.
@donpaulpm
@donpaulpm 7 жыл бұрын
Lets Build That App 🙄 I just implement calendar with fscalendar... But it have some issues with almofire... it shows 4error . But so far I can run the app with this red error...But I don't know if it will course any issues when I pull to app store..So I planing to have my own calender... But no idea where to start..If u pull the starting idea I will be great..or eg twice a week we all together can create custom class file for such things like discussion session.
@Gavolak
@Gavolak 7 жыл бұрын
In Java, I pumped out an answer in 10 minutes. But in this... I can't even name this language. Is it a variant of C? In your opinion, is Java becoming obsolete? I'm only in tenth grade and my experience is my AP computer science class, so forgive me if my knowledge Is lacking!
@LetsBuildThatApp
@LetsBuildThatApp 7 жыл бұрын
This is Swift, a language that is meant to replace Objective C for iOS development. Java will never be obsolete in the corporate world.
@robertcharmers3264
@robertcharmers3264 7 жыл бұрын
I'll second that!!! Been programming for as long as I can remember (circa 18 years). As you can imagine I have written code in numerous languages in that time from low-level Assembly to high-level Visual Basic and I'm yet to come across a language that has the shear expressiveness,flexibility and power of Java. The fact that I can write a piece of logic ONCE and deploy it as part of a Windows/Mac Desktop App, A Web Server App, Android Tablet or Mobile Phone App WITHOUT any platform-specific recompilation perfectly illustrates this point. Its not so much the Java language (and associated syntax and semantics) that was a breakthrough all those years ago, but rather the Language Runtime Paradigm that underpins it. The idea that perhaps, if virtualised, the entire runtime could be ported to different platforms thereby abstracting away and negating the need for developers to target said platforms themselves; developers can essentially write platform agnostic code.
@albertlu8407
@albertlu8407 7 жыл бұрын
驚為天人 :D
@LetsBuildThatApp
@LetsBuildThatApp 7 жыл бұрын
还行还行 今天的影片说实话不容易录
@albertlu8407
@albertlu8407 7 жыл бұрын
It's not easy, but we have faith in you! 👊
@LetsBuildThatApp
@LetsBuildThatApp 7 жыл бұрын
谢谢 I think I will go over an easier algorithm next Friday.
@JonathanGreenwalton21
@JonathanGreenwalton21 7 жыл бұрын
Its such bullshit that interviewers force this garbage on people. I literally told my interviewer that "I'm a developer not a computer scientist we won't use this to build any apps for the company, look at my repos on github I know how to build iOS apps so ask me a real question" I've been working there since June of last year.
@LetsBuildThatApp
@LetsBuildThatApp 7 жыл бұрын
+Jonathan Green yeah it's unfortunate that developers are tested on unrelated algorithms during interviews that don't really gauge their competence in building complete projects. I think you did the right thing.
@robertcharmers3264
@robertcharmers3264 7 жыл бұрын
@Jonathan Green Still, learning a little Data Structures and Algorithm theory can't hurt can it? Personally speaking, I have always been fascinated with the topic (Data Structures and Algorithms) and remember thoroughly enjoying learning how to store and perform operations on data in the most efficient manner possible. Plus there *are* certain computer science specific algorithms and techniques that are vital to any application development, Recursion being principal among them. I use recursion in my day-to-day programming almost as much as iteration!! An incredibly common recursion use case my be where your App creates a number of nested folders and there is a requirement to delete the root folder and all nested folders contained within it.
@alb12345672
@alb12345672 7 жыл бұрын
Better this than some math brain teaser algo under time pressure.
@_slier
@_slier 4 жыл бұрын
shit! ( unwrap the shit ) i will never be able to create my own compiler..building the tree itself is confusing let alone traversing it..
Interview Algorithm Challenge: Reverse Linked List - Swift
11:23
Lets Build That App
Рет қаралды 20 М.
Scary Programming Terms - Abstract Syntax Tree
22:40
Jack Mott
Рет қаралды 11 М.
터키아이스크림🇹🇷🍦Turkish ice cream #funny #shorts
00:26
Byungari 병아리언니
Рет қаралды 27 МЛН
Super gymnastics 😍🫣
00:15
Lexa_Merin
Рет қаралды 108 МЛН
Please be kind🙏
00:34
ISSEI / いっせい
Рет қаралды 180 МЛН
Swift 3 Fun Algorithms: Recursive Search through Binary Tree
16:34
Lets Build That App
Рет қаралды 22 М.
Compilation - Part Three: Syntax Analysis
22:05
Computer Science
Рет қаралды 38 М.
Parsing Explained - Computerphile
14:58
Computerphile
Рет қаралды 239 М.
Walking The AST - Programming Language From Scratch
25:43
tylerlaceby
Рет қаралды 13 М.
Inverting Binary Trees - You Suck at Coding [1]
10:19
Ben Awad
Рет қаралды 360 М.
Swift Fun Algorithms #6: Fibonacci Sequence
12:51
Lets Build That App
Рет қаралды 15 М.
Parsing Algorithms. Lecture [5/22] Abstract Syntax Trees
12:59
Dmitry Soshnikov
Рет қаралды 43 М.
Swift 3 Fun Algorithms: Filter, Map, Reduce Higher Order Functions
10:39
Lets Build That App
Рет қаралды 32 М.
터키아이스크림🇹🇷🍦Turkish ice cream #funny #shorts
00:26
Byungari 병아리언니
Рет қаралды 27 МЛН