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/-
基本思路如下：
遍历后缀表达式，遇到非操作符的字符则直接进栈，遇到操作符则出栈两个元素，进行对应操作，然后将得到的结果再次入栈。依次直到遍历完成，此处栈中保存的值就是当前表达式的值。
实现的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数据结构中栈应用之表达式求值的示例分析”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
