溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
這篇文章給大家分享的是有關(guān)JavaScript數(shù)據(jù)結(jié)構(gòu)中棧應(yīng)用之表達(dá)式求值的示例分析的內(nèi)容。小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過來看看吧。
具體如下：
下面來談一個(gè)比較經(jīng)典的表達(dá)式求值問題，這個(gè)問題主要是設(shè)計(jì)到操作符的優(yōu)先級(jí)。我們通?？吹降谋磉_(dá)式都是中綴表達(dá)式，存在很多優(yōu)先級(jí)差別，而后綴表達(dá)式則沒有這些優(yōu)先級(jí)問題。下面先看看兩種表達(dá)式的區(qū)別。
中綴表達(dá)式：a*b+c*d-e/f
后綴表達(dá)式：ab*cd*+ef/-
從中綴表達(dá)式轉(zhuǎn)換到后綴表示式是很難實(shí)現(xiàn)的，我們這里可以通過棧的思想來實(shí)現(xiàn)。下面進(jìn)行詳細(xì)的介紹是什么樣的思想：
在對一個(gè)中綴表示式進(jìn)行轉(zhuǎn)換的時(shí)候，遇到非操作符的字符則直接保存到后綴表示式的存儲(chǔ)空間中。
遇到（，則壓入棧，只有遇到對應(yīng)的）才能被彈出。
遇到），就將（之前的操作符全部彈出，并保存到存儲(chǔ)空間。
遇到*和/這樣優(yōu)先級(jí)高的，就判斷棧中的操作符優(yōu)先級(jí)是否低于當(dāng)前操作符。
如果棧中的遇到的低，則將遇到的繼續(xù)入棧；如果棧中的高，則將棧中的出棧，遇到的入棧。
最后，當(dāng)字符串遍歷完成，依次彈出操作符，保存到存儲(chǔ)空間。
為了方便理解，將上面的例子再次講解。a*b+c*d-e/f
首先是ab被保存到了存儲(chǔ)空間，然后*入?！，F(xiàn)在棧中只有*。
遇到+之后，由于*比+優(yōu)先級(jí)高，所以*出棧，+入棧，這樣存儲(chǔ)空間變?yōu)閍b*，棧中變?yōu)?。
再時(shí)候遇到c，存儲(chǔ)空間變?yōu)閍b*c，棧中還是+。
接下來遇到*和d，由于+比*低，所以*繼續(xù)入棧，棧中表為了+*，存儲(chǔ)空間為ab*cd。
之后遇到-，由于*比-高，所以+*出棧，-入棧，存儲(chǔ)空間變?yōu)閍b*cd*+
……后面不用解釋了，悟性再低也應(yīng)該會(huì)了。
下面我們用JavaScript代碼來實(shí)現(xiàn)下吧。
<!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 ')'://如果是）則將棧中左括號(hào)之前的對象彈出
{
if(myArray.length==0){
return false;
}
temp=myArray.pop();//非空，彈出對象
while(temp!='('){//只要不是左括號(hào)，則全部彈出
b+=temp;//并輸出到后綴表達(dá)式中
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=='-'){//如果遇到高的，則遇到的繼續(xù)入棧
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;//保存到存儲(chǔ)空間
}
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>當(dāng)然，以上程序還存在一點(diǎn)bug，但是思想應(yīng)該就是這樣子的。
下面，我們將講解如何通過后綴表達(dá)式計(jì)算出表達(dá)式的結(jié)果。
那么，我們將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式后，如何繼續(xù)計(jì)算呢？還是以這個(gè)例子為例。
中綴表達(dá)式：a*b+c*d-e/f
后綴表達(dá)式：ab*cd*+ef/-
基本思路如下：
遍歷后綴表達(dá)式，遇到非操作符的字符則直接進(jìn)棧，遇到操作符則出棧兩個(gè)元素，進(jìn)行對應(yīng)操作，然后將得到的結(jié)果再次入棧。依次直到遍歷完成，此處棧中保存的值就是當(dāng)前表達(dá)式的值。
實(shí)現(xiàn)的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])
{//遇到數(shù)值則直接入棧
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 '+':
{//遇到操作符則出棧兩個(gè)元素進(jìn)行對應(yīng)操作
temp=myArray.pop()+myArray.pop();
myArray.push(temp);//再將結(jié)果入棧
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);//再將結(jié)果入棧
temp=null;
break;
}
case '/':
{
s=myArray.pop();
temp=myArray.pop()/s;
myArray.push(temp);
s=null;temp=null;
break;
}
}
}
return myArray.pop();//算出結(jié)果
}
var a="12*34*+36/-";//1*2+3*4-3/6
var b=getValue(a);//13.5
alert(b);
</script>
</body>
</html>感謝各位的閱讀！關(guān)于“JavaScript數(shù)據(jù)結(jié)構(gòu)中棧應(yīng)用之表達(dá)式求值的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號(hào)
手機(jī)網(wǎng)站二維碼