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

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

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

众所周知,任何一个表达式,都可以用一棵表达式树来表示。例如,表达式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">//青少年考级竞赛题库(tiku.scratchor.com)搜集整理,感谢网友提供代码! #include&lt;iostream&gt; #include&lt;string&gt; #include &lt;cstring&gt; #include&lt;cmath&gt; #include&lt;stack&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><p><br/></p>
这道题暂未补解析。