栈实现中缀表达式转后缀表达式

发表于   |   分类于

最近在看《数据结构与算法的JavaScript描述》这本书，第四章栈的练习中有这么一题：“设计并实现一个JavaScript函数，该函数可以将中缀表达式转换为后缀表达式，然后利用栈对该表达式求值。”于是就有了这篇博客，记录这个算法的实现。

算法分析

参考详解如何将中缀表达式转化为后缀表达式
中缀表达式转后缀表达式遵循的规则：
1、任何中缀表达式都由运算数、运算符、括号这三部分组成。
2、从中缀表达式的左边开始扫描，遇到运算数时，直接将其输出，不压入堆栈。
3、若遇到左括号，则将其压入堆栈。
4、若遇到右括号，表示括号内的中缀表达式已经扫描完毕，这时需要将栈顶的运算符依次弹出并输出，直至遇到左括号，左括号弹出不输出。
5、若遇到的是运算符：如果该运算符的优先级大于栈顶运算符的优先级时，将其压入堆栈，否则，将栈顶运算符弹出并输出，接着和新的栈顶运算符比较，若大于，则将其压栈，若小于，继续将栈顶运算符弹出并输出…..一直敌对下去，直至当前运算符大于栈顶运算符位置。
6、最后一步，若扫描到中缀表达式的末尾（即扫描结束），若堆栈中还有存留的运算符依次弹出并输出即可。

知道了上面这些规则，下面就可以开始写代码了。

代码实现

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
function Stack(){
    this.dataStore = [];
    this.push = push;
    this.pop = pop;
    this.length = length;
    this.peek = peek;
    this.isEmpty = isEmpty;
    this.toString = toString;
}
function push(ele){
    this.dataStore.push(ele);
}
function pop(){
    return this.dataStore.pop();
}
function peek(){
    return this.dataStore[this.dataStore.length-1];
}
function isEmpty(){
    return this.dataStore.length === 0;
}
function length(){
    return this.dataStore.length;
}
function toString(){
    let concat = '';
    for(let i=0;i<this.dataStore.length;i++){
        concat += this.dataStore[i];
    }
    return concat;
}
function weight(str){
    switch(str){
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;       
    }
}
function expressionChange(expression){
    let now = '';
    let newExpress = [];
    let operator = new Stack();
    for( let i=0; i<expression.length;i++){
        now = expression[i];
        if(/\d/.test(now)){
            let str = '';
            while(/\d/.test(expression[i])){
                str += expression[i];
                i++;
            }
            newExpress.push(str);
            i--;
        }else if(/[+\-*\/]/.test(now)){
            ({operator, newExpress} = compare(now, operator, newExpress));
        }else if(now === '('){
            operator.push(now);
        }else if(now === ')'){
            ({operator, newExpress} = popOperator(operator, newExpress));
        }
    }
    while(!operator.isEmpty()){
        newExpress.push(operator.pop());
    }
    return newExpress;
}
function newIsDigit(now, newExpress){
}
function popOperator(operator, newExpress){
    if(operator.peek() === '('){
        operator.pop();
    }else{
        newExpress.push(operator.pop());
        ({operator, newExpress} = popOperator(operator, newExpress));
    }
    return {newExpress: newExpress, operator: operator};
}
function compare(now, operator, newExpress){
    if(operator.isEmpty()){
        operator.push(now);
    }else{
        let nowWeight = weight(now);
        let topWeight = weight(operator.peek());
        if(nowWeight > topWeight){
            operator.push(now);
        }else{
            newExpress.push(operator.pop());
            ({operator, newExpress} = compare(now, operator, newExpress));
        }
    }
    return {newExpress: newExpress, operator: operator};
}
function calculate(express){
    if(express.length>1){
        for(let i=0; i<express.length; i++){
            if(/[*+\-\/]/.test(express[i])){
                let first = express[i-2];
                let second = express[i-1];
                express.splice(i-2, 3, operator(first, second, express[i]));
                return calculate(express);
            }
        }
    }else{
        return express[0];
    } 
}
function operator(first, second, operator){
    switch(operator){
        case '*':
            return Number(first) * Number(second);
        case '/':
            return Number(first) / Number(second);
        case '+':
            return Number(first) + Number(second);
        case '-':
            return Number(first) - Number(second);
    }
}
var express = '20*(9+6/3-5)+4';
var suffixExpress = expressionChange(express)
console.log(suffixExpress.join(' '));
var result = calculate(suffixExpress);
console.log(result);