Scratch编程一级 题库
圣诞老人的礼物
圣诞节来临了,在城市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;
}中缀表达式的值
人们熟悉的四则运算表达式称为中缀表达式,例如(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;
}合法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;
}拨钟问题
有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;
}广义格雷码
在一组数的编码中,若任意两个相邻(首尾也视为相邻)的代码只有一位二进制数不同,则称这种编码为格雷码。如四位格雷码:
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;
}扑克牌排序
假设这里有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;
}词典
你旅游到了一个国外的城市。那里的人们说的外国语言你不能理解。不过幸运的是,你有一本词典可以帮助你。
时间限制: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;
}滑雪
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和它保存的最大滑行距离中的最大值。
最后求完总共的点,进行遍历,得到最终最大值。
表达式· 表达式树· 表达式求值
众所周知, 任何一个表达式, 都可以用一棵表达式树来表示。 例如,
表达式 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;
}