Here’s my solution in case anybody wants to see how I did it. I didn’t end up using any recursive behaviors for the gold solution, as the book suggests doing. Instead, I go through the token array and handle all multiplication and division sequences first, before beginning parsing the addition and subtraction. I’m using Xcode 10.1.
import Cocoa
enum Token {
// Every case has the input position as the first associated value
case number(Int, Int)
case plus(Int)
case minus(Int)
case times(Int)
case dividedBy(Int)
func getValues() -> (Int, Int?) {
switch self {
case .number(let index, let value):
return (index, value)
case .plus(let index), .minus(let index), .times(let index), .dividedBy(let index):
return (index, nil)
}
}
}
class Lexer {
enum Error: Swift.Error {
case invalidCharacter(Int, Character)
}
let input: String
var position: String.Index {
didSet {
index = input.distance(from: input.startIndex, to: position)
}
}
var index = 0
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":
// Another digit - add it into value
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() {
switch nextCharacter {
case "0" ... "9":
let value = getNumber()
tokens.append(.number(index, value))
case "+":
tokens.append(.plus(index))
advance()
case "-":
tokens.append(.minus(index))
advance()
case "*":
tokens.append(.times(index))
advance()
case "/":
tokens.append(.dividedBy(index))
advance()
case " ":
// just advance to ignore spaces
advance()
default:
let distanceToPosition = input.distance(from: input.startIndex, to: position)
throw Lexer.Error.invalidCharacter(distanceToPosition, nextCharacter)
}
}
return tokens
}
}
class Parser {
enum Error: Swift.Error {
case unexpectedEndOfInput
case invalidToken(Int, Int)
case repetitiveOperations(Int)
case failedToHandleMultiplicationOrDivision
}
var tokens: [Token]
var position = 0
init(tokens: [Token]) {
self.tokens = tokens
}
func tokenPeek() -> Token? {
guard position < tokens.endIndex else {
return nil
}
return tokens[position]
}
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, .minus, .times, .dividedBy:
throw Parser.Error.repetitiveOperations(token.getValues().0)
}
}
func replaceProductSequence(with product: Int) {
// replace * or / token with the product
tokens[position - 1] = .number(position, product)
// remove previous and following tokens
tokens.remove(at: position)
tokens.remove(at: position - 2)
}
func parse() throws -> Int {
// Check for and handle multiplication or division sequences
var previousToken: Token?
func handleProductSequence() {
previousToken = nil
position = 0
loop: while let token = getNextToken() {
switch token {
case .times:
// product placeholder with default value of 1
var product = 1
// multiply previous token by next token
if let previousValue = previousToken?.getValues().1, let nextValue = tokenPeek()?.getValues().1 {
product = previousValue * nextValue
replaceProductSequence(with: product)
}
// break out of loop once a replacement is complete to allow handling to restart on the mutated array
break loop
case .dividedBy:
// product placeholder with default value of 1
var product = 1
// divide previous token by next token
if let previousValue = previousToken?.getValues().1, let nextValue = tokenPeek()?.getValues().1 {
product = previousValue / nextValue
replaceProductSequence(with: product)
}
// break out of loop once a replacement is complete to allow handling to restart on the mutated array
break loop
default:
break
}
previousToken = token
}
}
// run product sequence handler at least once for every token;
// this ensures that subsequent multiplication or division statements are handled
for _ in 0..<tokens.count {
handleProductSequence()
}
// reset position before beginning parsing
position = 0
// require a number as first token
var value = try getNumber()
while let token = getNextToken() {
switch token {
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 Parser.Error.invalidToken(token.getValues().0, token.getValues().1!)
case .times, .dividedBy:
throw Parser.Error.failedToHandleMultiplicationOrDivision
}
}
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 index, let character) {
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 index, let value) {
print("Invalid token during parsing at index \(index): \(value)")
} catch Parser.Error.repetitiveOperations(let index){
if index == 0 {
print("Invalid token during parsing at index \(index). First token must be a number")
} else {
print("Invalid token during parsing at index \(index). There are repetitive operators")
}
} catch Parser.Error.failedToHandleMultiplicationOrDivision {
print("Failed to handle multiplication and/or division sequences; check operators")
} catch {
print("An error occurred: \(error)")
}
}
evaluate(" 1 + 3 / 2 * 5 * 10")
Output:
Evaluating: 1 + 3 / 2 * 5 * 10
Lexer output: [__lldb_expr_66.Token.number(2, 1), __lldb_expr_66.Token.plus(3), __lldb_expr_66.Token.number(6, 3), __lldb_expr_66.Token.dividedBy(7), __lldb_expr_66.Token.number(10, 2), __lldb_expr_66.Token.times(11), __lldb_expr_66.Token.number(14, 5), __lldb_expr_66.Token.times(15), __lldb_expr_66.Token.number(19, 10)]
Parser output: 51