首页 › 题库 › C/C++编程考级 › C/C++编程七级 › 简答题
简答题 偏难
#7353

表达式· 表达式树· 表达式求值 众所周知, 任何一个表达式, 都可以用一棵表达式树来表示。 例如, 表达式 a+b*c, 可以表示为如下的表达式树: + /…

表达式· 表达式树· 表达式求值

众所周知, 任何一个表达式, 都可以用一棵表达式树来表示。 例如,

表达式 a+b*c, 可以表示为如下的表达式树:

+

/ \

a *

/ \

 b c

现在, 给你一个中缀表达式, 这个中缀表达式用变量来表示(不含数字), 请你将这个中缀表达式用表达式二叉树的形式输出出来。

时间限制: 1000

内存限制: 65535

输入

输入分为三个部分。 第一部分为一行,即中缀表达式(长度不大于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
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;cmath&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;stack&gt; #include &lt;string&gt; #define OK 1 #define ERROR 0 #define MAXSIZE 50 using namespace std; struct number {   char ch;   int value; }; number a[10]; // 定义二叉树类型 typedef struct BiNode {   char date;   struct BiNode *lchild, *rchild; } BiNode; // 定义栈类型 typedef struct SqStack {   char *base;   char *top;   int stacksize; } SqStack; // 初始化栈 int InitStack(SqStack &amp;S) {   S.base = new char[MAXSIZE];   if (!S.base)     exit(ERROR);   S.top = S.base;   S.stacksize = MAXSIZE;   return OK; } // 出栈 char Pop(SqStack &amp;S) {   if (S.top == S.base)     return ERROR;   char e = *(--S.top);   return e; } // 入栈 int Push(SqStack &amp;S, char e) {   if (S.top - S.base == S.stacksize)     return ERROR;   *(S.top++) = e;   return OK; } // 将中缀表达式转化为后缀表达式 string Change(string str) {   // str为中缀表达式,str2为后缀表达式   string str2 = "";   char ch, e; // e用于保存栈中弹出的元素   SqStack S1; // S1用于存放操作符(为辅助栈),S用于存放后续表达式   InitStack(S1);   for (int i = 0; i &lt; str.size(); i++) {     ch = str[i];     if (ch &gt;= 'a' &amp;&amp; ch &lt;= 'z') {       str2 += ch;     }     if (ch == '(')       Push(S1, ch);     if (ch == ')') {       while (*(S1.top - 1) != '(') {         e = Pop(S1);         str2 += e;       }       Pop(S1); // 左括号出栈但不入S2栈中     }     // 遇到+或-时     // 栈空/栈顶为左括号:直接入栈     // 否则一直出栈,直到栈空/栈顶为左括号,再入栈     if (ch == '+' || ch == '-') {       while (*(S1.top - 1) != '(' &amp;&amp; S1.base != S1.top) {         e = Pop(S1);         str2 += e;       }       Push(S1, ch);     }     // 遇到*或/时     // 栈空/栈顶为左括号/栈顶操作符为+ or -:直接入栈     // 否则一直出栈,直到满足上述条件,再入栈     if (ch == '*' || ch == '/') {       while (S1.base != S1.top &amp;&amp; *(S1.top - 1) != '(' &amp;&amp;              *(S1.top - 1) != '-' &amp;&amp; *(S1.top - 1) != '+') {         e = Pop(S1);         str2 += e;       }       Push(S1, ch);     }   }   // 中缀表达式遍历完成,还需检查栈中是否有未输出字符   // 判断栈空,非空则直接出栈   while (S1.base != S1.top) {     e = Pop(S1);     if (e != '(')       str2 += e;   }   return str2; } struct BiNode *s[MAXSIZE]; // 定义栈,该栈用于存放树 int top = -1; // 建立二叉树 BiNode *CreatTree(string str) {   // str为后缀表达式   BiNode *T, *T2;   SqStack S;   BiNode *e1, *e2;   int i;   InitStack(S);   for (i = 0; i &lt; str.size() - 1; i++) {     if (str[i] &gt;= 'a' &amp;&amp; str[i] &lt;= 'z') {       T = new BiNode;       T-&gt;date = str[i];       T-&gt;lchild = T-&gt;rchild = NULL;       s[++top] = T;     } else {       T = new BiNode;       T-&gt;date = str[i];       e1 = s[top--];       e2 = s[top--];       T-&gt;lchild = e2;       T-&gt;rchild = e1;       s[++top] = T;     }   }   T = new BiNode;   T-&gt;date = str[i];   T-&gt;rchild = s[top--];   T-&gt;lchild = s[top--];   s[++top] = T;   T2 = new BiNode;   T2 = s[top];   return T2; } int Seek(char e, int n) {   for (int i = 0; i &lt; n; i++) {     if (a[i].ch == e)       return a[i].value;   } } int Count(string str, int n) {   // str为后缀表达式数组,n变量个数   int sum = 0;   stack&lt;int&gt; S;   int x, x1, x2;   for (int i = 0; i &lt; n; i++) {     cin &gt;&gt; a[i].ch &gt;&gt; a[i].value;   }   for (int i = 0; i &lt; str.size(); i++) {     if (str[i] &gt;= 'a' &amp;&amp; str[i] &lt;= 'z') {       x = Seek(str[i], n);       S.push(x);     } else {       x2 = S.top();       S.pop(); // 左操作数       x1 = S.top();       S.pop(); // 右操作数       switch (str[i]) {       case '+':         sum = x1 + x2;         break;       case '-':         sum = x1 - x2;         break;       case '*':         sum = x1 * x2;         break;       case '/':         sum = x1 / x2;         break;       }       S.push(sum);     }   }   sum = S.top();   return sum; } char arr[1000][1000]; // 打印二叉树 void PrintTree(int tag, BiNode *T, int x, int m, int y) {   arr[2 * tag - 1][(x + m) / 2] = T-&gt;date;   if (tag != 1) {     if (y == 1)       arr[2 * tag - 2][m] = '/';     else       arr[2 * tag - 2][x] = '\\';   }   if (T-&gt;lchild != NULL)     PrintTree(tag + 1, T-&gt;lchild, x, (x + m) / 2 - 1, 1);   if (T-&gt;rchild != NULL)     PrintTree(tag + 1, T-&gt;rchild, (x + m) / 2 + 1, m, 0); } // 计算二叉树的深度 int Depth(BiNode *T) {   int m, n;   if (T == NULL)     return 0;   else {     m = Depth(T-&gt;lchild);     n = Depth(T-&gt;rchild);     if (m &gt; n)       return (m + 1);     else       return (n + 1);   } } bool Judge(int i, int j, int n) {   for (int k = j + 1; k &lt;= n; k++) {     if (arr[i][k] != ' ')       return 1;   }   return 0; } int main() {   string str1; // 中序表达式   cin &gt;&gt; str1;   int n; // 变量个数   cin &gt;&gt; n;   string str2 = Change(str1); // str2为后序表达式   BiNode *T = CreatTree(str2);   int sum = Count(str2, n);   int dp = Depth(T);   cout &lt;&lt; str2 &lt;&lt; endl;   memset(arr, ' ', sizeof(arr));   PrintTree(1, T, 1, pow(2.0, dp) - 1, 0);   for (int i = 1; i &lt;= 2 * dp - 1; i++) {     for (int j = 1; j &lt;= pow(2.0, dp) - 1; j++) {       cout &lt;&lt; arr[i][j];       if (arr[i][j] != ' ') {         if (Judge(i, j, pow(2.0, dp) - 1))           continue;         else           break;       }     }     cout &lt;&lt; endl;   }   cout &lt;&lt; sum &lt;&lt; endl;   return 0; }</pre>
这道题暂未补解析。