中、后缀转前缀表达式以及前缀表达式求值的实现

发表于 | 分类于

前言

前中后缀表达式的基本介绍可见上篇文章：前中转后缀，本文不再赘述。

本文将实现将中缀、后缀表达式转变为前缀表达式并且实现一个简单的前缀表达式计算器。同时本文依旧约定表达式的基本数据结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
enum OperType
{
        /*OPERAND-操作数，OPERATOR-操作符*/
        OPERAND, OPERATOR
};

template <typename DataType>
union OperData
{
        char operatorCh;
        DataType operand;
};

template <typename DataType>
struct ExpressionAtom
{
        OperType operFlag;
        OperData<DataType> operValue;
};

注：本文所指表达式操作符只含有双目运算符且运算符的结合顺序为从左到右。

中缀转前缀表达式

前缀表达式在表达式树中的遍历顺序为：根->左->右，而后缀表达式的遍历顺序为：左->右->根。如果把后缀表达式逆序（即采用栈来存放结果），此时得到的表达式操作数和结合顺序均发生反向，如果我们采用从中缀表达式右端向左端扫描的方式则可以抵消这个影响。中缀表达式转后缀表达式中有一个经典的调度场算法，我们综合上述考虑和修改该算法便可以得到中缀转前缀表达式的算法。算法对于括号处理也需要反向。同时在操作符压栈时和中缀转后缀略有区别的是如果优先级相等也需要接着入栈（左结合）。具体实现代码如下：

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
#include <vector>
#include <stack>
using std::vector;
using std::stack;

bool isGreater(char oper1, char oper2)
{
        if (oper2 == ')') {
                return true;
        }

        if (oper1 == '+' || oper1 == '-') {
                if (oper2 == '*' || oper2 == '/') {
                        return false;
                }
                else {
                        return true;
                }
        }
        return true;
}

template <typename DataType>
void PopOperatorUntilRightBracket(stack<ExpressionAtom<DataType>> &operatorStack,
         stack<ExpressionAtom<DataType>> &resultStack)
{
        while (operatorStack.top().operValue.operatorCh != ')') {
                resultStack.push(operatorStack.top());
                operatorStack.pop();
        }
        operatorStack.pop(); /*弹出右括号*/
}

template <typename DataType>
void PopOperatorUntilLowPriority(stack<ExpressionAtom<DataType>> &operatorStack,
         stack<ExpressionAtom<DataType>> &resultStack, char nowOperator)
{
        while (!operatorStack.empty() &&
                        !isGreater(nowOperator, operatorStack.top().operValue.operatorCh)) {
                resultStack.push(operatorStack.top());
                operatorStack.pop();
        }
}

template <typename DataType>
vector<ExpressionAtom<DataType>> InfixToPrefix(vector<ExpressionAtom<DataType>> &inInfix)
{
        stack<ExpressionAtom<DataType>> operatorStack;

        stack<ExpressionAtom<DataType>> resultStack;

        /*不做差错检测*/
        for (int i = (int)inInfix.size() - 1; i >= 0; i--) {
                if (inInfix[i].operFlag == OPERATOR) {
                        if (inInfix[i].operValue.operatorCh == '(') {
                                PopOperatorUntilRightBracket(operatorStack, resultStack);
                        }
                        else if (inInfix[i].operValue.operatorCh == ')') {
                                operatorStack.push(inInfix[i]);
                        }
                        else {
                                PopOperatorUntilLowPriority(operatorStack, resultStack,
                                        inInfix[i].operValue.operatorCh);
                                operatorStack.push(inInfix[i]);
                        }
                }
                else {
                        resultStack.push(inInfix[i]);
                }
        }


        /*清空栈中操作符*/
        while (!operatorStack.empty()) {
                resultStack.push(operatorStack.top());
                operatorStack.pop();
        }

        vector<ExpressionAtom<DataType>> result;
        while (!resultStack.empty()) {
                result.push_back(resultStack.top());
                resultStack.pop();
        }
        return result;
}

中缀转前缀代码测试

使用如下图所示表达式树生成的中缀表达式来进行测试：图片来源
表达式树

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
143
144
145
146
147
148
#include <iostream>
#include <vector>
#include <queue>
using std::vector;
using std::queue;
using std::cout;
using std::endl;

template <typename DataType>
void PrintExpression(vector<ExpressionAtom<DataType>> &inExpr)
{
        for (size_t i = 0; i < inExpr.size(); i++) {
                if (inExpr[i].operFlag == OPERAND) {
                        cout << inExpr[i].operValue.operand << ";";
                }
                else {
                        cout << inExpr[i].operValue.operatorCh << ";";
                }
        }
        cout << endl;
}


int main()
{
        vector<ExpressionAtom<int>> testVec;

        ExpressionAtom<int> manualData;

        /*表达式为(3+1)*3/(9-5-2)-(3*(7-4)+6)*/

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '(';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 3;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '+';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 1;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = ')';
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '*';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 3;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '/';
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '(';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 9;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '-';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 5;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '+';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 2;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = ')';
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '-';
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '(';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 3;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '*';
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '(';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 7;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '-';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 4;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = ')';
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '+';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 6;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = ')';
        testVec.push_back(manualData);


        PrintExpression(testVec);

        auto result = InfixToPrefix(testVec); /*调用函数*/

        PrintExpression(result);

        return 0;
}

后缀转前缀表达式

前缀和后缀表达式在表达式树中的遍历顺序：前缀，根->左->右；后缀，左->右->根。分析和前缀转中缀类似，但是考虑后缀顺序反向，因此我们采取从后往前扫描的策略，同时采用栈存放操作数操作符以及根访问次数。只需将前缀转后缀代码稍加修改即可，具体代码如下所示：

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
#include <vector>
#include <stack>
using std::vector;
using std::stack;

template <typename DataType>
vector<ExpressionAtom<DataType>> PostfixToPrefix(vector<ExpressionAtom<DataType>> &inPostfix)
{
        stack<ExpressionAtom<DataType>> operatorStack;
        stack<int> visitTimesStack;
        stack<ExpressionAtom<DataType>> resultStack;

        /*不做差错检测*/
        for (int i = (int)inPostfix.size() - 1; i >= 0; i--) {
                /*前序遍历在第一次访问时弹出*/
                while (!visitTimesStack.empty() && visitTimesStack.top() <= 0) {
                        resultStack.push(operatorStack.top());
                        operatorStack.pop(); visitTimesStack.pop();
                }
                /*每访问一次-1*/
                if (!visitTimesStack.empty()) {
                        --visitTimesStack.top();
                }
                if (inPostfix[i].operFlag == OPERATOR) {
                        operatorStack.push(inPostfix[i]);
                        visitTimesStack.push(2); /*后序遍历为最后一次访问*/
                }
                else {
                        resultStack.push(inPostfix[i]);
                }
        }

        /*清空栈中操作符*/
        while (!visitTimesStack.empty() && visitTimesStack.top() <= 0) {
                resultStack.push(operatorStack.top());
                operatorStack.pop(); visitTimesStack.pop();
        }

        vector<ExpressionAtom<DataType>> result;
        while (!resultStack.empty()) {
                result.push_back(resultStack.top());
                resultStack.pop();
        }
        return result;
}

后缀转前缀代码测试

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
#include <iostream>
#include <vector>
#include <queue>
using std::vector;
using std::queue;
using std::cout;
using std::endl;

template <typename DataType>
void PrintExpression(vector<ExpressionAtom<DataType>> &inExpr)
{
        for (size_t i = 0; i < inExpr.size(); i++) {
                if (inExpr[i].operFlag == OPERAND) {
                        cout << inExpr[i].operValue.operand << ";";
                }
                else {
                        cout << inExpr[i].operValue.operatorCh << ";";
                }
        }
        cout << endl;
}


int main()
{
        vector<ExpressionAtom<int>> testVec;

        ExpressionAtom<int> manualData;

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 3;
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 1;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '+';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 3;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '*';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 9;
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 5;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '-';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 2;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '+';
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '/';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 3;
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 7;
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 4;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '-';
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '*';
        testVec.push_back(manualData);


        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 6;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '+';
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '-';
        testVec.push_back(manualData);

        PrintExpression(testVec);

        auto result = PostfixToPrefix(testVec);

        PrintExpression(result);

        return 0;
}

前缀表达式求值

前缀表达式可以快速转变成后缀表达式然后通过后缀表达式间接进行求值，但是前缀表达式也是可以直接求值，前缀表达式正确地表达了运算优先顺序，后缀表达式是从前往后依次求值，那么考虑到前缀表达式操作符在运算符前面，因此我们只需从后往前扫描前缀表达式即可，其余部分和后缀表达式求值类似，其代码稍作修改既可用于前缀求值，具体代码如下：

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
#include <vector>
#include <stack>
using std::vector;
using std::stack;

template <typename DataType>
DataType Calculate(DataType inData1, DataType inData2, char operatorCh)
{
        if (operatorCh == '+') {
                return inData1 + inData2;
        }
        else if (operatorCh == '-') {
                return inData1 - inData2;
        }
        else if (operatorCh == '*') {
                return inData1 * inData2;
        }
        else if (operatorCh == '/') {
                return inData1 / inData2;
        }
        else {
                return DataType(0);
        }
}

template <typename DataType>
DataType CalculatePrefixValue(vector<ExpressionAtom<DataType>> &inPrefix)
{
        stack<DataType> operandStack;

        /*不做差错检测*/
        for (int i = (int)inPrefix.size() - 1; i >= 0; i--) {
                if (inPrefix[i].operFlag == OPERATOR) {
                        int tmp1 = operandStack.top(); operandStack.pop();
                        int tmp2 = operandStack.top(); operandStack.pop();
                        int result = Calculate(tmp1, tmp2, inPrefix[i].operValue.operatorCh);
                        operandStack.push(result);
                }
                else {
                        operandStack.push(inPrefix[i].operValue.operand);
                }
        }
        return operandStack.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
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
143
144
145
146
147
148
149
150
151
152
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using std::vector;
using std::stack;
using std::queue;
using std::cout;
using std::endl;

template <typename DataType>
void PrintExpression(vector<ExpressionAtom<DataType>> &inExpr)
{
        for (size_t i = 0; i < inExpr.size(); i++) {
                if (inExpr[i].operFlag == OPERAND) {
                        cout << inExpr[i].operValue.operand << ";";
                }
                else {
                        cout << inExpr[i].operValue.operatorCh << ";";
                }
        }
        cout << endl;
}


int main()
{
        vector<ExpressionAtom<int>> testVec;

        ExpressionAtom<int> manualData;

        /*表达式为(3+1)*3/(9-5-2)-(3*(7-4)+6)*/

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '(';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 3;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '+';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 1;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = ')';
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '*';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 3;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '/';
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '(';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 9;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '-';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 5;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '+';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 2;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = ')';
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '-';
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '(';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 3;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '*';
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '(';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 7;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '-';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 4;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = ')';
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = '+';
        testVec.push_back(manualData);

        manualData.operFlag = OPERAND;
        manualData.operValue.operand = 6;
        testVec.push_back(manualData);

        manualData.operFlag = OPERATOR;
        manualData.operValue.operatorCh = ')';
        testVec.push_back(manualData);


        PrintExpression(testVec);

        auto result = InfixToPrefix(testVec); /*调用函数*/

        PrintExpression(result);

        cout << CalculatePrefixValue(result) << endl; /*测试代码*/

        return 0;
}

参考资料

波兰表示法-维基百科

中缀表示法-维基百科

逆波兰表示法-维基百科

调度场算法-维基百科

中缀/后缀/前缀表达式求值