Gold Challenge: Ch 20


#1

I try to upload my solution for the gold-challenge but I don’t know how…


#2

Posting code is pretty easy: Copy and paste it between a pair of three back ticks:

```
CODE
```

For example:

struct JimmyGiggle {
   void go () {
       print ("Hoot Hoot!")
   }
}


#3

Thanks ibex10, I will try it later.

Best regards,
Arthur.


#4

Gold Challenge:

import Cocoa

enum Token {
    case number(value: Int, pos: Int)
    case plus(pos: Int)
    case minus(pos: Int)
    case mult(pos: Int)
    case div(pos: Int)

    func returnNumberValue() -> Int{
        switch self {
        case .number(let value, _):
            return value
        default:
            return 0
        }
    }
}

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

    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 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:
                //A nondigit - go back to regular lexing
                return value
            }
        }
        return value
    }

    func lex() throws -> [Token] {
        var tokens = [Token]()
        while let nextCharacter = peek() {
            let tokenPosInInput = input.distance(from: input.startIndex, to: position)
            switch nextCharacter {
            case "0" ... "9":
                let value = getNumber()
                tokens.append(.number(value: value, pos: tokenPosInInput))
            case "+":
                tokens.append(.plus(pos: tokenPosInInput))
                advance()
            case "-":
                tokens.append(.minus(pos: tokenPosInInput))
                advance()
            case "*":
                tokens.append(.mult(pos: tokenPosInInput))
                advance()
            case "/":
                tokens.append(.div(pos: tokenPosInInput))
                advance()
            case " ":
                advance()
            default:
                throw Lexer.Error.invalidCharacter(nextCharacter, tokenPosInInput)
            }
        }
        return tokens
    }
}

class Parser {
    enum Error: Swift.Error {
        case unexpectedEndOfInput
        case invalidToken(String, Int)
        case impossibleError
    }

    var 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 {
            throw Parser.Error.unexpectedEndOfInput
        }

        switch token {
        case .number(let value, _):
            return value
        case .plus(let pos):
            throw Parser.Error.invalidToken("+", pos)
        case .minus(let pos):
            throw Parser.Error.invalidToken("-", pos)
        case .mult(let pos):
            throw Parser.Error.invalidToken("*", pos)
        case .div(let pos):
            throw Parser.Error.invalidToken("/", pos)

        }
    }

    func parse() throws -> Int {

        //Checking for all possible parsing errors
        var value = try getNumber()
        while let token = getNextToken() {
            switch token {
            case .number(let value, let pos):
                throw Parser.Error.invalidToken(String(value), pos)
            default:
                try getNumber()
            }
        }
        position = 0

        //resolving * and /
        while let token = getNextToken() {
            switch token {
            case .mult:
                value = tokens[position-2].returnNumberValue()
                let nextNumber = try getNumber()
                value *= nextNumber
                tokens[position-1] = .number(value: value, pos: 0)
                tokens.remove(at: position-2)
                tokens.remove(at: position-3)
                position = 0
            case .div:
                value = tokens[position-2].returnNumberValue()
                let nextNumber = try getNumber()
                value /= nextNumber
                tokens[position-1] = .number(value: value, pos: 0)
                tokens.remove(at: position-2)
                tokens.remove(at: position-3)
                position = 0
            default:
                break
            }
        }
        position = 0

        //resolving + and -
        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
            default:
                throw Parser.Error.impossibleError
            }
        }
        return value
    }
}

func evaluate(_ input: String) {
    print("Evaluating: \(input)")
    let lexer = Lexer(input: input)
    do {
        let tokens = try lexer.lex()
        let parser = Parser(tokens: tokens)
        let result = try parser.parse()
        print("Parser output: \(result)")
    } catch Lexer.Error.invalidCharacter(let character, let pos){
        var strPointError = String(repeatElement(" ", count: pos + 12))
        strPointError += "^"
        print(strPointError)
        print("Input contained an invalid character at index \(pos): \(character)")
    } catch Parser.Error.unexpectedEndOfInput {
        print("Unexpected end of input during parsing.")
    } catch  Parser.Error.invalidToken(let token, let pos){
        var strPointError = String(repeatElement(" ", count: pos + 12))
        strPointError += "^"
        print(strPointError)
        print("Invalid token during parsing at index \(pos): \(token)")

    } catch {
        print("An error ocurred: \(error)")
    }
    print("------------------------------------------------------")
}

evaluate("12000 + 3 + 5")
evaluate("10 + 5 + ab")
evaluate("10 + 5 5 - 1")
evaluate("45 + 5 -- 1")
evaluate("40-30+20-15+65-95+15")

evaluate("10*3+5*3")
evaluate("10+3*5+3")
evaluate("10+3*5*3")

evaluate("10/2*20+12/3")

Output:

Evaluating: 12000 + 3 + 5
Parser output: 12008
------------------------------------------------------
Evaluating: 10 + 5 + ab
                     ^
Input contained an invalid character at index 9: a
------------------------------------------------------
Evaluating: 10 + 5 5 - 1
                   ^
Invalid token during parsing at index 7: 5
------------------------------------------------------
Evaluating: 45 + 5 -- 1
                    ^
Invalid token during parsing at index 8: -
------------------------------------------------------
Evaluating: 40-30+20-15+65-95+15
Parser output: 0
------------------------------------------------------
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: 10/2*20+12/3
Parser output: 104
------------------------------------------------------

#5

I took a different approach, breaking up the parser into two separate parsing functions, one for multiplication & division, and one for addition & subtraction. I also added a peekNextToken function to look ahead at the next token without “consuming” it (necessary to determine when we’ve hit the end of a string of multiplication & division and need to return the result).

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

func parse() throws -> Int
{
    var value = try parseMultiplyDivide()
    
    while let token = getNextToken()
    {
        switch token
        {
        case .plus:
            let nextNumber = try parseMultiplyDivide()
            value += nextNumber
            
        case .minus:
            let nextNumber = try parseMultiplyDivide()
            value -= nextNumber
        
        case .multiply, .divide, .number:
            throw Parser.Error.invalidToken(token, position)
        }
    }
    return value
}

func parseMultiplyDivide() throws -> Int
{
    // require a number first
    var value = try getNumber()
    
    while let token = peekNextToken()
    {
        switch token
        {
        case .plus, .minus:
            return value
            
        case .multiply:
            getNextToken()
            let nextNumber = try getNumber()
            value *= nextNumber
            
        case .divide:
            getNextToken()
            let nextNumber = try getNumber()
            value /= nextNumber
            
        case .number:
            throw Parser.Error.invalidToken(token, position)
        }
    }
    return value
}

#6

Wow - This is great! I really like the “^” pointing at the character for the Silver challenge!
Thanks!


#7

In your func parseMultiplyDivide where you switch on plus and minus, does ‘return value’ mean that we just return the ‘value’ we get at the beginning of the function?

also for the func peekNextToken it looks to peek at the next token by checking to make sure that we still have tokens remaining and to get the token and its position?

@JonAult


#8

If it’s a single number followed by a ‘+’ or ‘-’, then yes, it just returns the number. Otherwise it performs the multiplication or division with the next number, and keeps on going until it hits a plus or minus, at which point it returns the result of the multiplications & divisions.

Yes, it does the same thing as getNextToken but without incrementing position.