We built a pretty trivial expression parser for prefix notation mathematic operations.
For example:
( + ( + 4 ( * 7 8 ) ) ( * 10 31 ) )
// 370
We looked at parsing a String into an [String] and recursively pulling it apart. There are a few String comparisions and Int casting which can sometimes be a little error prone, but it works.
The other day I was browsing the Swift Language docs and re-read through the Enumeration type. At the bottom there is a section under the Associated Types named Recursive Enumerations. A Recursive Enumeration is defined as an Enumeration that has another instance of the Enumeration as an associated value for one or more of the cases. The example they give stuck out:
indirect enum ArithmeticExpression {
case integer(Int)
case addition(ArithmeticExpression, ArithmeticExpression)
case multiplication(ArithmeticExpression, ArithmeticExpression)
}
In Part 1, the expression parsing code handled all three cases as, but we just used the String type to encode each expression when we could have leaned on the Swift’s Type system a bit more.
With the ArithmeticExpression Type we can reduce some complexity around how we apply expressions together. We can instead use an instance of this Type and switch over its possible cases. This should make the recursion feel much more safe and perhaps easier to reason about.
Here is a new version of the apply function we wrote. Let’s call it eval like the documentation, we’ll also change the integer case to be operand to align with the expression syntax:
func eval(_ expression: ArithmeticExpression) -> Int {
switch expression {
case let .operand(value):
return value
case let .addition(left, right):
return eval(left) + eval(right)
case let .multiplication(left, right):
return eval(left) * eval(right)
}
}
Let’s use the ArithmeticExpression type from the docs and make a few simple changes to our code to use this type instead.
Before we can evaluate an ArithmeticExpression we need to convert the [String] to a single ArithmeticExpression. Converting information from one format to another is called encoding. Let’s write an encode function:
func encode(_ components: inout [String]) -> ArithmeticExpression {
// ...
}
This looks quite a bit like the signature of our original eval from Part 1. However instead of an Int, we’ll return the concrete Enumeration Type. The shape of this function will look nearly the same as our original recursive function however, except for the bit at the end.
After the function determines the operator and the two operands, what we want to do is create an instance of the ArithmeticExpression corresponding to the operator:
switch op {
case "+":
return ArithmeticExpression.addition(left, right)
case "*":
return ArithmeticExpression.multiplication(left, right)
default:
throw ArithmeticExpressionError
.encodingError(
"Operator: \(op) not supported!"
)
}
Here, we can cleanly encode the expression into concrete a Type and throw a sensible error in the event the parsing finds an operator that is not supported. Here is our encoder:
// Converts an array of Strings to a single ArithmeticExpression
func encode(_ components: inout [String]) throws -> ArithmeticExpression {
let first = components.removeFirst()
if first != "(" {
print(first)
return ArithmeticExpression.operand(Int(first)!)
}
let op = components.removeFirst()
let left = try encode(&components)
let right = try encode(&components)
components.removeFirst()
switch op {
case "+":
return ArithmeticExpression.addition(left, right)
case "*":
return ArithmeticExpression.multiplication(left, right)
default:
throw ArithmeticExpressionError
.encodingError(
"Operator: \(op) not supported!"
)
}
}
Finally, our helper function should try to encode the [String] and then return the result of the eval’d ArithmeticExpression.
func evaluate(expression: String) -> Int {
var components = expression.components(separatedBy: " ")
let arithmeticExpression = try! encode(&components)
return eval(arithmeticExpression)
}
Sure, this looks nicer and maybe feels more Swift-like but we did make some tradeoffs.
There is more code this time which usually means more room for bugs. I would argue the additional code, the ArithmeticExpression type and its evaluation function makes our parsing a bit more robust. Safer, even. We moved logic out of our code and moved it closer to the Type itself. We also have a clean place to throw an error.
I wonder now, after looking at this refactor are we recursing twice? Once through the entire String expression and then a second time through the ArithmeticExpression object graph? It appears so. The object graph (I think) are just pointers in memory, so I’m going to hazard a guess that’s a constant time complexity.
Maybe that’s not awesome for really a large expression, though?
Think about the previous implementation and how you would extend it to include additional operations like subtraction - or maybe division % (🧐). That apply function we wrote suddely gets more complicated. Now consider this complexity as an extension to our Type. We would need to add a new case or two to our Type and then update the switch statement to create the new cases of our Enumeration and then lastly the eval to perform the proper math.
That code feels safer to me because it is isolated to the Type itself and it not tightly coupled with the program’s logic. Extending the Type feels more safe to me.
Swift’s Enumerations are really robust and can help make code cleaner-looking and easier to reason about.
Cheers 🍺!