定義
棧是一種特殊的列表请唱，棧內(nèi)的元素只能通過列表的一端訪問逢渔，這一端稱為棧頂凳兵。棧被稱為一種先入后出的數(shù)據(jù)結(jié)構(gòu)宋列；
由于棧具有先入后出房揭，后入先出的特點(diǎn)，所以在任何不在棧頂?shù)脑囟紵o法訪問氯葬，為了得到棧底的元素挡篓，必須先拿掉上面的元素婉陷。對(duì)棧的兩種主要操作是一個(gè)元素壓入棧和將一個(gè)元素彈出棧帚称；
原理
棧的實(shí)現(xiàn)
1、創(chuàng)建Stack構(gòu)造函數(shù)：
function Stack() {
this.dataList = [];
this.top = 0;
this.length = length;
this.push = push;
this.pop = pop;
this.peek = peek;
this.clear = clear;
}
2秽澳、當(dāng)前Stack的長度
function length() {
return this.top;
}
3闯睹、將元素壓入棧
function push(ele) {
this.top += 1;
this.dataList[this.top - 1] = ele;
}
4、將棧頂元素彈出棧
function pop() {
this.top -= 1;
return this.dataList[this.top];
}
5担神、讀取棧頂元素
function peek() {
return this.dataList[this.top - 1];
}
6楼吃、 清空棧頂
function clear() {
this.top = 0;
}
實(shí)現(xiàn)中綴表達(dá)式變成后綴表達(dá)式
1、規(guī)則
中綴表達(dá)式(8+3)(9-2)/(6+1)妄讯，轉(zhuǎn)換成后綴表達(dá)式83+92-61+/;
轉(zhuǎn)換過程：
- 如果遇到操作數(shù)孩锡，直接輸出；
- 如果遇到操作符亥贸，將其當(dāng)壓入到棧躬窜，包括左括號(hào)；
- 如果遇到右括號(hào)炕置，則將棧頂元素彈出并輸出荣挨，一直遇到到左括號(hào)為止；彈出左括號(hào)朴摊；
- 如果遇到其他操作符默垄，從棧中彈出元素直到遇到更低優(yōu)先級(jí)元素為止，彈出后甚纲，將操作符壓入到棧口锭；
- 當(dāng)讀到末尾時(shí)，將棧里的元素依次彈出介杆；
2讹弯、實(shí)現(xiàn)
首先，遇到括號(hào)直接壓入棧这溅；
讀到數(shù)字8组民，直接輸出；
讀到操作符" + ",直接壓入棧悲靴；
-
讀到數(shù)字3臭胜，直接輸出莫其；
stack棧： ( +
輸出： 8 3
-
讀到“)”,彈出并輸出“+”，彈出 “(”耸三；
stack棧：
輸出：8 3 +
讀到操作符“*”乱陡，由于棧是空的，直接壓入棧仪壮；
讀到“(”,直接壓入棧憨颠；
讀到數(shù)字9，直接輸出积锅；
讀到“-”爽彤，由于棧頂是“(”，所以直接壓入棧缚陷；
-
讀到數(shù)字2适篙，直接輸出；
stack棧：* ( -
輸出：8 3 + 9 2
-
讀到“)”,彈出并輸入“-”箫爷，彈出“(”嚷节；
stack棧：*
輸出：8 3 + 9 2 -
-
讀到“/”，由于棧頂元素“*”與讀到的“/”優(yōu)先級(jí)是一樣的虎锚，所以也要彈出并輸出硫痰，然后將讀到的“/”壓入棧中；
stack棧：/
輸出：8 3 + 9 2 - *
讀到“(”,直接壓入棧窜护；
讀到數(shù)字6效斑，直接輸出；
讀到操作符“+”柄慰，由于棧頂是“(”鳍悠，所以直接壓入棧；
-
讀到數(shù)字1坐搔，直接輸出藏研；
stack棧： / ( +
輸出： 8 3 + 9 2 - 6 1
-
讀到“)”,彈出并輸出“+”唆涝，彈出“(”
stack棧： /
輸出： 8 3 + 9 2 - 6 1 +
-
最后叶摄，由于已經(jīng)讀完這個(gè)算術(shù)表達(dá)式皇拣，所以將棧中的元素依次彈出并輸出
stack棧：
輸出 8 3 + 9 2 - 6 1 + /
代碼
function init(str) {
var operatorStack = new Stack();
var pushArr = [];
for (var i = 0; i < str.length; i++) {
if (isOperator(str[i])) {
var topEle = operatorStack.peek();
if (!topEle) {
operatorStack.push(str[i]);
} else {
switch (str[i]) {
case '(':
operatorStack.push(str[i]);
break;
case ')':
while (topEle !== '(') {
var operator = operatorStack.pop();
pushArr.push(operator);
topEle = operatorStack.peek();
}
operatorStack.pop();
break;
case '+':
case '-':
var flag = true;
while (flag) {
if (topEle === '(') {
operatorStack.push(str[i]);
flag = false;
} else {
var operator = operatorStack.pop();
pushArr.push(operator);
topEle = operatorStack.peek();
}
}
break;
case '*':
case '/':
if (topEle === '*' || topEle === '/') {
var operator = operatorStack.pop();
pushArr.push(operator);
}
operatorStack.push(str[i]);
break;
}
}
} else {
pushArr.push(str[i]);
}
}
if (operatorStack.length() > 0) {
while (operatorStack.length() > 0) {
var operator = operatorStack.pop();
pushArr.push(operator);
}
}
return pushArr.join('');
}
function isOperator(str) {
return ['+', '-', '*', '/', '(', ')'].indexOf(str) > -1;
}
