c/c++语言开发共享表达式·表达式树·表达式求值

描述

众所周知，任何一个表达式，都可以用一棵表达式树来表示。例如，表达式a+b*c，可以表示为如下的表达式树：
   +
  /  
 a    *
     /  
     b  c
现在，给你一个中缀表达式，这个中缀表达式用变量来表示（不含数字），请你将这个中缀表达式用表达式二叉树的形式输出出来。

输入

输入分为三个部分。
第一部分为一行，即中缀表达式(长度不大于50)。中缀表达式可能含有小写字母代表变量（a-z），也可能含有运算符（+、-、*、/、小括号），不含有数字，也不含有空格。
第二部分为一个整数n(n < 10)，表示中缀表达式的变量数。
第三部分有n行，每行格式为c　x，c为变量的字符，x为该变量的值。

输出

输出分为三个部分，第一个部分为该表达式的逆波兰式，即该表达式树的后根遍历结果。占一行。
第二部分为表达式树的显示，如样例输出所示。如果该二叉树是一棵满二叉树，则最底部的叶子结点，分别占据横坐标的第1、3、5、7……个位置（最左边的坐标是1），然后它们的父结点的横坐标，在两个子结点的中间。如果不是满二叉树，则没有结点的地方，用空格填充（但请略去所有的行末空格）。每一行父结点与子结点中隔开一行，用斜杠（/）与反斜杠（）来表示树的关系。/出现的横坐标位置为父结点的横坐标偏左一格，出现的横坐标位置为父结点的横坐标偏右一格。也就是说，如果树高为m，则输出就有2m-1行。
第三部分为一个整数，表示将值代入变量之后，该中缀表达式的值。需要注意的一点是，除法代表整除运算，即舍弃小数点后的部分。同时，测试数据保证不会出现除以0的现象。

样例输入

a+b*c
3
a 2
b 7
c 5

样例输出

abc*+
   +
  /  
 a    *
     /  
     b  c
37

中缀表达式生成二叉树

• 考虑没有括号的情况
  对于一个中缀表达式：(a+b),由运算符分为左右两个部分。其二叉树表示形式自然为：

所以，构建一个表达式树，关键在于找到表达式的根结点，然后分左右两个部分构建树；拓展到多个同级运算符的表达式：(a+b+c+…+n),可以这样构建其表达式树：

1. 找到最先运算的根结点,若以最右边的一个+为根结点
2. 以根结点分为左右两个部分
3. 构建根结点，左边构建树，右边构建树
4. 若左边部分又是一个表达式，执行1、2、3步骤
5. 若右边部分又是一个表达式，执行1、2、3步骤

这样就可以构建出整个表达式树：

• 考虑有不同优先级运算符的情况：
  (a+b*c)，因为+是最后运算，所以它一定是树的根，*先运算，是+号分得的右边部分的根，这样得到其表达式树：

所以，含有优先级不同的表达式，关键在于找到表达式最后运算的运算符，作为某个表达式树的根，然后分左右两个部分构建树；同样，同级运算符以最左边的运算符为最后运算的运算符，统一第一种情况：拓展到多个不同运算符出现的情况:(a+b*c p_1…p_k n(p_i为第i个运算符))

1. 找到最后运算的运算符作为根结点
2. 以根结点分为左右两个部分
3. 构建根结点，左边构建树，右边构建树
4. 若左边部分又是一个表达式，执行1、2、3步骤
5. 若右边部分又是一个表达式，执行1、2、3步骤

这样就可以构建出整个表达式树：

• 考虑存在括号的情况
  如果表达式中存在括号，最后运算的运算符一定在括号外，这样，需要一个变量记录括号位置，在括号外找到最后运算的运算符，然后分为左右两个部分，重复找括号，建树操作就可以了，以(a*b+(c+d))为例:

1. 找到最后运算的+号分左右两个部分：(a*b)和((c+d))
2. 左边部分建树
3. 右边部分建树：
   • 右边部分括号外找不到最后运算的运算符，说明整个表达式被括号括起来
   • 去掉括号：c+d 建树
4. 若左边部分又是一个表达式，执行1、2、3步骤
5. 若右边部分又是一个表达式，执行1、2、3步骤

所以，构建表达式树的函数:createexpressiontree(char *expression, int start, int end, bitree &tree)中，传入了表达式的开始下标和结尾下标，方便分割左边和右边部分：
createexpressiontree(char *expression, int start, int end, bitree &tree)函数：

void createexpressiontree(char *expression, int start, int end, bitree &tree) {     /**        * 这里，c1用来记录括号外最后运算的+或-       * c2用来记录括号外最后运算的+或-       * p记录括号当读到一个（ p++, ） 时 p--, 只有p==0时才说明c1, c2        * 括号外        */     int i, c1 = -1, c2 = -1, p = 0;      if (end - start == 1) {         //只有一个结点，直接建立结点         tree = new btnode;         tree->data = *(expression+start);         tree->left_child = tree->right_child = null;         return;     }     for (i = start; i < end; i++) {         switch (*(expression+i))         {         case '(': p++; break;         case ')': p--; break;         case '+': case '-': if (!p) c1 = i; break;         case '*': case '/': if (!p) c2 = i; break;         }     }     //c1 < 0，说明括号外没有第一优先级的+或者-，那么就只能考虑*或者/     if (c1 < 0) c1 = c2;          // 说明括号外没有第一优先级的*或者/，说明此时表达式被括号括起来, 去掉括号后建树     if (c1 < 0) createexpressiontree(expression,start+1,end-1,tree);     else {         //建立根         createexpressiontree(expression,c1,c1 + 1,tree);           //建立左树           createexpressiontree(expression,start,c1,tree->left_child);         //建立右树         createexpressiontree(expression,c1+1,end,tree->right_child);     } } 

对于建树这一部分，参考了,详细访问链接

打印表达式树

如题：

如果该二叉树是一棵满二叉树，则最底部的叶子结点，分别占据横坐标的第1、3、5、7……个位置（最左边的坐标是1），然后它们的父结点的横坐标，在两个子结点的中间。如果不是满二叉树，则没有结点的地方，用空格填充（但请略去所有的行末空格）。每一行父结点与子结点中隔开一行，用斜杠（/）与反斜杠（）来表示树的关系。/出现的横坐标位置为父结点的横坐标偏左一格，出现的横坐标位置为父结点的横坐标偏右一格。也就是说，如果树高为m，则输出就有2m-1行。

用一个graph[max_row][max_col] 数组保存表达式树的位置信息。以题例来看：
   +
  /  
 a    *
     /  
     b  c
首先，一共有(2^h-1)个结点,层层找结点位置，中间位置，即第(2^h-1)个结点+把该层分为两个部分，且左右部分皆是(2^h-2)长度(ps:因为包含了/的位置），如果有左结点，左结点就在(2^h-2)的中间部分，(ps:这里由于用到了(2^x)次方，在宏定义了一个pow(num) 1 << num, 1 << num 即右移num,即(2的num)次方)右结点也如此处理…这样，处理下一层时，也如同上一层处理:先处理根结点，在处理左右结点。在处理完根结点后下一层应该留给/，位置为中间位置左偏一个或右偏一个；

void print(bitree root, int row, int col, int len) {    if (root == null) return;     graph[row][col-1] = root->data;     //当前层中间位置     if (root->left_child!=null) {         graph[row+1][col-2] = '/';      //下一层留给/，中间位置偏左一个         print(root->left_child,row+2,col-len,len>>1); // 左边部分     }     if (root->right_child!=null) {         graph[row+1][col] = '\';         print(root->right_child,row+2,col+len,len>>1);     } } 

对于打印表达式树这一部分，参考了,详细访问链接

计算部分

对于这一部分，由于已经有了表达式树了，只需要一层层求解即可:

1. 如果结点是运算符,将左树和右树的计算结果和根运算
2. 如果结点不是运算符，直接返回变量值
   其中左树和右树的计算结果就是一个递归过程，反复执行1、2步；

这一部分由于要用到变量的值， 使用了 map<char,int> to_value的一个映射,给一个结点变量，对应一个变量值

对于计算部分，参考了,详细访问链接

其它

其他部分根据题意求解即可,关于表达式输入，使用了一个char*指针，但是我在这个地方初始化 expression = new char [52];一开始记成 expression = new char （52）;导致一直不能过…

完整代码

/* @file     :   expression_tree.cpp @time     :   2020/04/27 @desc     :   表达式·表达式树·表达式求值 */ #include <iostream> #include <stdlib.h> #include <string.h> #include <math.h> #include <map> #define pow(num) 1<<num #define max_row 70 #define max_col 300  using namespace std;  typedef struct btnode {     char data;     struct btnode *left_child;     struct btnode *right_child; }*bitree; char graph[max_row][max_col]; map <char,int> to_value; void createexpressiontree(char *expression, int start, int end, bitree &tree) {     int i, c1 = -1, c2 = -1, p = 0;     if (end - start == 1) {         tree = new btnode;         tree->data = *(expression+start);         tree->left_child = tree->right_child = null;         return;     }     for (i = start; i < end; i++) {         switch (*(expression+i))         {         case '(': p++; break;         case ')': p--; break;         case '+': case '-': if (!p) c1 = i; break;         case '*': case '/': if (!p) c2 = i; break;         }     }     if (c1 < 0) c1 = c2;     if (c1 < 0) createexpressiontree(expression,start+1,end-1,tree);     else {         createexpressiontree(expression,c1,c1 + 1,tree);         createexpressiontree(expression,start,c1,tree->left_child);         createexpressiontree(expression,c1+1,end,tree->right_child);     } } void postorder(bitree tree) {     if (tree == null) return;     postorder(tree->left_child);     postorder(tree->right_child);     cout << tree->data; } int getheight(bitree tree) {     int left_height, right_height;     if (tree == null) return 0;     else {         left_height = getheight(tree->left_child);         right_height = getheight(tree->right_child);         return (left_height > right_height)?(left_height+1):(right_height+1);     }   } void print(bitree root, int row, int col, int len) {    if (root == null) return;     graph[row][col-1] = root->data;     if (root->left_child!=null) {         graph[row+1][col-2] = '/';         print(root->left_child,row+2,col-len,len>>1);     }     if (root->right_child!=null) {         graph[row+1][col] = '\';         print(root->right_child,row+2,col+len,len>>1);     } } int calculate(bitree tree) {     switch (tree->data)      {     case '+':         return calculate(tree->left_child) + calculate (tree->right_child);         break;     case '-':         return calculate(tree->left_child) - calculate (tree->right_child);         break;     case '*':         return calculate(tree->left_child) * calculate (tree->right_child);         break;     case '/':         return calculate(tree->left_child) / calculate (tree->right_child);         break;     default:         return to_value[tree->data];         break;     } } int main(int argc, char const *argv[]) {     int n, value;     char *expression, valuable;     bitree tree;     // expression = (char*)malloc(sizeof(char)*52);     // expression = new char(52); !!!!!     expression = new char[52];     cin >> expression;     cin >> n;     while (n--) {         cin >> valuable >> value;         to_value[valuable] = value;     }     createexpressiontree(expression,0,strlen(expression),tree);      postorder(tree); cout << endl;     memset(graph,' ',sizeof(graph));     print(tree,0,pow(getheight(tree)-1),pow(getheight(tree)-2));      int j = 0, l = 0;     for (int i = 0; i < max_row; ++i) {         j = max_col - 1;         while (j >= 0 && graph[i][j] == ' ') --j;         if (j > -1) {             ++l;             graph[i][j+1] = '';         }         else break;     }     for (int i = 0; i < l; ++i) cout << graph[i] << endl;     cout << calculate(tree) << endl;     system("pause");     return 0; }