前、后缀表达式转中缀表达式的实现

发表于 | 分类于

前言

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

本文将实现将前缀、后缀表达式转变为中缀表达式。约定放置表达式的基本数据结构依然如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
#include <vector>
#include <stack>
#include <queue>
using std::vector;
using std::stack;
using std::queue;

template <typename DataType>
vector<ExpressionAtom<DataType>> PrefixToInfix(vector<ExpressionAtom<DataType>> &inPrefix)
{
        stack<ExpressionAtom<DataType>> operatorStack;
        stack<int> visitTimesStack;
        queue<ExpressionAtom<DataType>> resultQueue;

        /*不做差错检测*/
        for (size_t i = 0; i < inPrefix.size(); i++) {
                /*中序遍历在第二次访问时弹出*/
                while (!visitTimesStack.empty() && visitTimesStack.top() >= 1) {
                        resultQueue.push(operatorStack.top());
                        operatorStack.pop(); visitTimesStack.pop();
                }

                if (inPrefix[i].operFlag == OPERATOR) {
                        operatorStack.push(inPrefix[i]);
                        visitTimesStack.push(0); /*初始化访问数据*/
                }
                else {
                        /*每访问一次+1*/
                        if (!visitTimesStack.empty()) {
                                ++visitTimesStack.top();
                        }
                        resultQueue.push(inPrefix[i]);
                }
        }

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

        vector<ExpressionAtom<DataType>> result;
        while (!resultQueue.empty()) {
                result.push_back(resultQueue.front());
                resultQueue.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
#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 = 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 = 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 = 1;
        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 = OPERAND;
        manualData.operValue.operand = 5;
        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 = OPERATOR;
        manualData.operValue.operatorCh = '-';
        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 = OPERAND;
        manualData.operValue.operand = 6;
        testVec.push_back(manualData);

        PrintExpression(testVec);

        auto result = PrefixToInfix(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
46
#include <vector>
#include <stack>
using std::vector;
using std::stack;

template <typename DataType>
vector<ExpressionAtom<DataType>> PostfixToInfix(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();
                }

                if (inPostfix[i].operFlag == OPERATOR) {
                        operatorStack.push(inPostfix[i]);
                        visitTimesStack.push(1); /*中序遍历为第二次访问*/
                }
                else {
                        /*每访问一次-1*/
                        if (!visitTimesStack.empty()) {
                                --visitTimesStack.top();
                        }
                        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 = PostfixToInfix(testVec);

        PrintExpression(result);

        return 0;
}

参考资料

波兰表示法-维基百科

中缀表示法-维基百科

逆波兰表示法-维基百科

调度场算法-维基百科