溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章給大家分享的是有關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數據結構中棧應用之表達式求值的示例分析”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
