第四章 栈

栈的主要方法和属性

1. 栈的实现

function Stack() {
    this.dataStore = []; // 保存元素
    this.pop = pop;
    this.push = push;
    this.peek = peek;
    this.clear = clear;
    this.length = length;
    this.top = 0; // 指示新添加元素在数组中的插入位置
}

function pop() {
    return this.dataStore[--this.top];
}

function push(ele) {
    this.dataStore[this.top++] = ele;
}

function peek() {
    return this.dataStore[this.top-1];
}

function clear() {
    this.top = 0;
}

function length() {
    return this.top;
}

2. 练习

2.1 栈可以用来判断一个算术表达式中的括号是否匹配。

编写一个函数，该函数接受一个算术表达式作为参数，返回括号缺失的位置。下面是一个括号不匹配的算术表达式的例子：2.3 + 23 / 12 + (3.14159×0.24。

function matchBracket(expression) {
    // 如果匹配，返回-1，否则返回缺失的位置
    var stackOpt = new Stack();
    var eles = expression.split('');
    for (var i = 0; i < eles.length; i++) {
        var ele = eles[i];
        if (['{', '[', '('].indexOf(ele) !== -1) {
            stackOpt.push(ele);
        } else {
            var topEle = stackOpt.peek();
            switch (ele) {
                case '}':
                    if (topEle === '{') {
                        stackOpt.pop();
                        break;
                    }
                    return i+1;
                case ']':
                    if (topEle === '[') {
                        stackOpt.pop();
                        break;
                    }
                    return i+1;
                case ')': 
                    if (topEle === '(') {
                        stackOpt.pop();
                        break;
                    }
                    return i+1;
                default: break;
            }
        }
    };
    if (stackOpt.length()) {
        return expression.length+1;
    }
    return -1;
}

matchBracket('2.3 + 23 / 12 + (3.14159×0.24'); // 返回30.

2.2 一个算术表达式的后缀表达式形式如下：

op1 op2 operator

使用两个栈，一个用来存储操作数，另外一个用来存储操作符，设计并实现一个JavaScript函数，该函数可以将中缀表达式转换为后缀表达式，然后利用栈对该表达式求值。

function comparePriority(a, b) {
    // 比较栈顶操作符 a 和即将入栈的操作符 b 的优先级
    // a优先于b，返回 1，表示栈顶元素优先级较高，操作符需要出栈
    if (!a) { // a为空时，b入栈
        return 0;
    }

    if ((a === '(' && b !== ')') || b === '(') { // a为'('，或者b为'('时，直接入栈
        return 0;
    }
    if ((b === '*' || b === '/') && (a === '+' || a === '-')) { // b优先级大于a时，直接入栈
        return 0;
    }
    return 1;
}

function isOperator(tmp) {
    return ['+', '-', '*', '/', '(', ')'].indexOf(tmp) > -1;
}

function infixToPostfix(exp) {
    var operatorStack = new Stack();
    var postfixExp = [];

    exp.split('').forEach(function (char) {

        if (isOperator(char)) {
            // 比较优先级
            while(comparePriority(operatorStack.peek(), char)) {
                var tmp = operatorStack.pop();

                if (tmp !== '(' && tmp !== ')') {
                    postfixExp.push(tmp);
                }

                if (tmp === '(' && char === ')') { // 匹配到左括号的时候，结束循环。
                    break;
                }
            }
            if (char !== ')') {
                operatorStack.push(char);
            }
        } else {
            postfixExp.push(char);
        }
    });
    while(operatorStack.length()) {
        postfixExp.push(operatorStack.pop());
    }
    return postfixExp.join('');
}

function computePostfix(exp) {
    var numStack = new Stack();
    exp.split('').forEach(function (char) {
        if (char.trim()) {
            if (!isOperator(char)) {
                numStack.push(char);
            } else {
                var tmp = numStack.pop();
                numStack.push(eval(numStack.pop()+char+tmp));
            }
        }
    });
    return numStack.pop();
}

var postfixExp = infixToPostfix('(8-2)/(3-1)*(9-6)');
var postfixExpValue = computePostfix(postfixExp);

console.log(postfixExp); // 82-31-/96-*
console.log(postfixExpValue); // 9

最后

以上就是懵懂火车为你收集整理的第四章 栈的全部内容，希望文章能够帮你解决第四章 栈所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。