首页 › 题库 › Scratch编程考级 › 1.4 新建保存与语言选择

Scratch编程一级 题库

共 29 道题 ,第 2 / 2 页 · 按题型筛选,点「查看答案」核对解析
章节 1.4 新建保存与语言选择 清除
21 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.4 新建保存与语言选择

圣诞老人的礼物

圣诞节来临了,在城市A中圣诞老人准备分发糖果,现在有多箱不同的糖果,每箱糖果有自己的价值和重量,每箱糖果都可以拆分成任意散装组合带走。圣诞老人的驯鹿最多只能承受一定重量的糖果,请问圣诞老人最多能带走多大价值的糖果。

时间限制:1000

内存限制:65536

输入

第一行由两个部分组成,分别为糖果箱数正整数n(1 = n = 100),驯鹿能承受的最大重量正整数w(0<w<10000),两个数用空格隔开。其余n行每行对应一箱糖果,由两部分组成,分别为一箱糖果的价值正整数v和重量正整数w,中间用空格隔开。

输出

输出圣诞老人能带走的糖果的最大总价值,保留1位小数。输出为一行,以换行符结束。

样例输入

4 15
100 4
412 8
266 7
591 2

样例输出

1193.0
答案与解析
参考答案
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;
struct gift {
  int value;
  int weight;
  double density;
} gf[101];
bool cmp(gift f1, gift f2) { // 按照单重价值从大到小排序
  return f1.density > f2.density;
}
int main() {
  int n, w;
  cin >> n >> w;
  for (int i = 0; i < n; i++) {
    cin >> gf[i].value >> gf[i].weight;
    gf[i].density = 1.0 * gf[i].value / gf[i].weight;
  }
  sort(gf, gf + n, cmp);
  double totw = 0, totv = 0; // 注意到w为int型,可拆分为double型
  // 所以新建一个double型保存背包剩余重量
  for (int i = 0; i < n; i++) {
    if (totw + gf[i].weight <= w) {
      totw += gf[i].weight;
      totv += gf[i].value;
    } else {
      totv += gf[i].density * (w - totw);
      totw = w;
      break;
    }
  }
  printf("%.1lf", totv);
  return 0;
}
题目详情
22 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.4 新建保存与语言选择

中缀表达式的值

人们熟悉的四则运算表达式称为中缀表达式,例如(23+34*45/(5+6+7))。在程序设计语言中,可以利用堆栈的方法把中缀表达式转换成保值的后缀表达式(又称逆波兰表示法),并最终变为计算机可以直接执行的指令,得到表达式的值。 给定一个中缀表达式,编写程序,利用堆栈的方法,计算表达式的值。

时间限制:200

内存限制:65536

输入

第一行为测试数据的组数N 接下来的N行,每行是一个中缀表达式。表达式中只含数字、四则运算符和圆括号,操作数都是正整数,数和运算符、括号之间没有空格。中缀表达式的字符串长度不超过600。

输出

对每一组测试数据输出一行,为表达式的值

样例输入

3
3+5*8
(3+5)*8
(23+34*45/(5+6+7))

样例输出

43
64
108

提示

注意:运算过程均为整数运算(除法运算'/'即按照C++定义的int除以int的结果,测试数据不会出现除数为0的情况),输出结果也为整数(可能为负)。 中间计算结果可能为负。

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int get_fast(string op) // 运算符的优先级
{
  int ans = -1;
  switch (op[0]) {
  case '+':
  case '-':
    ans = 1;
    break;
  case '*':
  case '/':
    ans = 2;
    break;
  case '^':
    ans = 3;
    break;
  }
  return ans;
}
vector<string> scaner(string s) // 字符串拆解放入vector
{
  vector<string> ans;
  string ops = "+-*/^()";
  string t = "";
  for (int i = 0; i < s.size(); i++) {
    if (s[i] >= '0' && s[i] <= '9')
      t += s[i];
    else if (ops.find(s[i]) != string::npos) {
      if (t.size() > 0)
        ans.push_back(t);
      t = s[i];
      ans.push_back(t);
      t = "";
    }
  }
  if (t.size())
    ans.push_back(t);
  return ans;
}
vector<string> infix_Suffix(vector<string> exp) // 中缀表达式转后缀表达式
{
  vector<string> ans;
  stack<string> st;
  string op = "+-*/^()";
  for (int i = 0; i < exp.size(); i++) {
    if (exp[i] == "(")
      st.push(exp[i]);
    else if (exp[i] == ")") {
      while (st.top() != "(") {
        ans.push_back(st.top());
        st.pop();
      }
      st.pop();
    } else if (op.find(exp[i]) != string::npos) {
      while (st.size() && get_fast(exp[i]) <= get_fast(st.top())) {
        ans.push_back(st.top());
        st.pop();
      }
      st.push(exp[i]);
    } else
      ans.push_back(exp[i]);
  }
  while (st.size()) {
    ans.push_back(st.top());
    st.pop();
  }
  return ans;
}
int suffix_calc(vector<string> exp) // 后缀表达式计算结果
{
  stack<int> num;
  string ops = "+-*/^";
  for (int i = 0; i < exp.size(); i++) {
    if (ops.find(exp[i]) != string::npos) {
      int a = num.top();
      num.pop();
      int b = num.top();
      num.pop();
      if (exp[i] == "+")
        num.push(b + a);
      else if (exp[i] == "-")
        num.push(b - a);
      else if (exp[i] == "*")
        num.push(b * a);
      else if (exp[i] == "/")
        num.push(b / a);
      else if (exp[i] == "^")
        num.push(pow(b * 1.0, a));
    } else
      num.push(atoi(exp[i].c_str()));
  }
  cout << num.top() << endl;
  return num.top();
}
int main() {
  string s;
  int n;
  cin >> n;
  while (n--) {
    cin >> s;
    vector<string> vs = scaner(s);
    vs = infix_Suffix(vs);
    suffix_calc(vs);
  }
  return 0;
}
题目详情
23 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.4 新建保存与语言选择

合法C标识符

给定一个不包含空白符的字符串,请判断是否是C语言合法的标识符号(注:题目保证这些字符串一定不是C语言的保留字)。

C语言标识符要求:

1. 非保留字;

2. 只包含字母、数字及下划线(“_”)。

3. 不以数字开头。

时间限制:1000

内存限制:65536

输入

一行,包含一个字符串,字符串中不包含任何空白字符,且长度不大于20。

输出

一行,如果它是C语言的合法标识符,则输出yes,否则输出no。

样例输入

RKPEGX9R;TWyYcp

样例输出

no
答案与解析
参考答案
#include <iostream>
using namespace std;
int main() {
  string str;
  cin >> str;
  if (str[0] >= '0' && str[0] <= '9') {
    cout << "no" << endl;
    return 0;
  }
  for (int i = 0; i < str.length(); i++) {
    if (!((str[i] >= '0' && str[i] <= '9') ||
          (str[i] >= 'A' && str[i] <= 'Z') ||
          (str[i] >= 'a' && str[i] <= 'z') || str[i] == '_')) {
      cout << "no" << endl;
      return 0;
    }
  }
  cout << "yes" << endl;
  return 0;
}
题目详情
24 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.4 新建保存与语言选择

拨钟问题

有9个时钟,排成一个3*3的矩阵。

现在需要用最少的移动,将9个时钟的指针都拨到12点的位置。共允许有9种不同的移动。如下表所示,每个移动会将若干个时钟的指针沿顺时针方向拨动90度。

移动 影响的时钟

1 ABDE

2 ABC

3 BCEF

4 ADG

5 BDEFH

6 CFI

7 DEGH

8 GHI

9 EFHI

输入格式

9个整数,表示各时钟指针的起始位置,相邻两个整数之间用单个空格隔开。其中,0=12点、1=3点、2=6点、3=9点。

输出格式

输出一个最短的移动序列,使得9个时钟的指针都指向12点。按照移动的序号从小到大输出结果。相邻两个整数之间用单个空格隔开。(数据保证答案唯一)

样例输入

3 3 0 
2 2 2 
2 1 2

样例输出

4 5 8 9
答案与解析
参考答案
/*
9个操作,每个操作最多做3次
因为超过3次之后就回到原位置了。
所以可以9个for循环枚举每个操作
设置i[10]数组,i[1]~i[9]代表1到9这个操作
A始终受操作1,2,4的影响
时钟初始保存在数组mp[9]里
那么mp[1]的变化就是mp[1]+i[1]+i[2]+i[4]在对4取余
其余时钟变化也可以顺势表示出来
全部加起来求和如果等于0就全部归位了
全部等于0只能是9个0加起来没有别的情况因为不存在负数
*/
#include <bits/stdc++.h>
using namespace std;
int n, mp[10], i[10];
int main() {
  for (int i = 1; i <= 9; i++) {
    cin >> mp[i];
  }
  for (i[1] = 0; i[1] < 4; i[1]++) {
    for (i[2] = 0; i[2] < 4; i[2]++) {
      for (i[3] = 0; i[3] < 4; i[3]++) {
        for (i[4] = 0; i[4] < 4; i[4]++) {
          for (i[5] = 0; i[5] < 4; i[5]++) {
            for (i[6] = 0; i[6] < 4; i[6]++) {
              for (i[7] = 0; i[7] < 4; i[7]++) {
                for (i[8] = 0; i[8] < 4; i[8]++) {
                  for (i[9] = 0; i[9] < 4; i[9]++) {
                    int sum = 0;
                    sum += (mp[1] + i[1] + i[2] + i[4]) %
                           4; // 时钟A受操作1和2和4的影响其余同理
                    sum += (mp[2] + i[1] + i[2] + i[3] + i[5]) % 4;
                    sum += (mp[3] + i[2] + i[3] + i[6]) % 4;
                    sum += (mp[4] + i[1] + i[4] + i[5] + i[7]) % 4;
                    sum += (mp[5] + i[1] + i[3] + i[5] + i[7] + i[9]) % 4;
                    sum += (mp[6] + i[3] + i[5] + i[6] + i[9]) % 4;
                    sum += (mp[7] + i[4] + i[7] + i[8]) % 4;
                    sum += (mp[8] + i[5] + i[7] + i[8] + i[9]) % 4;
                    sum += (mp[9] + i[6] + i[8] + i[9]) % 4;
                    if (sum == 0) {
                      for (int x = 1; x <= 9; x++) {
                        while (i[x]--)
                          cout << x << " ";
                      }
                      return 0;
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }
  return 0;
}
题目详情
25 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.4 新建保存与语言选择

广义格雷码

在一组数的编码中,若任意两个相邻(首尾也视为相邻)的代码只有一位二进制数不同,则称这种编码为格雷码。如四位格雷码:

0000、0001、0011、0010、0110、0111、0101、0100、1100、1101、1111、1110、1010、1011、1001、1000

现在将格雷码扩展至其他进制,仍然是相邻两个数只能有一位不同。输入两个正整数n,m分别表示长度和进制,每行输出一个n位m进制数,输出任意一种编码即可。(提示:putchar输出效率更高)

时间限制:1000

内存限制:65536

输入

一行,两个整数n,m。其中 2 ≤ n ≤ 12 ,2 ≤ m ≤ 10 且mn ≤ 500000

输出

任意一种编码方案,每个编码一行。相邻两个编码相差一位。第一个编码和最后一个编码算相邻

样例输入

2 3

样例输出

00
10
20
21
01
11
12
22
02
答案与解析
参考答案
//答案仅供参考,来源于csdn,有部分错误 
#include <cstring> //memset(flag,0,sizeof(bool)*12*50010);
#include <iostream>
#include <queue>

using namespace std;
string a[12][50010];
bool flag[12][50010];
queue<string> q;
int n, m;
int main() {
  cin >> n >> m;
  string temp = "";
  // n为1的时候
  if (n == 1) {
    for (int i = 0; i < m; i++) {
      cout << i << endl;
    }
    return 0;
  }
  // n大于2的时候
  for (int i = 0; i < m; i++) {
    //      cout<<(temp+char(i+48))<<endl;
    q.push(temp + char(i + 48)); // i=0,把字符0入队
  }
  for (int time = 2; time <= n; time++) {
    memset(flag, 0, sizeof(bool) * 12 * 50010);
    int size = q.size(), l = 0; // l这里赋值0  因为要从1开始
    while (!q.empty()) {
      a[0][++l] = q.front();
      //      cout<<a[0][l]<<" ";
      q.pop();
    }
    // 复制一份 其他行数的
    for (int i = 1; i < m; i++) {
      for (int j = 1; j <= size; j++) {
        a[i][j] = a[0][j];
      }
    }
    // 添加前面一个值: 0—(m-1)
    for (int i = 0; i < m; i++) {
      for (int j = 1; j <= size; j++) {
        a[i][j] = char(i + 48) + a[i][j];
        //        cout<<a[i][j]<<" ";
        flag[i][j] = true;
      }
      //      cout<<endl;
    }
    // 蛇形取值
    int t = size * m; // t表示当前总个数
    // 保存第一行到q队列中
    for (int i = 1; i <= size; i++) {
      q.push(a[0][i]);
      flag[0][i] = false;
      t--;
    }
    //    cout<<q.size()<<endl;
    int x = 0, y = size;
    while (t > 0) {
      while (flag[x + 1][y] && t > 0) {
        flag[++x][y] = false;
        q.push(a[x][y]);
        t--;
      } // 向下

      if (flag[x][y - 1] && t > 0) {
        flag[x][--y] = false;
        q.push(a[x][y]);
        t--;
      } // 向左一位

      while (flag[x - 1][y] && t > 0) {
        flag[--x][y] = false;
        q.push(a[x][y]);
        t--;
      } // 向上

      if (flag[x][y - 1] && t > 0) {
        flag[x][--y] = false;
        q.push(a[x][y]);
        t--;
      } // 再向左一位
    }
  }
  // 输出
  while (!q.empty()) {
    cout << q.front() << endl;
    q.pop();
  }
  return 0;
}
题目详情
26 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.4 新建保存与语言选择

扑克牌排序

假设这里有36张扑克牌,分别为A1~A9,B1~B9,C1~C9,D1~D9,其中A代表方片,B代表草花,C代表红桃,D代表黑桃,那么,设定如下的排序规则:

1.对于两张卡牌,X1Y1与X2Y2,X1与X2表示A~D,Y1与Y2表示1~9,如果X1与X2不同,那么依照D>C>B>A的方式进行排序

2.假如有X1与X2相同时,那么就比较Y1与Y2的大小。

例如,对于如下的四张牌,有如下的升序排序结果:

D3,C4,A4,C1

升序排序的结果为A4,C1,C4,D3

有人提出了如下的排序策略:

先建立9个队列,用于存放点数的大小,将卡牌依点数存放入各自的队列之中,然后再按队列1到队列9依次出队。

例如,对于上面的结果,依次进队后,结果如下:

队列1:C1;队列3:D3,队列4:C4,A4

将其依次出队后,结果为C1,D3,C4,A4

然后,再建立4个队列,用于存放花色。将卡牌依花色A~D存放入队列1~4中,然后再按队列1到队列4依次出队。

例如,对于上面刚刚出队的序列C1,D3,C4,A4,将其依次进队,结果如下:

队列1:A4;队列3:C1,C4;队列4:D3

将其依次出队后,结果为A4,C1,C4,D3,排序结束。

请根据上面的算法,编写一个用队列对扑克牌排序的程序,要求依照上面的排序规则,根据先花色后点数的方法进行排序。

时间限制:1000

内存限制:65536

输入

输入分为两行,第一行为一个整数n,表示一共有n张牌(1<=n<=100) 第二行用XY的形式表示每一张牌,其中X为A~D,Y为1~9

输出

输出三个部分 第一个部分为第一次进队出队的结果,用Queue1:...表示,共9行,结果用空格分隔,下同 第二部分为第二次进队出队的结果,用QueueA:...表示,共4行 第三部分为一行,即将卡牌排序后的结果(升序排序)

样例输入

8
D8 A6 C3 B8 C5 A1 B5 D3

样例输出

Queue1:A1
Queue2:
Queue3:C3 D3
Queue4:
Queue5:C5 B5
Queue6:A6
Queue7:
Queue8:D8 B8
Queue9:
QueueA:A1 A6
QueueB:B5 B8
QueueC:C3 C5
QueueD:D3 D8
A1 A6 B5 B8 C3 C5 D3 D8

提示

第二次入队出队时,可以复用第一次时9个队列中的4个。所以其实只需要开辟9个队列即可。

答案与解析
参考答案
#include <iostream>
#include <queue>
#include <string>

using namespace std;
int main() {
  int n = 0;
  cin >> n;
  queue<string> q1[10], q2[4]; // 分别按照大小和花色存放扑克
  string *strs = new string[n];
  string newstr[10000];

  for (int i = 0; i < n; i++) {
    cin >> strs[i];
    q1[strs[i][1] - '1'].push(strs[i]); // 按照大小入队q1
  }

  for (int i = 0; i < n; i++) // 输出q1队列,从小到大
  {
    cout << "Queue" << i + 1 << ":";
    while (!q1[i].empty()) {
      cout << q1[i].front() << " ";
      q2[q1[i].front()[0] - 'A'].push(q1[i].front()); // 按照花色入队q2
      q1[i].pop();
    }
    cout << endl;
  }

  int c = 0;
  for (int i = 0; i < 4; i++) // 输出q2队列,按照花色
  {
    char t;
    t = (char)i + 'A';
    cout << "Queue" << t << ":"; // i+'A'做类型转换
    while (!q2[i].empty()) {
      cout << q2[i].front() << " ";
      newstr[c++] = q2[i].front(); // 将队列q2中的string保存到newstr中
      q2[i].pop();
    }
    cout << endl;
  }

  for (int i = 0; i < c; i++) // 输出升序排序后的卡牌
    cout << newstr[i] << " ";
  cout << endl;
  return 0;
}
题目详情
27 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.4 新建保存与语言选择

词典

你旅游到了一个国外的城市。那里的人们说的外国语言你不能理解。不过幸运的是,你有一本词典可以帮助你。

时间限制:3000

内存限制:65536

输入

首先输入一个词典,词典中包含不超过100000个词条,每个词条占据一行。每一个词条包括一个英文单词和一个外语单词,两个单词之间用一个空格隔开。而且在词典中不会有某个外语单词出现超过两次。词典之后是一个空行,然后给出一个由外语单词组成的文档,文档不超过100000行,而且每行只包括一个外语单词。输入中出现单词只包括小写字母,而且长度不会超过10。

输出

在输出中,你需要把输入文档翻译成英文,每行输出一个英文单词。如果某个外语单词不在词典中,就把这个单词翻译成“eh”。

样例输入

dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay

atcay
ittenkay
oopslay

样例输出

cat
eh
loops

提示

输入比较大,推荐使用C语言的I / O函数。

答案与解析
参考答案
#include <algorithm>
#include <stdio.h>
#include <string.h>

#define MAXSTR 11
#define MAXWORD 100010
using namespace std;
typedef struct {
  char foreign[MAXSTR];
  char english[MAXSTR];
} m_word;
m_word m_dic[MAXWORD];
int compare(const void *elem1, const void *elem2) {
  return strcmp(((m_word *)elem1)->foreign, ((m_word *)elem2)->foreign);
}
int main() {
  int count = 0;

  char chs[30];
  while (fgets(chs, 29, stdin), chs[0] != '\n') {
    sscanf(chs, "%s%s", m_dic[count].english, m_dic[count].foreign);
    count++;
  }
  qsort(m_dic, count, sizeof(m_word), compare);
  m_word tmp;
  m_word *ans;
  while (scanf("%s", tmp.foreign) != EOF) {
    ans = (m_word *)bsearch(&tmp, m_dic, count, sizeof(m_word), compare);
    if (ans != NULL)
      printf("%s\n", ans->english);
    else
      printf("eh\n");
  }
  return 0;
}
题目详情
28 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.4 新建保存与语言选择

滑雪

Michael喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上,这是最长的一条。

时间限制:1000

内存限制:65536

输入

输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行,每行有C个整数,代表高度h,0<=h<=10000。

输出

输出最长区域的长度。

样例输入

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

样例输出

25
答案与解析
参考答案
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
// 控制方向的常用方法
int n, m, a[205][205], s[205][205], ans;
int dfs(int x, int y) {
  if (s[x][y])
    return s[x][y];
  s[x][y] = 1; // 自身算一个距离
  for (int i = 0; i < 4; i++) {
    int tx = dx[i] + x, ty = dy[i] + y;
    if (tx > 0 && tx <= n && ty >= 1 && ty <= m && a[x][y] > a[tx][ty]) {
      dfs(tx, ty);
      s[x][y] = max(s[x][y], s[tx][ty] + 1);
      // 记忆化
    }
  }
  return s[x][y];
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      scanf("%d", &a[i][j]);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      ans = max(ans, dfs(i, j)); // 将每个点当成起点做dfs
  printf("%d", ans);
  return 0;
}

解题思路

采用递推的动态规划方式求解

先用结构体保存每个点对应的原本坐标位置和高度;

将所有点按高度从小到大排序;

用一个二维数组保存输入的原本数据,

再用一个二维数组保存对应位置的最大滑行距离;

从第二个点开始求解(因为第一个点高度最低,显然滑行距离为1)

依次和它在原本坐标里的上下左右四个方向进行判断,

如果它比某一方向上的高度高,则它的滑行距离就应该是相比较的最大滑行距离+1和它保存的最大滑行距离中的最大值。

最后求完总共的点,进行遍历,得到最终最大值。

题目详情
29 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.4 新建保存与语言选择

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

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

表达式 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
答案与解析
参考答案
#include <cmath>
#include <cstring>
#include <iostream>
#include <stack>
#include <string>

#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 &S) {
  S.base = new char[MAXSIZE];
  if (!S.base)
    exit(ERROR);
  S.top = S.base;
  S.stacksize = MAXSIZE;
  return OK;
}

// 出栈
char Pop(SqStack &S) {
  if (S.top == S.base)
    return ERROR;
  char e = *(--S.top);
  return e;
}

// 入栈
int Push(SqStack &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 < str.size(); i++) {
    ch = str[i];
    if (ch >= 'a' && ch <= '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) != '(' && S1.base != S1.top) {
        e = Pop(S1);
        str2 += e;
      }
      Push(S1, ch);
    }
    // 遇到*或/时
    // 栈空/栈顶为左括号/栈顶操作符为+ or -:直接入栈
    // 否则一直出栈,直到满足上述条件,再入栈
    if (ch == '*' || ch == '/') {
      while (S1.base != S1.top && *(S1.top - 1) != '(' &&
             *(S1.top - 1) != '-' && *(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 < str.size() - 1; i++) {
    if (str[i] >= 'a' && str[i] <= 'z') {
      T = new BiNode;
      T->date = str[i];
      T->lchild = T->rchild = NULL;
      s[++top] = T;
    } else {
      T = new BiNode;
      T->date = str[i];
      e1 = s[top--];
      e2 = s[top--];
      T->lchild = e2;
      T->rchild = e1;
      s[++top] = T;
    }
  }
  T = new BiNode;
  T->date = str[i];
  T->rchild = s[top--];
  T->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 < n; i++) {
    if (a[i].ch == e)
      return a[i].value;
  }
}

int Count(string str, int n) {
  // str为后缀表达式数组,n变量个数
  int sum = 0;
  stack<int> S;
  int x, x1, x2;
  for (int i = 0; i < n; i++) {
    cin >> a[i].ch >> a[i].value;
  }
  for (int i = 0; i < str.size(); i++) {
    if (str[i] >= 'a' && str[i] <= '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->date;
  if (tag != 1) {
    if (y == 1)
      arr[2 * tag - 2][m] = '/';
    else
      arr[2 * tag - 2][x] = '\\';
  }
  if (T->lchild != NULL)
    PrintTree(tag + 1, T->lchild, x, (x + m) / 2 - 1, 1);
  if (T->rchild != NULL)
    PrintTree(tag + 1, T->rchild, (x + m) / 2 + 1, m, 0);
}

// 计算二叉树的深度
int Depth(BiNode *T) {
  int m, n;
  if (T == NULL)
    return 0;
  else {
    m = Depth(T->lchild);
    n = Depth(T->rchild);
    if (m > n)
      return (m + 1);
    else
      return (n + 1);
  }
}

bool Judge(int i, int j, int n) {
  for (int k = j + 1; k <= n; k++) {
    if (arr[i][k] != ' ')
      return 1;
  }
  return 0;
}

int main() {
  string str1; // 中序表达式
  cin >> str1;
  int n; // 变量个数
  cin >> n;
  string str2 = Change(str1); // str2为后序表达式
  BiNode *T = CreatTree(str2);
  int sum = Count(str2, n);
  int dp = Depth(T);
  cout << str2 << endl;
  memset(arr, ' ', sizeof(arr));
  PrintTree(1, T, 1, pow(2.0, dp) - 1, 0);
  for (int i = 1; i <= 2 * dp - 1; i++) {
    for (int j = 1; j <= pow(2.0, dp) - 1; j++) {
      cout << arr[i][j];
      if (arr[i][j] != ' ') {
        if (Judge(i, j, pow(2.0, dp) - 1))
          continue;
        else
          break;
      }
    }
    cout << endl;
  }
  cout << sum << endl;
  return 0;
}
题目详情