编程入门项目二：实现一个自己的计算器程序

计算器程序的功能设计

一般计算器功能如下：

第一次出现的变量赋值语句，即为变量定义；
计算表达式的值。

这两个功能，看似简单，可实际要考虑的还很多，例如：变量是否有作用域的限制啊，合法变量名的规则，表达式中支持的运算符种类啊，每一种运算符的优先级，等等。这些需要考虑的细节，每一个都会给我们的项目增加一点点难度。

为了把难度控制在一个可以实现的范围，我们对计算器功能做进一步的细致描述，同时也是降低项目实现难度，重新修订的功能定义如下：

第一次出现的变量赋值语句，即为变量定义；
计算表达式的值；
没有作用域的概念，所有变量都是全局变量；
变量名只允许 26 个小写的英文字母，也就是说，程序中最多有 26 个变量；
表达式只支持四则混合运算 +、-、*、/ 以及 ()；
表达式中参与运算的值均为正整数，除法规则参考 C 语言整形之间的除法规则；
变量赋值语句和表达式语句，均各占一行。

样例输入：

1
2
3

a = 3
b = a * 3 + 5
(a + 4) * (b + 5)

可以看到，第 1 行输入，定义了变量 a，同时给 a 变量赋值为 3；第 2 行，定义了变量 b，同时给 b 变量赋值为 a * 3 + 5 的值，也就是 14；第 3 行，是一行表达式，计算的是 (a + 4) * (b + 5) 的值，最后的结果应该等于 7 * 19 = 133。

针对这份输入数据，我们的计算器程序分别输出每行表达式对应的值，也就是：

1
2
3

3
14
133

二叉树的遍历

基本概念

二叉树，就是每个节点下面最多有两个子节点的结构。如下图所示，就是一个二叉树结构：

我们把其中的 A 节点叫做“根节点”，B 和 C 是 A 节点的两个“子节点”，同理，E 和 F 是 C 节点的两个子节点，D 是 B 节点的子节点。如果更细致地划分，以 B 为根节点的子树，处于 A 节点的左侧，所以称为 A 节点的左子树，C 称为 A 节点的右子树。反过来，我们把 A 节点称为 B 和 C 节点的父节点，同时它也是 D、E、F 节点的祖先节点。

三种遍历方式

每一种遍历的方式，都是采用递归的定义方式。而所谓的前、中、后序遍历，其实说的是根节点的位置：根节点在左右子树遍历之前，那就是前序遍历；夹在左右子树中间，就是中序遍历；位于左右子树遍历之后，那就是后序遍历。

如果我们将上上图中的二叉树结构，分别按照三种方式进行遍历，会得到如下所示的遍历结果：

1
2
3

前序遍历：A B D C E F
中序遍历：D B A E C F
后序遍历：D B E F C A

注意，在写某一种遍历结果的时候，一定是按照递归展开的方式。例如：

在中序遍历中，我们是将根节点左子树所形成的中序遍历结果（D B），放在根节点 A 的左侧，然后是根节点 A，接着是根节点右子树的中序遍历结果（E C F）。所以最后，整棵树的中序遍历结果就是 D B A E C F。

思维利器：表达式树

基本概念

任何一个四则混合运算的表达式，都能转换成相对应的二叉树，而原表达式的值，等于对应二叉树的后序遍历结果。例如，下图就是一个加法表达式和它所对应的表达式树：

在表达式树中，根节点就是运算符 +(加号)，加号的左子树是数字 3，右子树是数字 5。根据刚刚所说的对应规则，在表达式树上，按照后序遍历的顺序，得到的就是表达式的值。图 3 中的表达式树，首先遍历得到左子树的数字 3，再遍历得到右子树的数字 5，最后遍历到根节点的运算符 +(加号)，就将左右子树的值做加法，得到原表达式的结果 8。

我们来看一个稍微复杂一点儿的表达式，以及它所对应的表达式树。

从图中可见，原表达式是 (3 + 5) * (6 - 2)，而其对应的表达式树中，已经没有了括号的影子。因为，图中表达式树的计算顺序应该是这样的：首先计算左子树所代表的 3 + 5 表达式的值，再计算右子树代表的 6 - 2 表达式的值，最后根据根节点的乘法运算，计算得到左右子树的乘积值。

表达式树的这种计算顺序，与原表达式添加了括号以后的计算顺序等价。

综上所述，我们可知，表达式树中越靠近根节点的运算符，优先级越低，而根节点代表了原表达式中，优先级最低的那个运算符。表达式中原有的括号，其实就是用来控制运算符之间的计算顺序的，这种计算顺序，对应的就是表达式树中的父子节点关系，这就是我们刚刚所说的，原表达式中的括号，被转换成了等价的树形结构关系的含义。

利用这种思维，解决表达式计算问题

任何一个表达式，都对应一个等价的表达式树。而这个表达式树的根节点所对应的，就是原表达式中最后一个被计算的运算符。如果我们可以找到这个运算符在原表达式中的位置，那么这个运算符所的左边部分，对应的就是表达式树根节点的左子树，运算符的右边部分，对应的就是表达式树根节点的右子树。

我们用 String 代表原表达式字符串，op 代表整个表达式中最后一个被计算的运算符，L_String 是 op 运算符左边的字符串，R_String 就是右边的字符串。

假设，我们有一个函数 get_val(String)，可以得到 String 所代表的表达式的值。那么关于 get_val(String)，我们就可以得到如下递推关系：

1	get_val(String) = get_val(L_String) op get_val(R_String)

也就是当前表达式的值，等于左边表达式的值与右边表达式的值之间的运算结果。举例子：

1	get_val("(3+5)(6-2)") = get_val("(3+5)") get_val("(6-2)")

如果我们能确定，表达式字符串中最后一个被计算的运算符的位置，我们就可以把原表达式字符串分成两部分，进行递归求解。所以，找到最后一个被计算的运算符的位置，才是我们完成程序的关键。

确定运算符顺序的技巧

问：怎么确定表达式中每一个运算符的计算顺序呢？
答：可以通过给每个运算符赋予一个权重，权重越高，代表计算优先级越高。

问：怎么设置权重？
答：根据四则混合运算的基础规则，我们可以给 +、-、、/ 运算符设定一个基础权重，例如，+、- 权重是 1，、/ 权重是 2；另外，可以对括号里面的所有运算符，额外加上一个很大的权重。

小结

二叉树的三种遍历方式：前序遍历、中序遍历与后序遍历，它们主要是依据根节点的位置划分出来的。
我们掌握了表达式与其对应的表达式树的对应关系。
表达式树的后续遍历结果，就等于原表达式的值。这种特性，给我们设计表达式求值程序，提供了思维方面的指导。

参考代码

#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f

/*
* 计算表达式 str 从 l 到 r 位置的值
* */
int calc(const char *str, int l, int r) {
    /*
    * pos : 根节点运算符的位置，初始化为 -1
    * priority : 根节点运算符的权重
    * temp : 由括号产生的额外权重
    * */
    int pos = -1, priority = INF - 1, temp = 0;
    for (int i = l; i <= r; i++) {
        int cur_priority = INF;
        switch (str[i]) {
            case '(': temp += 100; break;
            case ')': temp -= 100; break;
            case '+':
            case '-': cur_priority = 1 + temp;
            case '*':
            case '/': cur_priority = 2 + temp;
            default: break;
        }
        /*
        * cur_priority : 当前运算符的优先级
        * 更新区间内最低优先级的运算符的位置
        * */
        if (cur_priority <= priority) {
            pos = i;
            priority = cur_priority;
        }
    }

    /*
    * 如果 pos == -1，说明这一段表达式中没有运算符
    * 说明，这一段表达式中只有数字，也就是递归到了树的叶子结点
    * */
    if (pos == -1) {
        int num = 0;
        for (int i = l; i <= r; i++) {
            if (str[i] < '0' || str[i] >= '9') continue;
            num = num * 10 + (str[i] - '0');
        }
        return num;
    }

    /*
    * 递归计算得到运算符左边及右边表达式的值
    * 再根据当前运算符，得到当前表达式的值
    * */
    int a = calc(str, l, pos - 1);
    int b = calc(str, pos + 1, r);
    switch (str[pos]) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b;
    }
    return 0;
}

int get_val(const char *str) {
    return calc(str, 0, strlen(str) - 1);
}

int main() {
    char str[1000];
    while (scanf("%[^\n]", str) != EOF) {
        getchar();
        printf("%s = %d\n", str, get_val(str));
    }
    return 0;
}

项目地址