import Foundation

struct Token {
    let value : Float?
    let oper : String?
    
    init(value: Float?,oper: String? = nil) {
        self.value = value
        self.oper = oper
    }
    
    func isNumber() -> Bool { return value != nil }
    func numericValue() -> Float { return value! }
    func isX() -> Bool { return value == nil && oper == nil }
    func getOperator() -> String { return oper!}
}

class Tokenizer {
    let str : String
    var substr : String
    
    init(str:String) {
        self.str = str
        substr = str
    }
    
    func getNextToken() -> Token? {
        while !substr.isEmpty {
            let ch = String(substr.first!)
            substr = String(substr.dropFirst())
            if ch == " " {
                continue
            }
            if ch >= "0" && ch <= "9" || ch == "." {
                var sawDot = false
                var numStr = ch
                if ch == "." {
                    sawDot = true
                }
                while !substr.isEmpty {
                    let nextCh = String(substr.first!)
                    if sawDot && nextCh >= "0" && nextCh <= "9" {
                        numStr += nextCh
                        substr = String(substr.dropFirst())
                    } else if !sawDot && nextCh == "." {
                        sawDot = true
                        numStr += nextCh
                        substr = String(substr.dropFirst())
                    } else if nextCh >= "0" && nextCh <= "9" {
                        numStr += nextCh
                        substr = String(substr.dropFirst())
                    } else {
                        break
                    }
                }
                return Token(value: Float(numStr))
            } else if ch == "x" {
                return Token(value:nil)
            } else if ch == "-" || ch == "+" || ch == "*" || ch == "^" {
                return Token(value:nil,oper:ch)
            }
        }
        return nil
    }
    
    func getAllTokens() -> [Token] {
        var ts : [Token] = []
        while true {
            if let t = getNextToken() {
                ts.append(t)
            } else {
                break
            }
        }
        return ts
    }
}

class Node {
    func evalAt(x:Float) -> Float {
        return 0.0
    }
}

class OperNode : Node {
    let oper : String
    let left : Node
    let right : Node
    
    init(oper: String,left: Node, right: Node) {
        self.oper = oper
        self.left = left
        self.right = right
    }
    
    override func evalAt(x: Float) -> Float {
        switch oper {
        case "+":
            return left.evalAt(x: x) + right.evalAt(x: x)
        case "-":
            return left.evalAt(x: x) - right.evalAt(x: x)
        case "*":
            return left.evalAt(x: x) * right.evalAt(x: x)
        case "^":
            return pow(left.evalAt(x: x),right.evalAt(x: x))
        default:
            return 0.0
        }
    }
}

class UnaryMinusNode : Node {
    let arg : Node
    init(arg: Node) {
        self.arg = arg
    }
    
    override func evalAt(x: Float) -> Float {
        return -1.0*arg.evalAt(x: x)
    }
}
    
class NumNode : Node {
    let val : Float
    
    init(val: Float) {
        self.val = val
    }
    
    override func evalAt(x: Float) -> Float {
        return val
    }
}

class VarNode : Node {
    override func evalAt(x: Float) -> Float {
        return x
    }
}

class Parser {
    let tokens : [Token]
    var n : Int = 0
    
    init(str: String) {
        let t : Tokenizer = Tokenizer(str:str)
        tokens = t.getAllTokens()
    }
    
    func parse() -> Node? {
        return sum()
    }
    
    func sum() -> Node? {
        if n == tokens.count {
            return nil
        }
        let start = n
        if let left = product() {
            var result = left
            while n < tokens.count {
                if let o = tokens[n].oper {
                    n += 1
                    if o == "+" {
                        if let right = product() {
                            result = OperNode(oper: "+", left: result, right: right)
                        } else {
                            return nil
                        }
                    } else if o == "-" {
                        if let right = product() {
                            result = OperNode(oper: "-", left: result, right: right)
                        } else {
                            return nil
                        }
                    } else {
                        n -= 1
                        return nil
                    }
                } else {
                    return nil
                }
            }
            return result
        }
        n = start
        return nil
    }
    
    func product() -> Node? {
        if n == tokens.count {
            return nil
        }
        let start = n
        if let left = term() {
            if n < tokens.count {
                if let o = tokens[n].oper {
                    if o == "*" {
                        n += 1
                        if let right = term() {
                            return OperNode(oper: "*", left: left, right: right)
                        }
                    }
                }
            }
            return left
        }
        n = start
        return nil
    }
    
    func term() -> Node? {
        if n == tokens.count {
            return nil
        }
        if let t = pow() {
            return t
        }
        if let nm = number() {
            return nm
        }
        if let v = variable() {
            return v
        }
        if let o = tokens[n].oper {
            if o == "-" {
                n += 1
                if let right = term() {
                    return UnaryMinusNode(arg:right)
                } else {
                    n -= 1
                }
                return nil
            }
        }
        return nil
    }
    
    func pow() -> Node? {
        if n == tokens.count {
            return nil
        }
        let start = n
        let left = variable()
        if let l = left {
            if n < tokens.count {
                if let o = tokens[n].oper {
                    if o == "^" {
                        n += 1
                        let right = number()
                        if let r = right {
                            return OperNode(oper: "^", left: l, right: r)
                        }
                    }
                }
            }
        }
        n = start
        return nil
    }
    
    func number() -> Node? {
        if n == tokens.count {
            return nil
        }
        if tokens[n].isNumber() {
            let v = tokens[n].value
            n += 1
            return NumNode(val:v!)
        }
        return nil
    }
    
    func variable() -> Node? {
        if n == tokens.count {
            return nil
        }
        if tokens[n].isX() {
            n += 1
            return VarNode()
        }
        return nil
    }
}