Bronze & Silver Challenge: Ch 20

Note: I didn’t complete the Gold challenge because I kind-of gave up after 2 hours. I think I had the right approach, but I couldn’t really figure out the order of the expressions. I tried creating a function to reorder the tokens before parsing so that it worked out alright, but that messed up my positions…I’d love to see someone’s solution if anyone gets around to it

Bronze Challenge:

For this, we have to do a bit of shuffling of the code. Add a minus case in the global enum:

enum Token {
    case number(Int)
    case plus
    case minus
}

Next, we just have to enter some code in the Lexer and Parser in order to handle it, and it’ll compile successfully:

class Lexer {
    ...
    func lex() throws -> [Token] {
        var tokens = [Token]()

        while let nextCharacter = peek() {
            switch nextCharacter {
                case "0" ... "9":
                    let value = getNumber()
                    tokens.append(.number(value))
                case "+":
                    tokens.append(.plus)
                    advance()
                case "-":
                    tokens.append(.minus)
                    advance()
                case " " :
                    // Just advance to ignore spaces
                    advance()
                default:
                    throw Lexer.Error.invalidCharacter(nextCharacter)
            }
        }
        return tokens
    }
}
...
class Parser {
    ...
    func getNumber() throws -> Int {
        guard let token = getNextToken() else {
            throw Parser.Error.unexpectedEndOfInput
        }

        switch token {
            case .number(let value):
                return value
            case .plus, .minus:
                throw Parser.Error.invalidToken(token)
        }
    }

    func parse() throws -> Int {
        // Require a number first
        var value = try getNumber()

        while let token = getNextToken() {
            switch token {
                case .plus:
                    // After a plus, we must get another number
                    let nextNumber = try getNumber()
                    value += nextNumber
                case .minus:
                    let nextNumber = try getNumber()
                    value -= nextNumber
                case .number:
                    throw Parser.Error.invalidToken(token)
            }
        }
        return value
    }

Silver Challenge:

This challenge threw me for a bit of a loop. Determining the position of incorrect information during the lexing phase was easy enough: in the catch block for catching a Lexer error, determine the position at that point and return it (using the statement given in the challenge itself:

func evaluate(_ input: String) {
    ...
    do {...} 
    catch Lexer.Error.invalidCharacter(let character) {
        let distanceToPosition = input.distance(from: input.startIndex, to: lexer.position)
        print("Input contained an invalid character at index \(distanceToPosition): \(character)")
    }
    ...
}

Determining the position of the parsing error was a bit tricky. At first, I used the same line to determine the parsing position when an error was thrown. However, this resulted in a position that was obviously out of bounds of the input string (getting an index of 16 when the input was only 15 characters long). I needed to dig a bit deeper.

Note: Unfortunately, the solution I came up with doesn’t feel satisfactory to me, but it’s the best I could do without spending hours to solve it (really don’t want to do that right now). Let’s break it down.

First, I created another variable (positionInInput) in the Parser class to hold onto the current position information. This one will be tracking things slightly different from the position value we made in the chapter–it’s not determining the position of the token, it is adding ints to itself every time getNumber() and the actual parse-ing occurs. To make sure we are holding onto the right values, I converted the numbers into Strings and counted the characters, adding a 1 to signify a space in the input. (I REALLY don’t like this, because I’m basically assuming that every token provided will be separated by a space, which doesn’t necessarily happen. But I’m assuming it for now).

Next, I added a value to the invalidToken enum to accept an additional Int, invalidToken(Token, Int). This is so that when the error is thrown, we can also throw the positionInInput value to the catch block. I also added another Error, invalidInt(Int, Int), so that the number is reported in the catch statement instead of .number(3)

I’m just going to attach my entire Parser and evaluate(_:) function, because there was a bit of rearranging going on that I didn’t really keep track of.

class Parser {

    enum Error: Swift.Error {
        case unexpectedEndOfInput
        case invalidInt(Int, Int)
        case invalidToken(Token, Int)
    }

    let tokens: [Token]
    var position = 0
    var positionInInput = 0

    init(tokens: [Token]) {
        self.tokens = tokens
    }

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

    func getNumber() throws -> Int {
        guard let token = getNextToken() else {
            throw Parser.Error.unexpectedEndOfInput
        }

        switch token {
            case .number(let value):
                positionInInput += String(value).characters.count + 1
                return value
            case .plus, .minus:
                throw Parser.Error.invalidToken(token, positionInInput)
        }
    }

    func parse() throws -> Int {
        // Require a number first
        var value = try getNumber()

        while let token = getNextToken() {
            switch token {
                case .plus:
                    // After a plus, we must get another number
                    let nextNumber = try getNumber()
                    positionInInput += String(nextNumber).characters.count + 1
                    value += nextNumber
                case .minus:
                    let nextNumber = try getNumber()
                    positionInInput += String(nextNumber).characters.count + 1
                    value -= nextNumber
                case .number:
                    throw Parser.Error.invalidInt(value, positionInInput)
            }
        }
        return value
    }
}

func evaluate(_ input: String) {
    print("Evaluating: \(input)")
    let lexer = Lexer(input: input)

    do {
        let tokens = try lexer.lex()
        print("Lexer output: \(tokens)")
        let parser = Parser(tokens: tokens)
        let result = try parser.parse()
        print("Parser output: \(result)")
    } catch Lexer.Error.invalidCharacter(let character) {
        let distanceToPosition = input.distance(from: input.startIndex, to: lexer.position)
        print("Input contained an invalid character at index \(distanceToPosition): \(character)")
    } catch Parser.Error.unexpectedEndOfInput {
        print("Unexpected end of input during parsing")
    } catch Parser.Error.invalidInt(let (value, position)) {
        print("Invalid number during parsing at index \(position): \(value)")
    } catch Parser.Error.invalidToken(let (token, position)) {
        print("Invalid token during parsing at index \(position): \(token)")
    } catch {
        print("An error occurred: \(error)")
    }
}

evaluate("10 + 5 - 3 - 1")
evaluate("10 + 5 - 3 - a")
evaluate("10 - 3 - 1 - 1 - 1 1")
evaluate("10 - 3 3 + 5")

By all means, if someone can give me a better solution, I’m more than welcome to hear it!

Some Improvements

Lexer
The lexer is closer to the input stream, so it can add the position information to the Token objects. Also rather than throwing an exception it can return an error token for any unrecognised token it encounters.

struct Locus {
   let lineNo: UInt
   let charNo: UInt
}

enum Token {
    case number (pos:Locus, value:Int)
    case plus   (pos:Locus)
    case minus  (pos:Locus)
    case mul    (pos:Locus)
    case div    (pos:Locus)
    case lparen (pos:Locus)   // to force operator precedence: for example, 2 * (3 + 5)
    case rparen (pos:Locus)   //
    case error  (pos:Locus, details:String)
    case endOfStream
}

Parser
Rather than also evaluating arithmetic expressions, the parser can just focus on parsing and return an Abstract Syntax Tree object for arithmetic expressions.

enum UnaryOperator {
    case negate

    func op (_ v:Int) -> Int {
        switch self {
        case .negate:
            return -v
        }
    }
}
enum BinaryOperator {
    case plus
    case minus
    
    func op (_ v1:Int, _ v2:Int) -> Int {
        switch self {
        case .plus:
            return v1 + v2
        case .minus:
            return v1 - v2
        }
    }
}
protocol Expr {
    var value : Int {get}
}
struct Number : Expr {
    var value : Int
}
struct BinaryExpr : Expr {
    let binOp     : BinaryOperator
    let leftExpr  : Expr
    let rightExpr : Expr
    
    var value : Int {
        return binOp.op (leftExpr.value, rightExpr.value)
    }}
struct UnaryExpr : Expr {
    let unaryOp : UnaryOperator
    let expr    : Expr
    
    var value : Int {
        return unaryOp.op (expr.value)
    }
}

The parser also needs to address the issue of operator precedence in binary expressions, but that is probably too much to go into here (see the comments above in Token.)

I think my problem was just that I was trying to work with the code given instead of trying to find a new approach. Thanks for sharing what you’ve done! Definitely good insight

I got Gold solution…sort of brute force:

Basically, I created another function that removes a single multiply or division operation from an array of Tokens:
func removeMultDiv(_ tokens: [Tokens]) -> [Tokens]

So, a token array derived from “2+35+2" would return a token array representing “2+15+2”. Another example, a token array derived from "1+6/3+45” would return a token array representing “1+2+4*5”

Next, I added recursiveness to the function removeMultDiv so that it completely transforms input into a token array with only additions/subtractions operations.

Then, I applied this array of tokens to the function as built in the book, which only supports addition/subtraction.