当前位置：首页 > 资讯 > 技术文档

JavaScript数据结构中栈的应用之表达式求值问题详解

时间：2020-04-01 10:08 编辑：来源：阅读：
扫一扫，手机访问

摘要：JavaScript数据结构中栈的应用之表达式求值问题详解

本文实例讲述了JavaScript数据结构中栈的应用之表达式求值问题。分享给大家供大家参考，具体如下：下面来谈一个比较经典的表达式求值问题，这个问题主要是设计到操作符的优先级。我们通常看到的表达式都是中缀表达式，存在很多优先级差别，而后缀表达式则没有这些优先级问题。下面先看看两种表达式的区别。中缀表达式：a*b+c*d-e/f 后缀表达式：ab*cd*+ef/- 从中缀表达式转换到后缀表示式是很难实现的，我们这里可以通过栈的思想来实现。下面进行详细的介绍是什么样的思想：在对一个中缀表示式进行转换的时候，遇到非操作符的字符则直接保存到后缀表示式的存储空间中。遇到（，则压入栈，只有遇到对应的）才能被弹出。遇到），就将（之前的操作符全部弹出，并保存到存储空间。遇到*和/这样优先级高的，就判断栈中的操作符优先级是否低于当前操作符。如果栈中的遇到的低，则将遇到的继续入栈；如果栈中的高，则将栈中的出栈，遇到的入栈。最后，当字符串遍历完成，依次弹出操作符，保存到存储空间。为了方便理解，将上面的例子再次讲解。a*b+c*d-e/f 首先是ab被保存到了存储空间，然后*入栈。现在栈中只有*。遇到+之后，由于*比+优先级高，所以*出栈，+入栈，这样存储空间变为ab*，栈中变为+。再时候遇到c，存储空间变为ab*c，栈中还是+。接下来遇到*和d，由于+比*低，所以*继续入栈，栈中表为了+*，存储空间为ab*cd。之后遇到-，由于*比-高，所以+*出栈，-入栈，存储空间变为ab*cd*+ ……后面不用解释了，悟性再低也应该会了。下面我们用JavaScript代码来实现下吧。

<!DOCTYPE html>
<html>
 <head>
  <meta charset="utf-8">
  <title></title>
 </head>
 <body>
<script type="text/javascript">
 function midTOLast(a){
  var a_len=a.length;
  var myArray=new Array();
  b='';
  for(var i=0;i<a_len;i++){
   switch (a[i]){
    case '(':
    {
     myArray.push(a[i]);
     break;
    }
    case ')'://如果是）则将栈中左括号之前的对象弹出
    {
     if(myArray.length==0){
      return false;
     }
     temp=myArray.pop();//非空，弹出对象
     while(temp!='('){//只要不是左括号，则全部弹出
      b+=temp;//并输出到后缀表达式中
      if(myArray.length==0){//保证栈为空
       break;
      }
      temp=myArray.pop();
     }
     break;
    }
    case '*':
    case '/':
    {
     if(myArray.length==0){//如果栈为空则直接入栈
      myArray.push(a[i]);
     }else{
      temp=myArray[myArray.length-1];
      if(temp=='+'||temp=='-'){//如果遇到高的，则遇到的继续入栈
       myArray.push(a[i]);//遇到的入栈
      }
     }
     break;
    }
    case '+':
    case '-':
    {
     if(myArray.length==0){//如果栈为空则直接入栈
      myArray.push(a[i]);
     }else{
      temp=myArray[myArray.length-1];
      if(temp=='/'||temp=='*'){//如果遇到低的，则栈中的出栈，遇到的入栈
       while(myArray.length!=0){
        temp=myArray.pop();//栈中的出栈
        b+=temp;//保存到存储空间
       }
       myArray.push(a[i]);//遇到的入栈
      }
     }
     break;
    }
    default:
    {
     b+=a[i];
     break;
    }
   }
  }
  //最后将栈中剩下的操作符输出
  while(myArray.length!=0){
   temp=myArray.pop();
   b+=temp;
  }
  return true;
 }
 var x="a*b+c*d-e/f";
 midTOLast(x);
 alert(b);//ab*cd*+ef/-
</script>
 </body>
</html>

当然，以上程序还存在一点bug，但是思想应该就是这样子的。下面，我们将讲解如何通过后缀表达式计算出表达式的结果。那么，我们将中缀表达式转化为后缀表达式后，如何继续计算呢？还是以这个例子为例。中缀表达式：a*b+c*d-e/f 后缀表达式：ab*cd*+ef/- [b]基本思路[/b]如下： [b]遍历后缀表达式，遇到非操作符的字符则直接进栈，遇到操作符则出栈两个元素，进行对应操作，然后将得到的结果再次入栈。依次直到遍历完成，此处栈中保存的值就是当前表达式的值。[/b] 实现的JavaScript代码如下：

<!DOCTYPE html>
<html>
 <head>
  <meta charset="utf-8">
  <title></title>
 </head>
 <body>
<script type="text/javascript">
 function getValue(a){
  var a_len=a.length,
   myArray=new Array();
   for(var i=0;i<a_len;i++){
    switch (a[i])
    {//遇到数值则直接入栈
     case '0':
     case '1':
     case '2':
     case '3':
     case '4':
     case '5':
     case '6':
     case '7':
     case '8':
     case '9':
     {
      myArray.push(a[i]);
      break;
     }
     case '+':
     {//遇到操作符则出栈两个元素进行对应操作
      temp=myArray.pop()+myArray.pop();
      myArray.push(temp);//再将结果入栈
      temp=null;
      break;
     }
     case '-':
     {
      s=myArray.pop();
      temp=myArray.pop()-s;
      myArray.push(temp);
      s=null;temp=null;
      break;
     }
     case '*':
     {
      temp=myArray.pop()*myArray.pop();
      myArray.push(temp);//再将结果入栈
      temp=null;
      break;
     }
     case '/':
     {
      s=myArray.pop();
      temp=myArray.pop()/s;
      myArray.push(temp);
      s=null;temp=null;
      break;
     }
    }
   }
   return myArray.pop();//算出结果
 }
 var a="12*34*+36/-";//1*2+3*4-3/6
 var b=getValue(a);//13.5
 alert(b);
</script>
 </body>
</html>

好啦，栈的应用场景还有很多，比如进制的转换，行编辑程序，迷宫求解等。这里就不一一介绍了。更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《[url=http://www.1sucai.cn/Special/297.htm]JavaScript数据结构与算法技巧总结[/url]》、《[url=http://www.1sucai.cn/Special/119.htm]JavaScript数学运算用法总结[/url]》、《[url=http://www.1sucai.cn/Special/148.htm]JavaScript排序算法总结[/url]》、《[url=http://www.1sucai.cn/Special/281.htm]JavaScript遍历算法与技巧总结[/url]》、《[url=http://www.1sucai.cn/Special/472.htm]JavaScript查找算法技巧总结[/url]》及《[url=http://www.1sucai.cn/Special/439.htm]JavaScript错误与调试技巧总结[/url]》希望本文所述对大家JavaScript程序设计有所帮助。

全部评论(0)

上一篇：捕获浏览器关闭、刷新事件不同情况下的处理方法
下一篇：js函数的延迟加载实现代码

资讯排行榜
更多>>