Gold Challenge Solution Chapter 23

Swift Programming (3rd Edition) 23. Error Handling
1

I got pretty stuck on this for a while, figured someone else might appreciate the assist.
The following is how I implemented it. You might need to change around some other details but the core of it is below. Not sure how optimal it is but it seems to work.

func getNextExpression(_ value: Int) throws -> Int {
        guard let token = getNextToken() else {
            return value
        }
        let value2 = try getNextNumber()
        switch token {
        case .plus, .minus, .multiply:
            let value3: Int
            switch token {
            case .plus:
                value3 = try getNextExpression(value2)
                return value + value3
            case .minus:
                value3 = try getNextExpression(value2)
                return value - value3
            case .multiply:
                value3 = try getNextExpression(value * value2)
                return value3
            case .number(let value):
                throw Parser.Error.invalidToken(.number(value))
            }
        case .number(let value):
            throw Parser.Error.invalidToken(.number(value))
        }
    }

func parse() throws -> Int {
        
        var initialValue = try getNextNumber()
        
        var value = try getNextExpression(initialValue)
        
        while positon < tokens.count {
            value = try getNextExpression(value)
        }
        
        return value
    }
2

I don’t have the whole picture, but is the while-statement really needed? The getNextExpression function recursively consumes the entire input.

3

Sorry, my bad. Thanks for pointing that out, turns out it wasn’t actually working.

getNextExpression should look like this:

func getNextExpression(_ value: Int) throws -> Int {
        guard let token = getNextToken() else {
            return value
        }
        let nextToken: Token? = peekNextToken()
        let value2 = try getNextNumber()
        switch token {
        case .plus, .minus, .multiply:
            let value3: Int
            switch token {
            case .plus:
                value3 = try getNextExpression(value2)
                return value + value3
            case .minus:
                value3 = try getNextExpression(value2)
                return value - value3
            case .multiply:
                switch nextToken {
                case .multiply:
                    value3 = try getNextExpression(value * value2)
                default:
                    value3 = value * value2
                }
                return value3
            case .number(let value):
                throw Parser.Error.invalidToken(.number(value))
            }
        case .number(let value):
            throw Parser.Error.invalidToken(.number(value))
        }
    }

I realise it’s not exactly elegant. I ran into a bit of a trap trying not to rewrite too much, bit of a sunk cost situation.
The previous one didn’t actually work on any complex combos it just passed the examples in the book (from memory). However if you started subtracting after a multiplication it didn’t work.

So in this version the while loop is needed as originally intended as addition and subtraction move through the series of expressions recursively but multiplication returns to the top layer if the following token is addition or subtraction. The while loop then starts with the recursion again with the current working value.

I also added a peek method to make this possible:

   func peekNextToken() -> Token? {
        guard positon + 1 < tokens.count else {
            return nil
        }
        let token = tokens[positon + 1]
        return token
    }

The whole thing is as follows:

enum Token: CustomStringConvertible {
    case number(Int)
    case plus
    case minus
    case multiply
    
    var description: String {
        switch self {
        case .number(let n):
            return "Number: \(n)"
        case .plus:
            return "Symbol: +"
        case .minus:
            return "Symbol: -"
        case .multiply:
            return "Symbol: *"
        }
    }
}


class Lexer {
    enum Error: Swift.Error {
        case invalidCharacter(Character)
    }
    
    let input: String
    var positon: String.Index
    
    
    init(input: String) {
        self.input = input
        self.positon = input.startIndex
    }
    
    func peek() -> Character? {
        guard positon < input.endIndex else {
            return nil
        }
        return input[positon]
    }
    
    func advance() {
        assert(positon < input.endIndex, "Cannot advance past endIndex")
        positon = input.index(after: positon)
    }
    
    func getNumber() -> Int {
        var value: Int = 0
        
        while let nextCharacter = peek() {
            switch nextCharacter {
            case "0" ... "9":
                let digitValue = Int(String(nextCharacter))!
                value = value*10 + digitValue
                advance()
            default:
                return value
            }
        }
        return value
    }
    
    func lex() throws -> [Token] {
        var tokens = [Token]()
        
        while let nextCharacter = peek() {
            switch nextCharacter {
            case "0" ... "9":
                let value = getNumber()
                tokens.append(.number(value))
                break // TODO: real work
            case "+":
                tokens.append(.plus)
                advance()
            case "-":
                tokens.append(.minus)
                advance()
            case "*":
                tokens.append(.multiply)
                advance()
            case " ":
                advance()
            default:
                throw Lexer.Error.invalidCharacter(nextCharacter)
            }
        }
        return tokens
    }
}

class Parser {
    
    enum Error: Swift.Error {
        case unexpectedEndOfInput
        case invalidToken(Token)
    }
    
    let tokens: [Token]
    var positon: Int = 0
    
    init(_ tokens: [Token]) {
        self.tokens = tokens
    }
    
    func getNextToken() -> Token? {
        guard positon < tokens.count else {
            return nil
        }
        let token = tokens[positon]
        positon += 1
        return token
    }
    
    func peekNextToken() -> Token? {
        guard positon + 1 < tokens.count else {
            return nil
        }
        let token = tokens[positon + 1]
        return token
    }
    
    func getNextNumber() throws -> Int {
        guard let nextToken = getNextToken() else {
            throw Parser.Error.unexpectedEndOfInput
        }
        switch nextToken {
        case .number(let value):
            return value
        case .plus:
            throw Parser.Error.invalidToken(.plus)
        case .minus:
            throw Parser.Error.invalidToken(.minus)
        case .multiply:
            throw Parser.Error.invalidToken(.multiply)
        }
    }
    
    func getNextExpression(_ value: Int) throws -> Int {
        guard let token = getNextToken() else {
            return value
        }
        let nextToken: Token? = peekNextToken()
        let value2 = try getNextNumber()
        switch token {
        case .plus, .minus, .multiply:
            let value3: Int
            switch token {
            case .plus:
                value3 = try getNextExpression(value2)
                return value + value3
            case .minus:
                value3 = try getNextExpression(value2)
                return value - value3
            case .multiply:
                switch nextToken {
                case .multiply:
                    value3 = try getNextExpression(value * value2)
                default:
                    value3 = value * value2
                }
                return value3
            case .number(let value):
                throw Parser.Error.invalidToken(.number(value))
            }
        case .number(let value):
            throw Parser.Error.invalidToken(.number(value))
        }
    }
    
    
    
    func parse() throws -> Int {
        
        var initialValue = try getNextNumber()
        var value = try getNextExpression(initialValue)
        while positon < tokens.count {
            value = try getNextExpression(value)
        }
        return value
    }
}

func evaluate(_ input: String) {
    let lexer = Lexer(input: input)
    do {
        let tokens = try lexer.lex()
        print("Lexer output: \(tokens)")
        let parser = Parser(tokens)
        let result = try parser.parse()
        print("Parser output: \(result)")
    }catch Lexer.Error.invalidCharacter(let character){
        print("Invalid character detected at index \(input.distance(from: input.startIndex, to: lexer.positon)): \(character)")
    } catch Parser.Error.unexpectedEndOfInput {
        print("Unexpected end of input while parsing")
    } catch Parser.Error.invalidToken(let token) {
        print("Invalid token during parsing at index \(input.distance(from: input.startIndex, to: lexer.positon)): \(token)")
    }  catch {
        print("An error occured: \(error)")
    }
}
1 Like
4

Thank you for sharing the code.

It would be a really fun exercise to add the division and remainder operators, with the remainder operator having lower precedence than the division and multiplication, but higher precedence than the addition and subtraction.

Operator              Precedence
------------------    -----------
addition (+)             1
subtraction (-)          1
multiplication (*)       3
division (/)             3
remainder (%)            2
5

Tidy looking code, thanks for sharing. Try " 1 - 3 * 3 + 1". That’s the issue that got me stuck. Only solution I found was looking at the next operator.

The precedence challenge is interesting. I’m not really sure how to modify the control flow in a non janky way.

Will have a think and get back. I’m leaning to operator tokens getting a second parameter which is the assigned precedence. Then following a similar pattern to above but switching on the precedence instead of the operator. I can imagine it working for two levels of precedence but I’m not sure how you would approach 3 or more layers.

6

Before tackling the operator precedence challenge, an easier but really useful exercise would be to parse an input expression from left to right, assigning all binary operators equal precedence, and also introducing two new tokens lparen ‘(’ and rparen ‘)’ for grouping sub-expressions.

1 - (3 * 3) + 1

Another approach might look like this, introducing a new operator type for each operator token:

Summary 
//
//  Parser-Operator.swift
//  SwiftJam
//
//  Created by ibex on 23/8/2023.
//

// -------------------------------------------
//
protocol _Operator : CustomStringConvertible {
    var precedence : Int {get}
    func input (_: Int, _: Int) -> Int
}

extension BNR.Parser {
    typealias Operator = _Operator
}

extension BNR.Parser {
    func `operator` (from t: Token) throws -> Operator {
        if case .plus = t {
            return PlusOperator ()
        }
        
        if case .minus = t {
            return MinusOperator ()
        }
        
        if case .multiply = t {
            return MultiplyOperator ()
        }
        
        if case .divide = t {
            return DivideOperator ()
        }
        
        if case .modulo = t {
            return ModuloOperator ()
        }
        
        throw "undefined operator `\(t)`"
    }
}

extension BNR.Parser {
    struct PlusOperator : Operator {
        var precedence : Int {1}
        
        func input (_ u: Int, _ v : Int) -> Int {
            u + v
        }
        
        var description: String {
            "+"
        }
    }
    
    struct MinusOperator : Operator {
        var precedence : Int {1}
        
        func input (_ u: Int, _ v : Int) -> Int {
            u - v
        }
        
        var description: String {
            "-"
        }
    }
    
    struct MultiplyOperator : Operator {
        var precedence : Int {3}
        
        func input (_ u: Int, _ v : Int) -> Int {
            u * v
        }
        
        var description: String {
            "*"
        }
    }
    
    struct DivideOperator : Operator {
        var precedence : Int {3}
        
        func input (_ u: Int, _ v : Int) -> Int {
            guard v != 0 else {
                fatalError ("zero divisor")
            }
            return u / v
        }
        
        var description: String {
            "/"
        }
    }
    
    struct ModuloOperator : Operator {
        var precedence : Int {2}
        
        func input (_ u: Int, _ v : Int) -> Int {
            guard v > 0 else {
                fatalError ("divisor <= 0")
            }
            let r = u % v
            if r < 0 {
                return r + v
            }
            else {
                return r
            }
        }
        
        var description: String {
            "%"
        }
    }
}

After tackling all these challenges, a really good educational exercise would be to redesign the parser so that it returns the abstract syntax tree of an input expression, instead of returning an Int.

protocol Expr {
   func prettyPrint ()
   func evaluate () -> Int
}

class BinaryExpr: Expr {
   let lhs: Expr
   let rhs: Expr
}

class Add: BinaryExpr {
   ...
}

class Subtract: BinaryExpr {
  ...
}
...

func parse () -> Expr? {
   ...
}