定义
栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，这一端称为栈顶。栈被称为一种先入后出的数据结构；
由于栈具有先入后出，后入先出的特点，所以在任何不在栈顶的元素都无法访问，为了得到栈底的元素，必须先拿掉上面的元素。对栈的两种主要操作是一个元素压入栈和将一个元素弹出栈；
原理
栈的实现
1、创建Stack构造函数：
function Stack() {
this.dataList = [];
this.top = 0;
this.length = length;
this.push = push;
this.pop = pop;
this.peek = peek;
this.clear = clear;
}
2、当前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;
}
实现中缀表达式变成后缀表达式
1、规则
中缀表达式(8+3)(9-2)/(6+1)，转换成后缀表达式83+92-61+/;
转换过程：
- 如果遇到操作数，直接输出；
- 如果遇到操作符，将其当压入到栈，包括左括号；
- 如果遇到右括号，则将栈顶元素弹出并输出，一直遇到到左括号为止；弹出左括号；
- 如果遇到其他操作符，从栈中弹出元素直到遇到更低优先级元素为止，弹出后，将操作符压入到栈；
- 当读到末尾时，将栈里的元素依次弹出；
2、实现
首先，遇到括号直接压入栈；
读到数字8，直接输出；
读到操作符" + ",直接压入栈；
-
读到数字3，直接输出；
stack栈： ( +
输出： 8 3
-
读到“)”,弹出并输出“+”，弹出 “(”；
stack栈：
输出：8 3 +
读到操作符“*”，由于栈是空的，直接压入栈；
读到“(”,直接压入栈；
读到数字9，直接输出；
读到“-”，由于栈顶是“(”，所以直接压入栈；
-
读到数字2，直接输出；
stack栈：* ( -
输出：8 3 + 9 2
-
读到“)”,弹出并输入“-”，弹出“(”；
stack栈：*
输出：8 3 + 9 2 -
-
读到“/”，由于栈顶元素“*”与读到的“/”优先级是一样的，所以也要弹出并输出，然后将读到的“/”压入栈中；
stack栈：/
输出：8 3 + 9 2 - *
读到“(”,直接压入栈；
读到数字6，直接输出；
读到操作符“+”，由于栈顶是“(”，所以直接压入栈；
-
读到数字1，直接输出；
stack栈： / ( +
输出： 8 3 + 9 2 - 6 1
-
读到“)”,弹出并输出“+”，弹出“(”
stack栈： /
输出： 8 3 + 9 2 - 6 1 +
-
最后，由于已经读完这个算术表达式，所以将栈中的元素依次弹出并输出
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;
}
