# 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]
}

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
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)
case "/":
tokens.append(.Slash)
case "+":
tokens.append(.Plus)
case "-":
tokens.append(.Minus)
case " ":
// Just advance to ignore spaces
default:
// Someone unexpected - need to send back an error
throw Error.InvalidCharacter(nextCharacter, position)
}
}
}
}

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
}
}

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]
}

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
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)
case "-":
tokens.append(.Minus)
case "*":
tokens.append(.Multiply)
case"/":
tokens.append(.Divide)
case " ":
default:
throw Error.InvalidCharacter(nextCharacter)
}
}
}
}

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
}

}

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.