本文实例讲述了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>
新闻热点
疑难解答
图片精选
