#ALL_LEXEMS = [:open, :close, :operator, :number, :function, :var]

IDENTIFIER = /[a-zA-Z]\w*/

$registered_functions = {sin: 1, cos: 1, log: 1, exp: 1}
$registered_operators = {:+ => 1, :- => 1, :* => 2, :/ => 2, :^ => 3}
$unary = {:- => true, :+ => true}
$commutative = {:+ => true, :* => true}

def numeric?(object)
  true if Float(object) rescue false
end

class Token
  attr_accessor :typ
  attr_accessor :data

  def detect_type s
    @data = s
    return :open if s=="("
    return :close if s==")"
    return :number if numeric?(s)
    return :function if $registered_functions[s.to_sym]
    return :operator if $registered_operators[s.to_sym]
    return :var if IDENTIFIER =~ s
    throw "unrecognised token: #{s}"
  end

  def initialize s
    @typ = detect_type(s)
  end

  def to_s
    "[#{@typ}: #{@data}]"
  end

end

def lexer string
  string.scan(/(?:[0-9]*\.?[0-9]+(?:[eE][-+]?[0-9]+)?)|[a-zA-Z]\w*|\S/).map{|x| Token.new(x)}
end

class Operation
  attr_accessor :args, :parent, :data

  def evaluate vars={}
    throw :abstract
  end
  def simplify
#    p "simplify: #{self}"
    @args.map!(&:simplify)
    self
  end
  def initialize parent,data
    @data = data
    @args = []
    move_to(parent)
  end
  def move_to parent
    @parent.args.delete(self) if @parent
    @parent = parent
    @parent.args << self if @parent
  end
  def to_s
    @data.to_s
  end
  def priority
    10000
  end
  def differentiate(var)
    throw :abstract
  end
  def depends(var)
    @args.any?{|a| a.depends(var)}
  end
end

#syntax sugar
def make_op(*pseudo)
#  p pseudo
  case pseudo.length
    when 1
      if pseudo.first.is_a?(Symbol)
        result = OpVariable.new(nil, pseudo.first)
      elsif pseudo.first.is_a?(Operation)
        result = pseudo.first
      else
        result = OpConstant.new(nil, pseudo.first)
      end
    when 2..3
      if $registered_functions[pseudo[0]]
        result = OpFunction.new(nil, pseudo[0])
        result.args = [make_op(pseudo[1])]
        result
      else
        result = OpBinary.new(nil, pseudo[1])
        nums = pseudo.length > 2 ? [0,2] : [0]
        result.args = nums.map{|x| make_op(pseudo[x])}
        result
      end
  end
end


class OpConstant < Operation
  def evaluate vars={}
    @data
  end
  def differentiate(var)
    make_op(0)
  end
  def to_s
    @data.to_f.to_s
  end
end

class OpDummy < Operation
  def evaluate vars={}
    @args[0].evaluate(vars)
  end
  def differentiate(var)
    @args[0].differentiate(var)
  end
  def simplify
    super
    @args[0]
  end
  def to_s
    "(#{@args[0]})"
  end
  def priority
    0
  end
end

class OpVariable < Operation
  def evaluate vars={}
    vars[@data]
  end
  def differentiate(var)
    make_op(@data == var ? 1 : 0)
  end
  def depends(var)
    @data == var
  end
end

TRIVIALS =
    {
        [:x, :*, 1] => :x,
        [:x, :+, 0] => :x,
        [:x, :/, 1] => :x,
        [:x, :-, 0] => :x,
        [:x, :^, 1] => :x,

        [:x, :^, 0] => 0,
        [:x, :*, 0] => 0,
        [:x, :/, 0] => Float::INFINITY,
        [0, :^, :x] => 0,
        [0, :/, :x] => 0,

        [:x, :*, Float::INFINITY] => Float::INFINITY,
        [:x, :+, Float::INFINITY] => Float::INFINITY,
        [:x, :/, Float::INFINITY] => 0,
        [:x, :-, Float::INFINITY] => Float::INFINITY,
        [:x, :^, Float::INFINITY] => Float::INFINITY,
        [Float::INFINITY, :/, :x] => Float::INFINITY,
        [Float::INFINITY, :-, :x] => Float::INFINITY,
        [Float::INFINITY, :^, :x] => Float::INFINITY,
    }

class OpBinary < Operation
  def evaluate vars={}
    @args[0].evaluate(vars).send(@data == :^ ? :** : @data, @args[1].evaluate(vars))rescue @args[0].evaluate(vars).to_f.send(@data == :^ ? :** : @data, @args[1].evaluate(vars).to_f)
  end

  def to_s
    "(#{@args[0]} #{@data} #{@args[1]})"
  end
  def priority
    $registered_operators[@data]
  end
  def simplify
    super
    #evaluate constant expressions
    return make_op(evaluate) if @args.all?{|x| x.is_a? OpConstant}

    #simplify (a op a) cases
    if @args[0].to_s == @args[1].to_s
      case @data
        when :-
          return make_op(0)
        when :+
          return make_op(2, :*, @args[0])
        when :*
          return make_op(@args[0], :^, 2)
        when :/
          return make_op(1)
        when :^
          return self
      end
    end

    #simplify trivial expressions
    result = nil
    TRIVIALS.each do |x, val|
      first = x[0]
      operator = x[1]
      second = x[2]
      next unless operator == @data
      if $commutative[@data] && @args[0].is_a?(OpConstant)
        @args[1],@args[0] = @args[0],@args[1]
      end
      if first == :x
        it = @args[0]
      else
        next unless @args[0].is_a?(OpConstant) && @args[0].data == first
      end
      if second == :x
        it = @args[1]
      else
        next unless @args[1].is_a?(OpConstant) && @args[1].data == second
      end
      result = (val == :x) ? it : make_op(val)
      break
    end
    return result if result

    #order for nice reading
    if($commutative[@data] && @args[1].is_a?(OpConstant))
      if (@args[1].evaluate < 0) || @data == :*
        @args[1],@args[0] = @args[0],@args[1]
      end
    end
    self
  end


  def differentiate(var)
    u = @args[0].clone
    v = @args[1].clone
    du = @args[0].differentiate(var)
    dv = @args[1].differentiate(var)
    case @data
      when :+, :-
        make_op(du, @data, dv)
      when :*
        make_op( make_op(u, :*, dv), :+, make_op(v, :*, du) )
      when :/
        make_op( make_op( make_op(du, :*, v), :-, make_op(dv, :*, u) ), :/,make_op(v, :*, v))
      when :^
        if not u.depends(var)
          #u^x
          lnu = make_op(:log, u)
          make_op(dv, :*, make_op(clone, :*, lnu))
        elsif not v.depends(var)
          #x^v
          make_op(du, :*, make_op(v, :*, make_op(u, :^, make_op(v, :-, 1))))
        else
          #general case
          lnu = make_op(:log, u)
          make_op( make_op(u, :^, v), :*, make_op(make_op(dv, :*, lnu), :+, make_op(make_op(v, :*, du), :/, u)))
        end
      else
        clone
    end
  end

end

class OpFunction < Operation
  def evaluate vars={}
    Math.send(@data, @args[0].evaluate(vars))
  end
  def simplify
    super
    return make_op(evaluate) if @args[0].is_a?(OpConstant)
    self
  end
  def to_s
    "#{@data.to_s}#{@args[0]}"
  end
  def differentiate(var)
    y = @args[0]
    dy = @args[0].differentiate(var)
    df = case @data
          when :sin
            make_op(:cos,y)
          when :cos
            make_op(0, :-,make_op(:sin,y))
          when :exp
            clone
           when :log
             make_op(1, :/, y)
          else
            clone
         end
    make_op(dy, :*, df)
  end
end



def parse lexems
  expect_bin = false
  cur_op = OpDummy.new(nil, nil)
  nested = []
  lexems.each do |lexem|
    #p "cur=#{cur_op} parent=#{cur_op ? cur_op.parent : nil}"
    #p "lexem=#{lexem.data} mode=#{expect_bin ? "bin" : "un"}"
      # cur_op = cur_op.parent
    if expect_bin
      expect_bin = false
      case lexem.typ
        when :close
          #cur_op = cur_op.parent
          cur_op = nested.pop
          expect_bin = true
        when :operator
          sym = lexem.data.to_sym
          prio = $registered_operators[sym]
          while cur_op.priority >= prio
            cur_op = cur_op.parent
          end
          it = cur_op.args.last
          op = OpBinary.new(cur_op, sym)
          it.move_to(op)
          cur_op = op
        else
          throw "unexpected token: #{lexem}"
      end
    else
      case lexem.typ
        when :open
          nested.push(cur_op)
          cur_op = OpDummy.new(cur_op, nil)
        when :operator
          throw "unexpected token: #{lexem}" unless $unary[lexem.data.to_sym]
          cur_op = OpBinary.new(cur_op, lexem.data.to_sym)
          OpConstant.new(cur_op, 0)
        when :number
          expect_bin = true
          OpConstant.new(cur_op, lexem.data.to_r)
        when :function
          cur_op = OpFunction.new(cur_op, lexem.data.to_sym)
        when :var
          expect_bin = true
          OpVariable.new(cur_op, lexem.data.to_sym)
        else
          throw "unexpected token: #{lexem}"
      end
    end
  end
#  p "cur=#{cur_op} parent=#{cur_op ? cur_op.parent : nil}"
  while cur_op.parent
    cur_op = cur_op.parent
  end
  cur_op.simplify
end

def test(str, var)
  y = parse(lexer(str))
  dy = y.differentiate(var).simplify
  p("d#{y}/d#{var} = #{dy}")
end
test("-x6/1e-6+6*x6-1/x5", :x6)
test("-x6/1e-6+6*x6-1/x5", :x5)
test("-x/1+x/(1/6)", :x)
test("-13.5*(x*(-13))", :x)

test("-1*x+2", :x)
test("(1+1)", :x)
test("-(1/x)+2/x", :x)
test("-1/x+2/0", :x)

test("sin(x)", :x)
test("-(2*x)-3", :x)
test("sin(2*x)/x", :x)

test("x^x", :x)
test("x^x", :y)
test("x^y", :x)
test("y^x", :x)

test("(x-1)*(x+1)", :x)
test("x*x-1", :x)
test("2^exp(x)", :x)
test("(x*x)^0", :x)
test("x*(1/2-1/3-1/6)", :x)

test("0/0+x", :x)