表达式树

二叉树是表达式处理的常用工具。例如，表达式

  1. a+b*(c-d)-e/f

image.png
其中，每个非叶子结点表示一个运算符，左子树是第一个运算数对应的表达式，而右子树则是第二个运算数对应的表达式。如何给一个表达式简历表达式树呢？方法有很多，这里只介绍一种：找到“最后计算”的运算符（它是整颗表达式树的根），然后递归处理。

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. const int N = 1010;
  7. int lch[N], rch[N], idx, root;
  8. char op[N], s[N];
  10. int build_tree(char *s, int x, int y){
  11.     int c1 = -1, c2 = -1, p = 0;
  12.     int u;
  14.     if (y - x == 1){   // 只有一个字符了 
  15.         u = ++idx;
  16.         lch[u] = rch[u] = -1;
  17.         op[u] = s[x];
  18.         return u;
  19.     }
  21.     for (int i = x; i < y; i++){
  22.         if (s[i] == '(') p++;
  23.         if (s[i] == ')') p--;
  24.         if (s[i] == '+' || s[i] == '-')
  25.             if (!p) c1 = i;
  26.         if (s[i] == '*' || s[i] == '/')
  27.             if (!p) c2 = i;
  28.     }
  30.     // 找不到括号外的加减，就用乘除
  31.     if (c1 < 0) c1 = c2;
  32.     // 整个表达式被一对括号括起来，往里缩一位 
  33.     if (c1 < 0) return build_tree(s, x + 1, y - 1);
  35.     u = ++idx;
  36.     lch[u] = build_tree(s, x, c1);
  37.     rch[u] = build_tree(s, c1 + 1, y);
  38.     op[u] = s[c1];
  40.     return u;
  41. }
  43. void in_order(int u){
  44.     if (lch[u] == -1 && rch[u] == -1){
  45.         cout << op[u];
  46.         return ;
  47.     }
  49.     in_order(lch[u]);
  50.     cout << op[u];
  51.     in_order(rch[u]);
  52. }
  54. void pre_order(int u){
  55.     if (lch[u] == -1 && rch[u] == -1){
  56.         cout << op[u];
  57.         return ;
  58.     }
  60.     cout << op[u];
  61.     pre_order(lch[u]);
  62.     pre_order(rch[u]);
  63. }
  65. int main(){
  66.     scanf("%s", s);
  67.     root = build_tree(s, 0, strlen(s));
  69.     in_order(root);
  70.     puts("");
  71.     pre_order(root);
  73.     return 0;
  74. }
  76. /*
  77. a+b*(c-d)-e/f
  78. */

上述代码是如何寻找“最后一个运算符”的呢？代码用了一个变量p，只有当p=0时才考虑这个运算符。为什么呢？因为括号里的运算符一定不是最后计算的，应当忽略。例如，(a+b)*c中虽然有一个加号，但却是在括号里的，实际上比它优先级高的乘号才是最后计算的。由于加减和乘除号都是左结合的，最后一个运算符才是最后计算的，所以用两个变量c1和c2分别记录“最右”出现的加减号和乘除号。
再接下来的代码就不难理解了：如果括号外有加减号，它们肯定最后计算；但如果没有加减号，就需要考虑乘除号（if(c1 < 0) c1 = c2）；如果全都没有，说明整个表达式外面被一对括号括起来，把它去掉后递归调用。这样，就找到了最后计算的运算符s[c1]，它的左子树是区间[x, c1]，右子树是区间[c1+1, y]。