Solution for Ch 20 Bronze, Silver, and Gold Challenge in Xcode 9.3


#1
//  main.swift
import Foundation

enum Token: Equatable {
  case number(Int)
  case plus
  case minus
  case multiply
  case divide
  case blank
}

extension Token: CustomStringConvertible {
  var description: String {
    switch self {
    case .number(let value): return String(value)
    case .plus: return "+"
    case .minus: return "-"
    case .multiply: return "*"
    case .divide: return "/"
    case .blank: return "_"
    }
  }
}

class Lexer {
  enum Error: Swift.Error {
    case invalidCharacter(Character, String.Index)
  }

  let input: String
  var position: String.Index

  init(input: String) {
    self.input = input
    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 endIndex!")
    position = input.index(after: position)
  }

  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 "*":
        tokens.append(.multiply)
        advance()
      case "/":
        tokens.append(.divide)
        advance()
      case " ":
        advance()
      default:
        throw Lexer.Error.invalidCharacter(nextCharacter, position)
      }
    }
    return tokens
  }

  func getNumber() -> Int {
    var value = 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
  }
}

class Parser {
  enum Error: Swift.Error {
    case unexpectedEndOfInput([Token], Int)
    case invalidToken([Token], Int)
    case divisionByZero([Token])
    case unexpectedError
  }

  var tokens: [Token]

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

  func parse() throws -> Int {
    let initialTokens = tokens

    for (index, token) in tokens.enumerated() {
      if tokens.indices.contains(index + 1) {
        let nextToken = tokens[index + 1]
        if case .number = token, case .number = nextToken {
          throw Parser.Error.invalidToken(initialTokens, index + 1)
        }
      }
    }

    while true {
      let highPrecedenceOperatorToken = tokens.first(where: { $0 == Token.multiply || $0 == Token.divide})
      let lowPrecedenceOperatorToken = tokens.first(where: { $0 == Token.plus || $0 == Token.minus})

      let operatorToken: Token
      switch (highPrecedenceOperatorToken != nil, lowPrecedenceOperatorToken != nil) {
      case (true, _):
        operatorToken = highPrecedenceOperatorToken!
      case (_, true):
        operatorToken = lowPrecedenceOperatorToken!
      case (false, false):
        let resultTokens = tokens.filter { $0 != Token.blank }
        if resultTokens.count == 1,
          case .number(let value) = resultTokens[0] {
          return value
        } else {
          throw Parser.Error.unexpectedError
        }
      }

      let operatorIndex = tokens.index(of: operatorToken)!
      var token: Token

      var leftOperandIndex = operatorIndex
      repeat {
        leftOperandIndex -= 1
        if leftOperandIndex < 0 {
          throw Parser.Error.invalidToken(initialTokens, 0)
        }
        token = tokens[leftOperandIndex]
      } while token == .blank
      guard case .number(let leftValue) = token else {
        throw Parser.Error.invalidToken(initialTokens, leftOperandIndex)
      }

      var rightOperandIndex = operatorIndex
      repeat {
        rightOperandIndex += 1
        if rightOperandIndex == tokens.count {
          throw Parser.Error.unexpectedEndOfInput(initialTokens, rightOperandIndex)
        }
        token = tokens[rightOperandIndex]
      } while token == .blank
      guard case .number(let rightValue) = token else {
        throw Parser.Error.invalidToken(initialTokens, rightOperandIndex)
      }

      switch operatorToken {
      case .plus:
        tokens[operatorIndex] = .number(leftValue + rightValue)
      case .minus:
        tokens[operatorIndex] = .number(leftValue - rightValue)
      case .multiply:
        tokens[operatorIndex] = .number(leftValue * rightValue)
      case .divide:
        if rightValue == 0 {
          throw Parser.Error.divisionByZero(tokens)
        }
        tokens[operatorIndex] = .number(leftValue / rightValue)
      default: break
      }
      tokens[leftOperandIndex] = .blank
      tokens[rightOperandIndex] = .blank

//      print(tokens)   // uncomment to show steps
    }
  }
}

func evaluate(_ input: String) {
  func printErrorMessage(_ message: String, forTokens tokens: [Token], withErrorAt position: Int) {
    let expressionString = tokens.reduce("") { "\($0)\($1.description) " }
    var padding = tokens[..<position].reduce("") { "\($0)\($1.description) " }
    padding = repeatElement(" ", count: padding.count).joined(separator: "")
    print(expressionString)
    print(padding + "^\r" + padding + message)
  }

  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 position) {
    let distanceToPosition = input.distance(from: input.startIndex, to: position)
    let padding = repeatElement(" ", count: "Evaluating: ".count + distanceToPosition).joined(separator: "")
    print(padding + "^\r" + padding + "Invalid character: \(character)")
  } catch Parser.Error.unexpectedEndOfInput(let tokens, let position) {
    printErrorMessage("Unexpected end of input", forTokens: tokens, withErrorAt: position)
  } catch Parser.Error.invalidToken(let tokens, let position) {
    printErrorMessage("Parsing Error. Invalid token: \(tokens[position])", forTokens: tokens, withErrorAt: position)
  } catch Parser.Error.divisionByZero {
    print("Error: Division by zero")
  } catch Parser.Error.unexpectedError {
    print("Unexpected Error")
  } catch {
    print("An error occurred: \(error)")
  }
  print()
}

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

evaluate("10 * 3 + 5 * 3")      // Should print 45
evaluate("10 + 3 * 5 + 3")      // Should print 28
evaluate("10 + 3 * 5 * 3")      // Should print 55
evaluate("1 + 2 * 3 - 4 / 2")   // Should print 5
evaluate("2 * 8 / 0")           // Division by zero
evaluate("+ 3")

Output:

Evaluating: 1 + 3 + 7a + 8
                     ^
                     Invalid character: a

Evaluating: 10 +  3  8 + 7
10 + 3 8 + 7 
       ^
       Parsing Error. Invalid token: 8

Evaluating: 10 + 3 - 5
Parser output: 8

Evaluating: 10 + 3 5
10 + 3 5 
       ^
       Parsing Error. Invalid token: 5

Evaluating: 10 +
10 + 
     ^
     Unexpected end of input

Evaluating: 10 * 3 + 5 * 3
Parser output: 45

Evaluating: 10 + 3 * 5 + 3
Parser output: 28

Evaluating: 10 + 3 * 5 * 3
Parser output: 55

Evaluating: 1 + 2 * 3 - 4 / 2
Parser output: 5

Evaluating: 2 * 8 / 0
Error: Division by zero

Evaluating: + 3
+ 3 
^
Parsing Error. Invalid token: +

#2

My solution to the gold challenge (nothing fancy but it should be as close as possible to the hint given on the book):

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

extension Token: CustomStringConvertible {
    var description: String {
        switch self {
        case .number(let value):
            return String(value)
        case .plus:
            return "+"
        case .minus:
            return "-"
    
        case .multiply:
            return "*"
        case .divide:
            return "/"
        }
    }
}

class Lexer {
    enum Error: Swift.Error {
        case invalidCharacter(Character, Int)
    }
    let input: String
    var position: String.Index

    init(input: String) {
        self.input = input
        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 endIndex!")
        position = input.index(after: position)
    }

    func getNumber() -> Int {
        var value = 0
        while let nextCharacter = peek() {
            switch nextCharacter {
            case "0"..."9":
                let digitValue = Int(String(nextCharacter))!
                value = 10*value + 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))
            case "+":
                tokens.append(.plus)
                advance()
            case "-":
                tokens.append(.minus)
                advance()
            case "*":
                tokens.append(.multiply)
                advance()
            case "/":
                tokens.append(.divide)
                advance()
            case " ":
                advance()
            default:
                let index = input.distance(from: input.startIndex, to: position)
                throw Lexer.Error.invalidCharacter(nextCharacter, index)
            }
        }
    
        return tokens
    }
}

class Parser {
    enum Error: Swift.Error {
        case unexpectedEndOfInput(Int)
        case invalidToken(Token, Int)
        case divisonByZero()
    }
    let tokens: [Token]
    var position = 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 {
            let index = Int(position)
            throw Parser.Error.unexpectedEndOfInput(index)
        }
    
        switch token {
        case .number(let value):
            return value
        case .multiply:
            fallthrough
        case .divide:
            fallthrough
        case .minus:
            fallthrough
        case .plus:
            let index = Int(position)
            throw Parser.Error.invalidToken(token, index)
        }
    }

    func getTermValue() throws -> Int {
        var result = try getNumber()
        var termEnded = false
        while  !termEnded {
            if let token = getNextToken() {
                switch token {
                case .number:
                    throw Parser.Error.invalidToken(token, position)
                case .multiply:
                    guard position < tokens.count else {
                        throw Parser.Error.unexpectedEndOfInput(position)
                    }
                    let rightOperand = try getNumber()
                    result *= rightOperand
                case .divide:
                    guard position < tokens.count else {
                        throw Parser.Error.unexpectedEndOfInput(position)
                    }
                    let rightOperand = try getNumber()
                    guard rightOperand != 0 else {
                        throw Parser.Error.divisonByZero()
                    }
                    result /= rightOperand
                case .plus:
                    fallthrough
                case .minus:
                    position -= 1
                    termEnded = true
                    break
                }
            } else {
                termEnded = true
            }
        }
    
        return result
    }

    func parse() throws -> Int {
        assert(!tokens.isEmpty)
        var result = try getTermValue()
        while let token = getNextToken() {
            switch token {
            case .plus:
                guard position < tokens.count else {
                    throw Parser.Error.unexpectedEndOfInput(position)
                }
                let rightValue = try getTermValue()
                result += rightValue
            case .minus:
                guard position < tokens.count else {
                    throw Parser.Error.unexpectedEndOfInput(position)
                }
                let rightValue = try getTermValue()
                result -= rightValue
            case .number:
                throw Parser.Error.invalidToken(token, position)
            case .multiply:
                fallthrough
            case .divide:
                throw Parser.Error.unexpectedEndOfInput(position)
            }
        }
    
        return result
    }
}

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 Parser.Error.unexpectedEndOfInput(let index) {
        print("Unexpected end of input during parsing at index \(index)")
    } catch Parser.Error.invalidToken(let token) {
        print("Invalid token during parsing at index \(token.1): \(token.0)")
    } catch Lexer.Error.invalidCharacter(let character) {
        print("Input contained an invalid character at index \(character.1): \(character.0)")
    } catch {
        print("An error occurred: \(error)")
    }
}

evaluate("10 + 5 + 6 + 1")
evaluate("1 + 2 + abcdefg")
evaluate("1 + + 2")
evaluate("1 +2 +")
evaluate("10 + 2 + 3 + 7 - 1")
evaluate("1")
evaluate("2 - 1 * 6 + 3 * 2 * 3 / 2 + 1")
evaluate("2*2+3*2")
evaluate ("2/2 + 3 - 1 / 0")