有关栈的记录：
// 栈----先进后出
// 栈的方法：
// push 添加一个元素到栈顶
// pop 弹出栈顶元素
// top 返回栈顶元素，注意，不是弹出
// isEmpty 判断栈是否为空
// size 返回栈里元素的个数
// clear 清空栈
// 栈的方法
function Stack () {
var items = []; // 存储数据
// 从栈顶添加元素，也叫压栈
this.push = function () {
items.push(item);
};
// 弹出栈顶元素
this.pop = function () {
return items.pop();
};
// 返回栈顶元素
this.top = function () {
return items[items.length-1];
};
// 判断栈是否为空
this.isEmpty = function () {
return items.length == 0;
};
// 返回栈的大小
this.size = function () {
return items.length
};
// 清空栈
this.clear = function () {
items = [];
};
}
//判断字符串里的括号是否合法
function is_leagl_brackets (string) {
var stack = new Stack();
for(var i=0; i<string.length; i++){
var item = string[i];
// 遇到左括号入栈
if(item == "("){
stack.push(item);
}else if(item == ")"){
// 遇到右括号，判断栈是否为空
if(stack.isEmpty()){
return false;
}else{
stack.pop(); // 弹出左括号
}
}
}
// 如果栈为空，说明字符串括号合法
return stack.isEmpty();
}
console.log(is_leagl_brackets('())(())('))
// 中缀表达式 a+b，1+2，2*2
// 后缀表达式 ab+，3+，4*；计算机里的计算方法
// 原理：使用for循环遍历数组，对每一个元素做如下操作
// 1. 如果元素不是+-*/中的某一个，就压入栈中
// 2. 如果元素是+-*/中的某一个，则从栈里连续弹出两个元素，并对这两个元素进行计算，将计算结果压入栈中
// for循环结束之后，栈里只有一个元素，这个元素就是整个表达式的计算结果
function calc_exp(exp){
var stack = new Stack();
for(var i=0; i<exp.length; i++){
var item = exp[i];
if(["+","-","*","/"].indexOf(item) >= 0){
var val1 = stack.pop();
var val2 = stack.pop();
// 第一次弹出来的数值在操作符的右边，第二次弹出的值在操作符的左边
var exp_str = val2 + item + val1;
//计算并取整
var res = parseInt(eval(exp_str));
stack.push(res.toString());
}else{
stack.push(item)
}
}
return stack.pop();
}
// 4+13/5 对应的后缀表达式 ["4","13","5","/","-"]
console.log(calc_exp(["4","13","5","/","-"]))
// 实现一个栈，除了常见的push,pop方法外，提供一个min方法，返回栈里最小的元素，且时间复杂度为o(1)
function MinStack(){
var data_stack = new Stack.Satck(); // 存储数据
var min_stack = new Stack.Satck(); // 存储最小的值
// push方法
this.push = function(item){
data_stack.push(item);
// min_stack为空或者栈顶元素大于item
if(min_stack.isEmpty() || item < min_stack.top()){
min_stack.push(item);
}else{
min_stack.push(min_stack.top());
}
};
// 弹出栈顶元素
this.pop = function(){
data_stack.pop();
min_stack.pop();
};
// 返回栈的最小值
this.min = function(){
return min_stack.pop();
};
}
minstack = new MinStack();
minstack.push(3);
minstack.push(6);
minstack.push(8);
console.log(minstack.min())
// 中缀表达式转后缀表达式
var priority_map = {
"+": 1,
"-": 1,
"*": 2,
"/": 2
};
function infix_exp_2_postfix_exp(exp){
var stack = new Stack.Stack();
var postfix_lst = [];
for(var i=0; i<exp.length; i++){
var item = exp[i];
// 如果是数字，直接放入到postfix_lst中
if(!isNaN(item)){
postfix_lst.push(item);
}else if(item == "("){
// 遇到左括号入栈
stack.push(item);
}else if(item == ")"){
// 遇到右括号，把栈顶元素弹出，直到遇到左括号
while(stack.top() != "("){
postfix_lst.push(stack.pop());
}
stack.pop(); //左括号出栈
}else{
// 遇到运算符，把栈顶的运算符弹出，直到栈顶的运算符优先级小于当前运算符
while(!stack.isEmpty() && ["+","-","*","/"].indexOf(stack.top()) >=0
&& priority_map[stack.top()] >= priority_map[item]){
// 把弹出的运算符加入到postfix_lst
postfix_lst.push(stack.pop());
}
}
}
}
