Silver Challenge


#1
import Cocoa

enum Token {
  case Number(Int)
  case Plus
  case Minus
}

class Lexer {
  enum Error: ErrorType {
    case InvalidCharacter(Character, String.CharacterView.Index)
  }
  
  let input: String.CharacterView
  var position: String.CharacterView.Index
  
  init(input: String) {
    self.input = input.characters
    self.position = self.input.startIndex
  }
  
  func peek() -> Character? {
    guard position < input.endIndex else {
      return nil
    }
    return input[position]
  }
  
  func advance() {
    assert(position < input.endIndex, "Cannot advance past the end!")
    ++position
  }
  
  func getNumber() -> Int {
    var value = 0
    
    while let nextCharacter = peek() {
      switch nextCharacter {
      case "0" ... "9":
        // Another digit - add it into value
        let digitValue = Int(String(nextCharacter))!
        value = 10 * value + digitValue
        advance()
      default:
        // A non-digit - go back to regular lexing
        return value
      }
    }
    return value
  }
  
  func lex() throws -> [Token] {
    var tokens = [Token]()
    
    while let nextCharacter = peek() {
      switch nextCharacter {
      case "0" ... "9":
        // Start of a number - need to grab the rest
        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:
        // Someone unexpected - need to send back an error
        throw Error.InvalidCharacter(nextCharacter, position)
      }
    }
    return tokens
  }
}

class Parser {
  enum Error: ErrorType {
    case UnexpextedEndOfInput
    case InvalidToken(Token, Int)
  }
  
  let tokens: [Token]
  var position = 0
  
  init(tokens: [Token]) {
    self.tokens = tokens
  }
  
  func getNextToken() -> Token? {
    guard position < tokens.count else {
      return nil
    }
    return tokens[position++]
  }
  
  func getNumber() throws -> Int {
    guard let token = getNextToken() else {
      throw Error.UnexpextedEndOfInput
    }
    
    switch token {
    case .Number(let value):
      return value
    case .Plus, .Minus:
      throw Error.InvalidToken(token, --position)
    }
  }
  
  func parse() throws -> Int {
    // Require a number first
    var value = try getNumber()
    
    while let token = getNextToken() {
      switch token {
      // Getting a Plus after number is legal
      case .Plus:
        // After a Plus, we must get another number
        let nextNumber = try getNumber()
        value += nextNumber
      case .Minus:
        let nextNumber = try getNumber()
        value -= nextNumber
      // Getting a Number after a Number is not legal
      case .Number:
        throw Error.InvalidToken(token, --position)
      }
    }
    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 index) {
    print("Item contined an invalid character at index \(index): \(character)")
  } catch Parser.Error.UnexpextedEndOfInput {
    print("Unexpected end of input during parsing")
  } catch Parser.Error.InvalidToken(let token, let index) {
    switch token {
    case .Number(let number):
      print("Invalid token during parsing at index \(index): \(number)")
    case .Minus, .Plus:
      print("Invalid token during parsing at index \(index): \(token)")
    }
  } catch {
    print("An error occurred: \(error)")
  }
  
}
// Invalid token during parsing at index 4: Minus
evaluate("10 + 5 - - 3 - 1")

#2

Hello,

I’ve been struggling with this Silver Challenge for the past couple of days. I was able to solve the first part for the example “1 + 3 + 7a + 8” and get the response “Input contained an invalid character at index 9: a”. But for the second example, “10 + 3 3 + 7”, I cannot figure out how to get the parser to return the index of the problematic number in the original input string. The response should indicate the index is “7”. The best I can do is return the index in the token list, which is “3”. This is the same as is given by the Pseudowolf’s code.

What am I missing? :question:

Mark


#3

My implementation for the silver challenge was to create an array where each element is a String.CharacterView.Index of the beginning of each token and then pass that on to the parser, which can then reference that array when it hits an error. One gotcha is getNextToken() increments the position in the return statement, so you have to look at the previous token when handling the error.

Evaluating: 10 + 3 3 + 7
Invalid token during parsing at index 7: 3

[code]func lex() throws -> ([Token], [String.CharacterView.Index]) {
var tokens = Token
var tokenIndex: [String.CharacterView.Index] = []

    // Loop through input[String] until end is reached
    while let nextCharacter = peek() {
        switch nextCharacter {
        case "0" ... "9":
            // Start of a number - need to grab the rest
            tokenIndex.append(position)
            let value = getNumber()
            tokens.append(.Number(value))
            
        case "+":
            tokenIndex.append(position)
            tokens.append(.Plus)
            advance()
            
        case "-":
            tokenIndex.append(position)
            tokens.append(.Minus)
            advance()
            
        case " ":
            // advance() to ignore spaces
            advance()
            
        default:
            // Something unexpected happened
            throw Error.InvalidCharacter(nextCharacter, position)
        }
    }
    print(tokenIndex)
    return (tokens, tokenIndex)
}

class Parser {

enum Error: ErrorType {
    case UnexepectedEndOfInput
    case InvalidToken(Token, String.Index)
}

let tokens: [Token]
let tokenIndex: [String.CharacterView.Index]
var position = 0

init(tokens: [Token], tokenIndex: [String.CharacterView.Index]) {
    self.tokens = tokens
    self.tokenIndex = tokenIndex
}

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

func getNumber() throws -> Int {
    guard let token = getNextToken() else {
        throw Error.UnexepectedEndOfInput
    }
    
    switch token {
    case .Number(let value):
        return value
    case .Plus:
        // getNextToken() advances position before we verify the token, so we have
        // return the previous token index
        let errorPosition = position - 1
        throw Error.InvalidToken(token, tokenIndex[errorPosition])
    case .Minus:
        let errorPosition = position - 1
        throw Error.InvalidToken(token, tokenIndex[errorPosition])

    }
    
}

func parse() throws -> Int {
    // Get the first token which has to be a number
    var value = try getNumber()
    
    while let token = getNextToken() {
        switch token {
            
        case .Plus:
            // After a plus the next token must be a number
            let nextNumber = try getNumber()
            value += nextNumber
            
        case .Minus:
            let nextNumber = try getNumber()
            value -= nextNumber
            
        // Cant get a number token after another number token.
        case .Number:
            let errorPosition = position - 1
            throw Error.InvalidToken(token, tokenIndex[errorPosition])
        }
        
    }
    return value
}

}

[/code]


#4

My solution was to use the reference we already have to the lexer.position which references the String.CharacterView.Index already. It’s a simple solution but it works. :confused: Maybe I’m missing something here…

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) {
        print("Input contained an invalid character at index \(lexer.position): \(character)")
    } catch Parser.Error.UnexpectedEndOfInput {
        print("Unexpected end of input during parsing at index \(lexer.position)")
    } catch Parser.Error.InvalidToken(let token) {
        print("Invalid token during parsing at index \(lexer.position): \(token)")
    } catch {
        print("An error occurred: \(error)")
    }
}

#5

[quote=“astericky”]My solution was to use the reference we already have to the lexer.position which references the String.CharacterView.Index already. It’s a simple solution but it works. :confused: Maybe I’m missing something here…
[/quote]

Well, this works fine for the Lexer.Error handling. However, the Parser runs after the Lexer, so calling a Lexer property from within a Parser:Error handler will not give you what you’re expecting - it will always just return the final value of lexer.position.

I chose to have the Lexer build an [Int] of position values for each token:

[code] var tokenIndex = Int

func lex() throws -> ([Token], [Int]) {
    var tokens = [Token]()
    
    while let nextCharacter = peek() {
        switch nextCharacter {
        case "0" ... "9":
            tokenIndex.append(Int(String(position))!)
            let value = getNumber()
            tokens.append(.Number(value))
            
        case "+":
            tokenIndex.append(Int(String(position))!)
            tokens.append(.Plus)
            advance()

        case "-":
            tokenIndex.append(Int(String(position))!)
            tokens.append(.Minus)
            advance()
        
        case " ":
            advance()
            
        default:
            throw Error.InvalidCharacter(nextCharacter, position)
        }
    }
    return (tokens, tokenIndex)
}

[/code]
Which then gets passed to the parser along with the tokens. The parser maintains an index counter into the array, incrementing it every time it advances to the next token, and the error handlers use tuples to pass the multiple values involved.

[code]class Parser {
enum Error: ErrorType {
case UnexpectedEndOfInput
case InvalidToken(Token, Int)
}

let tokens: [Token]
let tokenIndex: [Int]
var tokenCounter = 0
var position = 0

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

func getNextToken() -> Token? {
    guard position < tokens.count else {
        return nil
    }
    tokenCounter += 1
    // oy, increment/decrement operators are deprecated
    // return tokens[postiion++]
    let returnToken = tokens[position]
    position += 1
    return returnToken
}

func getNumber() throws -> Int {
    guard let token = getNextToken() else {
        throw Error.UnexpectedEndOfInput
    }
    switch token {
    case .Number(let value):
        return value

    // expecting a Number, any other Token value is an error - point to it, then throw
    case .Plus, .Minus:
        throw Error.InvalidToken(token, tokenIndex[tokenCounter - 1])
    }
}

func parse() throws -> Int {
    // require a number first
    var value = try getNumber()
    
    while let token = getNextToken() {
        switch token {
        // getting a Plus after a Number is legal
        case .Plus:
            let nextNumber = try getNumber()
            value += nextNumber
            
        // getting a Minus after a Number is legal
        case .Minus:
            let nextNumber = try getNumber()
            value -= nextNumber
            
        // getting a Number after a Number is not legal
        case .Number:
            throw Error.InvalidToken(token, tokenIndex[tokenCounter - 1])
        }
    }
    return value
}

}

func evaluate(input: String) {
print(“Evaluating (input)”)
let lexer = Lexer(input: input)

do {
    let (tokens, tokenIndex) = try lexer.lex()
    print("Lexer output: \(tokens)")
    
    let parser = Parser(tokens: tokens, tokenIndex: tokenIndex)
    let result = try parser.parse()
    print("Parser output: \(result)")
} catch Lexer.Error.InvalidCharacter(let (character, index)) {
    print("Input contained an invalid character at index \(index): \(character)")
} catch Parser.Error.UnexpectedEndOfInput {
    print("Unexpected end of input during parsing")
} catch Parser.Error.InvalidToken(let (token, index)) {
    print("Invalid token during parsing at index \(index): \(token)")
} catch {
    print("An error occurred: \(error)")
}

}
[/code]

evaluate("10 + 3 + 5") // Parser output: 18 evaluate("10 + 3 5") // Invalid token during parsing at index 7: Number(5) evaluate("10 + ") // Unexpected end of input during parsing evaluate("1 + 2 + abcdefg") // Input contained an invalid character at index 8: a evaluate("10 + 5 - 3") // Parser output: 12 evaluate("1 + 3 + 7a + 8") // Input contained an invalid character at index 9: a evaluate("10 + 3 3 + 7") // Invalid token during parsing at index 7: Number(3) evaluate("10 + 3 + - 7") // Invalid token during parsing at index 9: Minus evaluate("10 + 3 + + 7") // Invalid token during parsing at index 9: Plus


#6

Hi marcopolo, please have a look at my solution where I solved that issue:


#7

Hi Pseudowolf, the second part of your solution is not correct, please have a look at mine:


#8

Hi astericky, your solution gives most of the time a wrong result in the line “print(“Invalid token during parsing at index (lexer.position): (token)”)”: for instance, in case you call “evaluate(“10 + 3 3 - 5”)” you get an index position at 12 instead of 7. Please have a look at my solution: