fork download 
  1. #ALL_LEXEMS = [:open, :close, :operator, :number, :function, :var]
  2.  
  3. IDENTIFIER = /[a-zA-Z]\w*/
  4.  
  5. $registered_functions = {sin: 1, cos: 1, log: 1, exp: 1}
  6. $registered_operators = {:+ => 1, :- => 1, :* => 2, :/ => 2, :^ => 3}
  7. $unary = {:- => true, :+ => true}
  8. $commutative = {:+ => true, :* => true}
  9.  
  10. def numeric?(object)
  11.   true if Float(object) rescue false
  12. end
  13.  
  14. class Token
  15.   attr_accessor :typ
  16.   attr_accessor :data
  17.  
  18.   def detect_type s
  19.     @data = s
  20.     return :open if s=="("
  21.     return :close if s==")"
  22.     return :number if numeric?(s)
  23.     return :function if $registered_functions[s.to_sym]
  24.     return :operator if $registered_operators[s.to_sym]
  25.     return :var if IDENTIFIER =~ s
  26.     throw "unrecognised token: #{s}"
  27.   end
  28.  
  29.   def initialize s
  30.     @typ = detect_type(s)
  31.   end
  32.  
  33.   def to_s
  34.     "[#{@typ}: #{@data}]"
  35.   end
  36.  
  37. end
  38.  
  39. def lexer string
  40.   string.scan(/(?:[0-9]*\.?[0-9]+(?:[eE][-+]?[0-9]+)?)|[a-zA-Z]\w*|\S/).map{|x| Token.new(x)}
  41. end
  42.  
  43. class Operation
  44.   attr_accessor :args, :parent, :data
  45.  
  46.   def evaluate vars={}
  47.     throw :abstract
  48.   end
  49.   def simplify
  50. #    p "simplify: #{self}"
  51.     @args.map!(&:simplify)
  52.     self
  53.   end
  54.   def initialize parent,data
  55.     @data = data
  56.     @args = []
  57.     move_to(parent)
  58.   end
  59.   def move_to parent
  60.     @parent.args.delete(self) if @parent
  61.     @parent = parent
  62.     @parent.args << self if @parent
  63.   end
  64.   def to_s
  65.     @data.to_s
  66.   end
  67.   def priority
  68.     10000
  69.   end
  70.   def differentiate(var)
  71.     throw :abstract
  72.   end
  73.   def depends(var)
  74.     @args.any?{|a| a.depends(var)}
  75.   end
  76. end
  77.  
  78. #syntax sugar
  79. def make_op(*pseudo)
  80. #  p pseudo
  81.   case pseudo.length
  82.     when 1
  83.       if pseudo.first.is_a?(Symbol)
  84.         result = OpVariable.new(nil, pseudo.first)
  85.       elsif pseudo.first.is_a?(Operation)
  86.         result = pseudo.first
  87.       else
  88.         result = OpConstant.new(nil, pseudo.first)
  89.       end
  90.     when 2..3
  91.       if $registered_functions[pseudo[0]]
  92.         result = OpFunction.new(nil, pseudo[0])
  93.         result.args = [make_op(pseudo[1])]
  94.         result
  95.       else
  96.         result = OpBinary.new(nil, pseudo[1])
  97.         nums = pseudo.length > 2 ? [0,2] : [0]
  98.         result.args = nums.map{|x| make_op(pseudo[x])}
  99.         result
  100.       end
  101.   end
  102. end
  103.  
  104.  
  105. class OpConstant < Operation
  106.   def evaluate vars={}
  107.     @data
  108.   end
  109.   def differentiate(var)
  110.     make_op(0)
  111.   end
  112.   def to_s
  113.     @data.to_f.to_s
  114.   end
  115. end
  116.  
  117. class OpDummy < Operation
  118.   def evaluate vars={}
  119.     @args[0].evaluate(vars)
  120.   end
  121.   def differentiate(var)
  122.     @args[0].differentiate(var)
  123.   end
  124.   def simplify
  125.     super
  126.     @args[0]
  127.   end
  128.   def to_s
  129.     "(#{@args[0]})"
  130.   end
  131.   def priority
  132.     0
  133.   end
  134. end
  135.  
  136. class OpVariable < Operation
  137.   def evaluate vars={}
  138.     vars[@data]
  139.   end
  140.   def differentiate(var)
  141.     make_op(@data == var ? 1 : 0)
  142.   end
  143.   def depends(var)
  144.     @data == var
  145.   end
  146. end
  147.  
  148. TRIVIALS =
  149.     {
  150.         [:x, :*, 1] => :x,
  151.         [:x, :+, 0] => :x,
  152.         [:x, :/, 1] => :x,
  153.         [:x, :-, 0] => :x,
  154.         [:x, :^, 1] => :x,
  155.  
  156.         [:x, :^, 0] => 0,
  157.         [:x, :*, 0] => 0,
  158.         [:x, :/, 0] => Float::INFINITY,
  159.         [0, :^, :x] => 0,
  160.         [0, :/, :x] => 0,
  161.  
  162.         [:x, :*, Float::INFINITY] => Float::INFINITY,
  163.         [:x, :+, Float::INFINITY] => Float::INFINITY,
  164.         [:x, :/, Float::INFINITY] => 0,
  165.         [:x, :-, Float::INFINITY] => Float::INFINITY,
  166.         [:x, :^, Float::INFINITY] => Float::INFINITY,
  167.         [Float::INFINITY, :/, :x] => Float::INFINITY,
  168.         [Float::INFINITY, :-, :x] => Float::INFINITY,
  169.         [Float::INFINITY, :^, :x] => Float::INFINITY,
  170.     }
  171.  
  172. class OpBinary < Operation
  173.   def evaluate vars={}
  174.     @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)
  175.   end
  176.  
  177.   def to_s
  178.     "(#{@args[0]} #{@data} #{@args[1]})"
  179.   end
  180.   def priority
  181.     $registered_operators[@data]
  182.   end
  183.   def simplify
  184.     super
  185.     #evaluate constant expressions
  186.     return make_op(evaluate) if @args.all?{|x| x.is_a? OpConstant}
  187.  
  188.     #simplify (a op a) cases
  189.     if @args[0].to_s == @args[1].to_s
  190.       case @data
  191.         when :-
  192.           return make_op(0)
  193.         when :+
  194.           return make_op(2, :*, @args[0])
  195.         when :*
  196.           return make_op(@args[0], :^, 2)
  197.         when :/
  198.           return make_op(1)
  199.         when :^
  200.           return self
  201.       end
  202.     end
  203.  
  204.     #simplify trivial expressions
  205.     result = nil
  206.     TRIVIALS.each do |x, val|
  207.       first = x[0]
  208.       operator = x[1]
  209.       second = x[2]
  210.       next unless operator == @data
  211.       if $commutative[@data] && @args[0].is_a?(OpConstant)
  212.         @args[1],@args[0] = @args[0],@args[1]
  213.       end
  214.       if first == :x
  215.         it = @args[0]
  216.       else
  217.         next unless @args[0].is_a?(OpConstant) && @args[0].data == first
  218.       end
  219.       if second == :x
  220.         it = @args[1]
  221.       else
  222.         next unless @args[1].is_a?(OpConstant) && @args[1].data == second
  223.       end
  224.       result = (val == :x) ? it : make_op(val)
  225.       break
  226.     end
  227.     return result if result
  228.  
  229.     #order for nice reading
  230.     if($commutative[@data] && @args[1].is_a?(OpConstant))
  231.       if (@args[1].evaluate < 0) || @data == :*
  232.         @args[1],@args[0] = @args[0],@args[1]
  233.       end
  234.     end
  235.     self
  236.   end
  237.  
  238.  
  239.   def differentiate(var)
  240.     u = @args[0].clone
  241.     v = @args[1].clone
  242.     du = @args[0].differentiate(var)
  243.     dv = @args[1].differentiate(var)
  244.     case @data
  245.       when :+, :-
  246.         make_op(du, @data, dv)
  247.       when :*
  248.         make_op( make_op(u, :*, dv), :+, make_op(v, :*, du) )
  249.       when :/
  250.         make_op( make_op( make_op(du, :*, v), :-, make_op(dv, :*, u) ), :/,make_op(v, :*, v))
  251.       when :^
  252.         if not u.depends(var)
  253.           #u^x
  254.           lnu = make_op(:log, u)
  255.           make_op(dv, :*, make_op(clone, :*, lnu))
  256.         elsif not v.depends(var)
  257.           #x^v
  258.           make_op(du, :*, make_op(v, :*, make_op(u, :^, make_op(v, :-, 1))))
  259.         else
  260.           #general case
  261.           lnu = make_op(:log, u)
  262.           make_op( make_op(u, :^, v), :*, make_op(make_op(dv, :*, lnu), :+, make_op(make_op(v, :*, du), :/, u)))
  263.         end
  264.       else
  265.         clone
  266.     end
  267.   end
  268.  
  269. end
  270.  
  271. class OpFunction < Operation
  272.   def evaluate vars={}
  273.     Math.send(@data, @args[0].evaluate(vars))
  274.   end
  275.   def simplify
  276.     super
  277.     return make_op(evaluate) if @args[0].is_a?(OpConstant)
  278.     self
  279.   end
  280.   def to_s
  281.     "#{@data.to_s}#{@args[0]}"
  282.   end
  283.   def differentiate(var)
  284.     y = @args[0]
  285.     dy = @args[0].differentiate(var)
  286.     df = case @data
  287.           when :sin
  288.             make_op(:cos,y)
  289.           when :cos
  290.             make_op(0, :-,make_op(:sin,y))
  291.           when :exp
  292.             clone
  293.            when :log
  294.              make_op(1, :/, y)
  295.           else
  296.             clone
  297.          end
  298.     make_op(dy, :*, df)
  299.   end
  300. end
  301.  
  302.  
  303.  
  304. def parse lexems
  305.   expect_bin = false
  306.   cur_op = OpDummy.new(nil, nil)
  307.   nested = []
  308.   lexems.each do |lexem|
  309.     #p "cur=#{cur_op} parent=#{cur_op ? cur_op.parent : nil}"
  310.     #p "lexem=#{lexem.data} mode=#{expect_bin ? "bin" : "un"}"
  311.       # cur_op = cur_op.parent
  312.     if expect_bin
  313.       expect_bin = false
  314.       case lexem.typ
  315.         when :close
  316.           #cur_op = cur_op.parent
  317.           cur_op = nested.pop
  318.           expect_bin = true
  319.         when :operator
  320.           sym = lexem.data.to_sym
  321.           prio = $registered_operators[sym]
  322.           while cur_op.priority >= prio
  323.             cur_op = cur_op.parent
  324.           end
  325.           it = cur_op.args.last
  326.           op = OpBinary.new(cur_op, sym)
  327.           it.move_to(op)
  328.           cur_op = op
  329.         else
  330.           throw "unexpected token: #{lexem}"
  331.       end
  332.     else
  333.       case lexem.typ
  334.         when :open
  335.           nested.push(cur_op)
  336.           cur_op = OpDummy.new(cur_op, nil)
  337.         when :operator
  338.           throw "unexpected token: #{lexem}" unless $unary[lexem.data.to_sym]
  339.           cur_op = OpBinary.new(cur_op, lexem.data.to_sym)
  340.           OpConstant.new(cur_op, 0)
  341.         when :number
  342.           expect_bin = true
  343.           OpConstant.new(cur_op, lexem.data.to_r)
  344.         when :function
  345.           cur_op = OpFunction.new(cur_op, lexem.data.to_sym)
  346.         when :var
  347.           expect_bin = true
  348.           OpVariable.new(cur_op, lexem.data.to_sym)
  349.         else
  350.           throw "unexpected token: #{lexem}"
  351.       end
  352.     end
  353.   end
  354. #  p "cur=#{cur_op} parent=#{cur_op ? cur_op.parent : nil}"
  355.   while cur_op.parent
  356.     cur_op = cur_op.parent
  357.   end
  358.   cur_op.simplify
  359. end
  360.  
  361. def test(str, var)
  362.   y = parse(lexer(str))
  363.   dy = y.differentiate(var).simplify
  364.   p("d#{y}/d#{var} = #{dy}")
  365. end
  366. test("-x6/1e-6+6*x6-1/x5", :x6)
  367. test("-x6/1e-6+6*x6-1/x5", :x5)
  368. test("-x/1+x/(1/6)", :x)
  369. test("-13.5*(x*(-13))", :x)
  370.  
  371. test("-1*x+2", :x)
  372. test("(1+1)", :x)
  373. test("-(1/x)+2/x", :x)
  374. test("-1/x+2/0", :x)
  375.  
  376. test("sin(x)", :x)
  377. test("-(2*x)-3", :x)
  378. test("sin(2*x)/x", :x)
  379.  
  380. test("x^x", :x)
  381. test("x^x", :y)
  382. test("x^y", :x)
  383. test("y^x", :x)
  384.  
  385. test("(x-1)*(x+1)", :x)
  386. test("x*x-1", :x)
  387. test("2^exp(x)", :x)
  388. test("(x*x)^0", :x)
  389. test("x*(1/2-1/3-1/6)", :x)
  390.  
  391. test("0/0+x", :x)
  392.  
Success #stdin #stdout 0.06s 9992KB
comments (?)
stdin 
Standard input is empty
stdout 
"d(((0.0 - (x6 / 1.0e-06)) + (6.0 * x6)) - (1.0 / x5))/dx6 = -999994.0"
"d(((0.0 - (x6 / 1.0e-06)) + (6.0 * x6)) - (1.0 / x5))/dx5 = (0.0 - (-1.0 / (x5 ^ 2.0)))"
"d((0.0 - x) + (x / 0.16666666666666666))/dx = 5.0"
"d(0.0 - (13.5 * (-13.0 * x)))/dx = 175.5"
"d((0.0 - x) + 2.0)/dx = -1.0"
"d2.0/dx = 0.0"
"d((0.0 - (1.0 / x)) + (2.0 / x))/dx = ((0.0 - (-1.0 / (x ^ 2.0))) + (-2.0 / (x ^ 2.0)))"
"dInfinity/dx = 0.0"
"dsinx/dx = cosx"
"d((0.0 - (2.0 * x)) - 3.0)/dx = -2.0"
"d(sin(2.0 * x) / x)/dx = ((((2.0 * cos(2.0 * x)) * x) - sin(2.0 * x)) / (x ^ 2.0))"
"d(x ^ x)/dx = ((x ^ x) * (logx + 1.0))"
"d(x ^ x)/dy = 0.0"
"d(x ^ y)/dx = (y * (x ^ (y - 1.0)))"
"d(y ^ x)/dx = ((y ^ x) * logy)"
"d((x - 1.0) * (x + 1.0))/dx = ((x - 1.0) + (x + 1.0))"
"d((x ^ 2.0) - 1.0)/dx = (2.0 * x)"
"d(2.0 ^ expx)/dx = (expx * (0.6931471805599453 * (2.0 ^ expx)))"
"d0.0/dx = 0.0"
"d0.0/dx = 0.0"
"d(x + NaN)/dx = 1.0"
https://ideone.com/60SVXF
language:
Ruby (ruby 2.5.5)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!