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

发表于 | 分类于

前言

前缀表达式又称波兰表达式，其将操作符放置于操作数前面，该类型的表达式无需括号仍然可以无歧义地被解析，如果将表达式以表达式树的形式展现，则前缀表达式对应于前序遍历结果。

中缀表达式在表达式中将操作符（双目）置于操作数的中间，是目前常用的一种表示方法，中缀表达式需要通过括号来指示运算优先顺序，一般中缀表达式在计算机中无法直接用于计算，中缀表达式对应于表达式树的中序遍历结果。

后缀表达式又称逆波兰表达式，式中操作符位于操作数的后面，在计算机内部易于直接计算（借助栈），和前缀表达式一样后缀表达式也无需借助括号便可以无歧地被解析，后缀表达式对应于表达式树的后序遍历结果。

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

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

template <typename DataType>
vector<ExpressionAtom<DataType>> PrefixToPostfix(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() >= 2) {
                        resultQueue.push(operatorStack.top());
                        operatorStack.pop(); visitTimesStack.pop();
                }
                /*每访问一次+1*/
                if (!visitTimesStack.empty()) {
                        ++visitTimesStack.top();
                }
                if (inPrefix[i].operFlag == OPERATOR) {
                        operatorStack.push(inPrefix[i]);
                        visitTimesStack.push(0); /*初始化访问数据*/
                }
                else {
                        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 = PrefixToPostfix(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
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
#include <vector>
#include <stack>
#include <queue>
using std::vector;
using std::stack;
using std::queue;

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

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

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

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

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

        queue<ExpressionAtom<DataType>> resultQueue;

        /*不做差错检测*/
        for (size_t i = 0; i < inInfix.size(); i++) {
                if (inInfix[i].operFlag == OPERATOR) {
                        if (inInfix[i].operValue.operatorCh == ')') {
                                PopOperatorUntilLeftBracket(operatorStack, resultQueue);
                        }
                        else if (inInfix[i].operValue.operatorCh == '(') {
                                operatorStack.push(inInfix[i]);
                        }
                        else {
                                PopOperatorUntilLowPriority(operatorStack, resultQueue,
                                        inInfix[i].operValue.operatorCh);
                                operatorStack.push(inInfix[i]);
                        }
                }
                else {
                        resultQueue.push(inInfix[i]);
                }
        }


        /*清空栈中操作符*/
        while (!operatorStack.empty()) {
                resultQueue.push(operatorStack.top());
                operatorStack.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
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 = InfixToPostfix(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 CalculatePostfixValue(vector<ExpressionAtom<DataType>> &inPostfix)
{
        stack<DataType> operandStack;

        /*不做差错检测*/
        for (size_t i = 0; i < inPostfix.size(); i++) {
                if (inPostfix[i].operFlag == OPERATOR) {
                        int tmp1 = operandStack.top(); operandStack.pop();
                        int tmp2 = operandStack.top(); operandStack.pop();
                        int result = Calculate(tmp2, tmp1, inPostfix[i].operValue.operatorCh);
                        operandStack.push(result);
                }
                else {
                        operandStack.push(inPostfix[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
#include <iostream>
#include <vector>
using std::vector;
using std::cout;
using std::endl;

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

    ExpressionAtom<int> 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 = 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 = InfixToPostfix(testVec);

    PrintExpression(result);

    cout << CalculatePostfixValue(result) << endl; /*后缀计算结果*/

    return 0;
}

参考资料

波兰表示法-维基百科

中缀表示法-维基百科

逆波兰表示法-维基百科

调度场算法-维基百科