这次聊一个比较有意思的算法，能够处理算术表达式的计算。

理解起来倒不是太难，只是不同于往常的思维方式，较为抽象。

做好准备，我们就开始吧。

算术表达式求值算法

问题描述

给定一行仅包含加减乘除括号与数字的表达式，求出结果。

如：输入(33+2)*2-4/2，输出68。

问题分析

第一眼看起来，好像也没什么难的，不就是python3中一句"print(eval(input()))"就能搞定的事情么。

但多想一想，好像又不太对？

如果按顺序计算：33+2=35；35*2=70；70-4/2……要怎么才能让计算机知道需要先算4/2=2再计算70-2呢……

就算把符号优先级告诉计算机，计算机也不一定懂分析啊……

既然如此，不如直接把算式按计算顺序重排好了再交给计算机计算，由我们来完成分析优先级的部分。

要实现优先级的重排，我们要先引入一个概念：

逆波兰表达式

逆波兰表达式又叫做后缀表达式，是一种没有括号，并严格遵循“从左到右”运算的后缀式表达方法。

比如： 1 * 2 + ( 3 - 4 / 5 ) * 6，写作逆波兰表达式就变成了： 1 2 * 3 4 5 / - 6 * + 。

当计算机计算逆波兰表达式的时候，先读入1和2，然后读入乘号，进行1*2的运算，得出2。

接着继续读入3, 4, 5，此时已经存入2, 3, 4, 5四个数字，读入除号，先进行最后两个数，即4/5的运算，得出0.8。

此时存取的数字为2, 3, 0.8，读入减号，计算3-0.8=2.2；剩下2, 2.2，读入6，存取的数字为2, 2.2, 6。

这时遇到乘号，就计算2.2*6=13.2，再遇到加号，计算最后的两个数：2+13.2=15.2。

这时15.2就是这个算式的结果，看一看，是不是和原式答案相同？

那么我们要如何将中缀表达式（常见的那种符号在中间的表达式）变为后缀表达式（逆波兰表达式）呢？

其实也不难，可以参考百度百科中提到的做法。

1、首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。

2、读入一个用中缀表示的简单算术表达式，为方便起见，设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。

3、从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。

4、如果不是数字，该字符则是运算符，此时需比较优先关系。

具体做法是：将该字符与运算符栈顶的运算符的优先关系相比较。如果该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。若不是的话，则将栈顶的运算符从栈中弹出，直到栈项运算符的优先级低于当前运算符，将该字符入栈。

5、重复步骤1～2，直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。

那么，知道了原理，我们就可以开始设计算法了。

代码实现

具体内容我已经在代码的注释里写得很详细了，理解了原理后，是不是没有那么抽象了？

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
153
154
155
156
157
158
159
//算术表达式求值算法

#include <bits/stdc++.h>
using namespace std;

int evaluateExpression();                 //算术表达式求值
bool isSymbol(char c);                    //判断c是否为操作符
bool isNum(char c);                       //判断c是否为数字
int priority(char x, char y);             /*判断x和y的优先级; 若x较高:返回1 ;若x较低:返回-1;若相同:返回0
                                            优先级相同的情况: 1.都为'#':为空; 2.为'('和')':括号里面没有任何值*/
int calculate(int a, char symbol, int b); //进行双目计算

int main()
{
    while (1)
    {
        cout << "请输入表达式,以#结尾:" << endl;
        cout << evaluateExpression() << endl;
        fflush(stdin); //用来吞回车
    }
    return 0;
}

int evaluateExpression()
{
    stack<int> OP_NUM;     //存放操作数
    stack<char> OP_SYMBOL; //存放操作符
    int a, b;              //存放需要临时计算的两个数字
    char c;                //c存放当前读入的字符

    OP_SYMBOL.push('#'); //先压入一个#, 后续用于判断运算结束
    c = getchar();
    while (c != '#' || OP_SYMBOL.top() != '#') //只有当前字符为#且栈顶字符也为#时(说明没有其他符号了), 才说明读取结束
    {
        if (isSymbol(c))
        {
            switch (priority(OP_SYMBOL.top(), c))
            {
            //栈顶操作符优先级小于当前操作符, 先把当前操作符进栈
            case -1:
                OP_SYMBOL.push(c);
                c = getchar();
                break;
            //栈顶操作符优先级较高, 先用该操作符计算数字栈顶两个元素, 将结果入数据栈, 然后重新将当前操作符与下一个比较
            case 1:
                //取出数据栈顶的两个元素, 因为入栈和出栈的顺序是反的, 为了符合习惯阅读顺序, 先取b再取a
                b = OP_NUM.top();
                OP_NUM.pop();
                a = OP_NUM.top();
                OP_NUM.pop();

                OP_NUM.push(calculate(a, OP_SYMBOL.top(), b));
                OP_SYMBOL.pop();
                break;
            //返回值为0, 说明该操作为空操作, 直接出栈不管
            case 0:
                OP_SYMBOL.pop();
                c = getchar();
                break;
            }
        }

        else if (isNum(c))
        {
            int temp;           //如果读入的是数字,需要将该数字完整地读完;如"233",需要分别读三次
            char d = getchar(); //读入下一个字符,判断是否为数字
            temp = c - 48;
            while (isNum(d)) //如果d为数字, 就不断读入并合并, 直到读到符号为止
            {
                temp = temp * 10 + (d - 48);
                d = getchar();
            }
            c = d; //将该符号赋给c
            OP_NUM.push(temp);
        }

        else //能运行到这里, 说明有非法字符的输入
        {
            cout << "Input Error" << endl;
            exit(0);
        }
    }
    return OP_NUM.top(); //运算结束, 返回最后剩余的栈顶数字, 即为结果
}

bool isSymbol(char c)
{
    return (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')' || c == '#');
}

bool isNum(char c)
{
    return (c >= 48 && c <= 57);
}
int priority(char x, char y)
{
    switch (x)
    {
    //操作符优先级:括号>乘除>加减
    case '+':
        return (y == '*' || y == '/' || y == '(') ? -1 : 1;
    case '-':
        return (y == '*' || y == '/' || y == '(') ? -1 : 1;
    case '*':
        return (y == '(') ? -1 : 1;
    case '/':
        return (y == '(') ? -1 : 1;
    case '(':
        //栈顶左括号的情况要特殊考虑:如果当前操作符为#,说明没有右括号匹配,程序错误
        if (y == '#')
        {
            cout << "Please enter correct expression" << endl;
            exit(0);
        }
        //如果当前操作符为右括号, 说明括号中为空, 无视即可
        //如果是其他操作符, 返回-1使得当前操作符得以进栈
        return (y == ')') ? 0 : -1;
    case ')':
        //括号不匹配, 程序错误
        if (y == '(')
        {
            cout << "Please enter correct expression" << endl;
            exit(0);
        }
        //遇到右括号, 说明括号内的内容已经被完成地输入, 需要拿出来优先计算
        return 1;
    case '#':
        //栈顶操作符为#, 说明是程序刚开始或结束, 刚开始就出现右括号, 肯定错误
        if (y == ')')
        {
            cout << "Please enter correct expression" << endl;
            exit(0);
        }
        //如果当前操作符也为#, 说明程序结束, 返回0即可
        //其余情况下都返回-1, 使得当前操作符得以进栈
        return (y == '#') ? 0 : -1;
    }
    return 0;
}
int calculate(int a, char symbol, int b)
{
    switch (symbol)
    {
    case '+':
        return a + b;
    case '-':
        return a - b;
    case '*':
        return a * b;
    case '/':
        if (b == 0)
        {
            cout << "Division by zero" << endl;
            exit(0);
        }
        return a / b;
    }
    return 0;
}