shunting.swift

//: Playground - noun: a place where people can play

import Cocoa

enum Symbol {
    case MathOperator(Operator)
    case MathParenthesis(Parenthesis)

    init?(symbol: Character) {

        if let newOperator = Operator(rawValue: symbol) {
            self = .MathOperator(newOperator)
            return
        }

        if let newParenthesis = Parenthesis(rawValue: symbol) {
            self = .MathParenthesis(newParenthesis)
            return
        }

        return nil
    }
}

enum Parenthesis: Character {
    case Open = "("
    case Close = ")"
}

enum Associativity {
    case Left
    case Right
}

enum Operator: Character {
    case Plus = "+"
    case Minus = "-"
    case Multiplication = "*"
    case Division = "/"
    case Power = "^"

    var precendence: Int {
        switch self {
        case .Plus, .Minus: return 2
        case .Multiplication, .Division: return 3
        case .Power: return 4
        }
    }

    var associativity: Associativity {
        switch self {
        case .Plus, .Minus, .Multiplication, .Division: return .Left
        case .Power: return .Right
        }
    }
}

func > (lhs: Operator, rhs: Operator) -> Bool {
    return lhs.precendence > rhs.precendence
}

func >= (lhs: Operator, rhs: Operator) -> Bool {
    return lhs.precendence >= rhs.precendence
}

enum Token {
    case Variable(Character)
    case MathSymbol(Symbol)
}

// https://en.wikipedia.org/wiki/Shunting-yard_algorithm
func shuntingYard(expression: String, output: [Token] = [], symbolStack: [Symbol] = []) -> [Token] {

    guard let first = expression.characters.first else {
        return output + symbolStack.map { .MathSymbol($0) }
    }

    let subExpression = String(expression.characters.dropFirst())

    guard first != " " else {
        return shuntingYard(subExpression, output: output, symbolStack: symbolStack)
    }

    guard let newSymbol = Symbol(symbol: first) else {
        // we assume it's a variable
        return shuntingYard(subExpression, output: output + [.Variable(first)], symbolStack: symbolStack)
    }

    guard let firstSymbol = symbolStack.first else {
        return shuntingYard(subExpression, output: output, symbolStack: [newSymbol])
    }

    switch (newSymbol, firstSymbol) {

    case (.MathOperator(let newOp), .MathOperator(let oldOp)) where (newOp >= oldOp && newOp.associativity == .Right):
        return shuntingYard(subExpression, output: output, symbolStack: [newSymbol] + symbolStack)

    case (.MathOperator(let newOp), .MathOperator(let oldOp)) where newOp > oldOp:
        return shuntingYard(subExpression, output: output, symbolStack: [newSymbol] + symbolStack)

    case (.MathOperator, .MathOperator):
        return shuntingYard(expression, output: output + [.MathSymbol(firstSymbol)], symbolStack: Array(symbolStack.dropFirst()))

    case (.MathParenthesis(.Open), _):
        return shuntingYard(subExpression, output: output, symbolStack: [newSymbol] + symbolStack)

    case (.MathParenthesis(.Close), .MathParenthesis(.Open)):
        return shuntingYard(subExpression, output: output, symbolStack: Array(symbolStack.dropFirst()))

    case (_, .MathParenthesis(.Open)):
        return shuntingYard(subExpression, output: output, symbolStack: [newSymbol] + symbolStack)

    case (.MathParenthesis(.Close), .MathOperator):
        return shuntingYard(expression, output: output + [.MathSymbol(firstSymbol)], symbolStack: Array(symbolStack.dropFirst()))

    default:
        fatalError("newSymbol:\(newSymbol)\noldSymbol:\(firstSymbol)")
    }
}


let outcome = shuntingYard("A + B / C")