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

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

iOS Basic Training Course

Completed Source Code

[johnnyAustria]

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 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 = node.operation!)
return node.leftChild!), evaluate(node: node.rightChild!))
}

Not sure its any shorter, but I still had fun writing it.

[kryptoshi]

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

[andreychirkov]

Fantastic! Looking forward next Friday episode

[xShorDz]

I think this is the best gift for my today's birthday, thank you Brian!

[stevenhans]

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

[ProgrammerinToronto]

Thank you for your awesome algorithm show! can't wait to see next time.

[MThomasson]

Excellent video once again. I've learnt so much from you! Looking forward to next vid.

[yanxu]

So clear! My professor is useless. Thank you.

[robertcharmers]

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.

[aleksejsigaj]

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

[kennygrandberry]

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.

[JayJay-kimi]

I'm having a similar problem parsing GraphQL's AST. Nested fields and arguments can be nested so deep. I learned this at University 20 years ago and forgot everything 😓

[ypaut]

Greetings, what is the editor you are using? Thank you for the video.

[cesarcontreras]

hey, I would like to see a video about MVP pattern with Swift. Nice video tho, great job!

[PythonPlusPlus]

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

[thedrei]

yeah, want more algo videos like this one

[JeffKang]

Which code editor feature puts those evaluation numbers on the right column? Thanks for the video.

[StunnerAlpha]

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?

[engen]

Hi Brian, Are you planing to cover all the data structure and algorithms on friday episode?

[geomichelon]

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?