第四章 栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
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