Web 技术研究所

我一直坚信着,Web 将会成为未来应用程序的主流

多项式方程的一般化处理

  在提问模块上有人问到了关于解方程的问题,这是个稍复杂的算法问题,而且它确实有应用场景。我记得在许多年前我就写过类似的程序,当时是为了解决从任意表达式直接计算二次函数解的问题,而且还是用VBS写的。这回使用JavaScript把它再实现一次。
  这个算法还是存在应用场景的,比如低次多项式方程一般化之后就可以直接套用公式来得到各个精确解,或者使用迭代法来求近似解。对于一些特殊的操作也可以描述为多元的多项式方程来解,在一些逻辑压缩算法中可能会用到。
  下面的代码没必要认真看,需要时直接拿了用就行,我也没写详细的注释。如果有兴趣的话就用自己的思路实现一个。
  另外要注意几个问题:输入的式子中乘号不能省略,也没有实现乘方运算,而且不要出现符号堆叠的情况,比如a*-1应该写成a*(-1)
<style>
input,textarea {width:100%;font:14px/22px Consolas,微软雅黑;}
textarea {height:200px;}
</style>
<input value="(a+b+c)*(a+b+c)*(a+b+c)=0" id="source" />
<input type="button" value="一般化" id="convert" />
<textarea id="result"></textarea>
<script>
convert.onclick=function(){
  result.value=generalize(source.value);
};

//多项式方程一般化 作者:次碳酸钴(admin@web-tinker.com)
function generalize(s){
  var t,m=[],i;
  //一致化处理
  s=s.replace(/\s/g,"").replace(/^(.*)=(.*)$/,"$1-($2)");
  while((t=s.replace(/\(([^()]*)\)/g,function(e,a){
    return "$"+m.push(a);
  }))!=s&&(s=t));
  //还原式子
  for(i=0,s=f(s);i<s.length;i++)
    if(/^[+-]/.test(s[i][0]))s[i]=s[i].join("");
    else s[i]="+"+s[i].join("");
  return s.join("").replace(/^\+/,"");
  //递归过程
  function f(s,v){
    //初始化
    var i,j,k,t,o,n,s=s.split(/(?=[+-])/g);
    for(i=0;i<s.length;i++)s[i]=s[i].split(/(?=[*/])/g);
    //去分母
    for(i=0;n=s[i];i++)for(j=0;j<n.length;j++)
      if(n[j].charAt(0)=="/"&&(o=n.splice(j--,1)[0]))
        for(k=0;t=s[k];k++)if(k!=i)t.push("*"+o.slice(1));
    //去括号
    for(i=0;n=s[i];i++)for(j=0;o=n[j];j++)
      if((t=o.split("$")).length==2)
        n.splice(j,1),n[0]=n.length?(
          t[0]=t[0]=="-"^n[0].charAt(0)=="-"?"-":"+",
          n[0]=n[0].replace(/[-+*]*/,t[0])
        ):t[0]+"1",s[i]=f(m[t[1]-1],n),j=0/0,
        Array.prototype.splice.apply(s,[i,1].concat(s[i])),i--;
    //乘法分配
    if(v&&v.length)switch(v[0].charAt(0)){
      case "-":for(i=0;n=s[i];i++)
        n[0]=("-"+n[0]).replace(/--/,"+").replace(/-\+/,"-");
      case "+":v[0]=v[0].slice(1);
      default:v[0]="*"+v[0];
      case "*":for(i=0;n=s[i];i++)Array.prototype.push.apply(n,v);
    };
    //合并同类项
    o={};for(i=0;i<s.length;i++){
      t=[],v=1;if(!isNaN((n=s[i][0])*1))v*=n;
      else n.charAt(0)=="-"&&(v=-v),t.push(n.replace(/[+-]/,""));
      for(j=1;j<s[i].length;j++)
        isNaN((n=s[i][j].slice(1))*1)?t.push(n):v*=n;
      (n=t.sort().join("*")) in o?o[n]+=v:o[n]=v;
    };s=[];for(i in o)if(o[i]!=0)if(i){
      if(Math.abs(o[i])!=1)i=o[i]+"*"+i;
      if(o[i]==-1&&i)i="-"+i;
      s.push(i.split(/(?=\*)/));
    }else s.push([o[i]+""]);
    return s.length||s.push(["0"]),s; 
  };
};
</script>
网名:
3.80.32.*
电子邮箱:
仅用于接收通知
提交 悄悄的告诉你,Ctrl+Enter 可以提交哦
神奇海螺
[查看全部主题]
各类Web技术问题讨论区
发起新主题
本模块采用即时聊天邮件通知的模式
让钛合金F5成为历史吧!
次碳酸钴的技术博客,文章原创,转载请保留原文链接 ^_^