Gold challenge

#1

Solution for gold challenge, but it’s not good. It works perfectly for expression like “3 * 2 + 5 / 2 - 4 + 5”, but for expression like “9 / 3 / 3” we’ll got incorrect result or “9”. And I’m really get stack how to make it work ((.

import Cocoa

enum Token {
  case Number(Double)
  case Asterisk
  case Slash
  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() -> Double {
    var value = 0.0
    
    while let nextCharacter = peek() {
      switch nextCharacter {
      case "0" ... "9":
        // Another digit - add it into value
        let digitValue = Double(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(.Asterisk)
        advance()
      case "/":
        tokens.append(.Slash)
        advance()
      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 -> Double {
    guard let token = getNextToken() else {
      throw Error.UnexpextedEndOfInput
    }
// MARK: - Gold challenge solution:
    switch token {
    case .Number(var value):
      if let nextToken = getNextToken() {
        switch nextToken {
        case .Plus, .Minus:
          position--
          return value
        case .Asterisk:
          value *= try getNumber()
        case .Slash:
          
          value /= try getNumber()
          
        default:
          throw Error.InvalidToken(nextToken, --position)
        }
      }
      return value
    case .Plus, .Minus, .Slash, .Asterisk:
      throw Error.InvalidToken(token, --position)
    }
  }
  
  func parse() throws -> Double {
    // 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)
      default:
        break
      }
    }
    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, .Asterisk, .Slash:
      print("Invalid token during parsing at index \(index): \(token)")
    }
  } catch {
    print("An error occurred: \(error)")
  }
}
// Evaluation result is 40.0
evaluate("10 * 4 + 9 / 3 - 3")
// Evaluating result is 49 ((
evaluate("10 * 4 + 9 / 3 / 3")

P. S. I find where is the bag, but can’t patch it.

#2

Your code treats “9 / 3 / 3” as if it were “9 / (3 / 3)”.

It tries to execute the division from right to left. This works fine for multiplication but causes issues for division.
To fix this create a new method to call following a division token. Instead of getNumber which returns an Int, getNumberFollowingDivisor returns [Double] which can be divided in the correct sequence.


import Cocoa

enum Token {
    case Number(Double)
    case Plus
    case Minus
    case Multiply
    case Divide
}

class Lexer {
    enum Error: ErrorType {
        case InvalidCharacter(Character)
    }
    
    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() -> Double {
        var value = 0.0
        
        while let nextCharacter = peek() {
            switch nextCharacter {
            case "0" ... "9":
                let digitValue = Double(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:
                throw Error.InvalidCharacter(nextCharacter)
            }
        }
        return tokens
    }
}

class Parser {
    enum Error: ErrorType {
        case UnexpectedEndOfInput
        case InvalidToken(Token)
    }
    
    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 -> Double {
        guard let token = getNextToken() else {
            throw Error.UnexpectedEndOfInput
        }
        
        switch token {
        case .Number(var value):
            if let nextToken = getNextToken() {
                switch nextToken {
                case .Plus, .Minus:
                    position--
                    return value
                case .Multiply:
                    value *= try getNumber()
                case .Divide:
                    let divisorResult = try getNumberFollowingDivisor()
                    for i in divisorResult {
                        value /= i
                    }
                    return value
                case .Number(_):
                    throw Error.InvalidToken(nextToken)
                }
            }
            return value
        case .Plus, .Minus, .Multiply, .Divide:
            throw Error.InvalidToken(token)
        }
    }
    
    func getNumberFollowingDivisor() throws -> [Double] {
        var numbers = [Double]()
        
        guard let token = getNextToken() else {
            throw Error.UnexpectedEndOfInput
        }
        
        switch token {
        case .Number(let value):
            numbers.append(value)
            if let nextToken = getNextToken() {
                switch nextToken {
                case .Plus, .Minus, .Multiply, .Number(_):
                    position--
                    return numbers
                case .Divide:
                    let returnedArray = try getNumberFollowingDivisor()
                    numbers += returnedArray
                    return numbers
                }
            }
        case .Plus, .Minus, .Divide, .Multiply: return numbers
        }
        return numbers
    }
    
    func parse() throws -> Double {
        var value = try getNumber()
        while let token = getNextToken() {
            switch token {
            case .Plus:
                let nextNumber = try getNumber()
                value += nextNumber
            case .Minus:
                let nextNumber = try getNumber()
                value -= nextNumber
            case .Multiply, .Divide: break
            case .Number: throw Error.InvalidToken(token)
            }
        }
        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 charIndex = input.characters.indexOf(character)!
        print("Input contined an invalid character at index \(charIndex) : \(character)")
    } catch Parser.Error.InvalidToken(let token) {
        print("\(token)")
        var newString = ""
        switch token {
        case .Number(let value):
            newString = "\(value)"
        case .Plus:
            newString = "+"
        case .Minus:
            newString = "-"
        default:
            break
        }
        let char = newString[newString.startIndex]
        let tokenIndex = input.characters.indexOf(char)
        print("Invalid token during parsing at index \(tokenIndex!): \(char)")
    } catch Parser.Error.UnexpectedEndOfInput {
        print("Unexpected end of input during parsing")
    } catch {
        print("An error occurred: \(error)")
    }
}

evaluate("10 / 4 + 5 * 3")
/*
Evaluating 10 / 4 + 5 * 3
Lexer output [Token.Number(10.0), Token.Divide, Token.Number(4.0), Token.Plus, Token.Number(5.0), Token.Multiply, Token.Number(3.0)]
Parser output: 17.5
*/
#3

Thank you guys so much for this. I am going to peruse your solutions to this problem. This is one of the two problems I wasn’t able to build without bugs on my own.