C/C++编程六级 题库
波兰表达式
波兰表达式是一种把运算符前置的算术表达式,例如普通的表达式2 + 3的波兰表示法为+ 2 3。波兰表达式的优点是运算符之间不必有优先级关系,也不必用括号改变运算次序,例如(2 + 3) * 4的波兰表示法为* + 2 3 4。本题求解波兰表达式的值,其中运算符包括+ - * /四个。
时间限制:1000
内存限制:65536
输入
输入为一行,其中运算符和运算数之间都用空格分隔,运算数是浮点数。
输出
输出为一行,表达式的值。 可直接用printf("%f\n", v)输出表达式的值v。
样例输入
* + 11.0 12.0 + 24.0 35.0
样例输出
1357.000000
#include <bits/stdc++.h>
using namespace std;
double exp() {
char s[20];
cin >> s;
switch (s[0]) {
case '+':
return exp() + exp();
case '-':
return exp() - exp();
case '*':
return exp() * exp();
case '/':
return exp() / exp();
default:
return stof(s);
}
}
int main() {
printf("%0.6f", exp());
return 0;
}括号配对
字符串中可能有三种成对的括号,"( )"、"[ ]"、"{ }"。请判断字符串的括号是否都正确配对。无括号也算正确配对。括号交叉算不正确配对,例如"12{34[78}ab]"就不算正确配对。但是一对括号被包含在另一对括号里面,例如"12{ab[8]}"不影响正确性。
时间限制:1000
内存限制:65536
输入
第一行为整数n(n<40),接下来有n行,每行一个无空格的字符串,长度小于1000。
输出
对每行字符串,如果括号配对,输出"YES",否则输出"NO"。
样例输入
2
12{ab[8]}
12{34[78}ab]样例输出
YES NO
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
int main() {
cin >> n;
while (n--) {
cin >> s;
stack<char> st;
int ls = s.size();
bool sign = true;
for (int i = 0; i < ls; i++) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{')
st.push(s[i]);
else if (!st.empty() && s[i] == ')') {
if (st.top() == '(')
st.pop();
else
sign = false;
} else if (s[i] == '}') {
if (!st.empty() && st.top() == '{')
st.pop();
else
sign = false;
} else if (s[i] == ']') {
if (!st.empty() && st.top() == '[')
st.pop();
else
sign = false;
}
}
if (st.empty() && sign)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}扑克牌排序(2023.3)
假设这里有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 <bits/stdc++.h>
using namespace std;
int main() {
int n;
string s;
queue<string> qn[9];
queue<string> color[4];
queue<string> qs;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s;
int t = s[1] - '0' - 1;
qn[t].push(s);
}
for (int i = 0; i <= 8; i++) {
cout << "Queue" << i + 1 << ":";
while (!qn[i].empty()) {
s = qn[i].front();
switch (s[0]) {
case 'A':
color[0].push(s);
break;
case 'B':
color[1].push(s);
break;
case 'C':
color[2].push(s);
break;
case 'D':
color[3].push(s);
break;
}
qn[i].pop();
cout << s << " ";
}
cout << endl;
}
for (int i = 0; i <= 3; i++) {
cout << "Queue" << (char)('A' + i) << ":";
while (!color[i].empty()) {
s = color[i].front();
color[i].pop();
qs.push(s);
cout << s << " ";
}
cout << endl;
}
while (!qs.empty()) {
cout << qs.front() << " ";
qs.pop();
}
return 0;
}滑动窗口
给定一个长度为n(n<=10^6)的数组。有一个大小为k的滑动窗口从数组的最左端移动到最右端。你可以看到窗口中的k个数字。窗口每次向右滑动一个数字的距离。
下面是一个例子:
数组是 [1 3 -1 -3 5 3 6 7], k = 3。

你的任务是得到滑动窗口在每个位置时的最大值和最小值。
时间限制:20000
内存限制:65536
输入
输入包括两行。 第一行包括n和k,分别表示数组的长度和窗口的大小。 第二行包括n个数字。
输出
输出包括两行。 第一行包括窗口从左至右移动的每个位置的最小值。 第二行包括窗口从左至右移动的每个位置的最大值。
样例输入
8 3 1 3 -1 -3 5 3 6 7
样例输出
-1 -3 -3 -3 3 3 3 3 5 5 6 7
#include#include #include using namespace std; int n, k, tmp; deque p; deque q; vector arr; vector MyMax; vector MyMin; int main() { cin >> n >> k; for (int i = 0; i < n; ++i) { scanf("%d", &tmp); arr.push_back(tmp); } for (int i = 0; i < n; ++i) { if (!p.empty() && p.front() == i - k) // 把窗口划过部分的序号删掉 p.pop_front(); while (!p.empty() && arr[p.back()] < arr[i]) // 删去队尾比当前元素小的,肯定用不到他们 p.pop_back(); p.push_back(i); // 当前元素入队 if (i >= k - 1) // 从k-1开始记录(第一个窗口 MyMax.push_back(arr[p.front()]); } for (int i = 0; i < n; ++i) { if (!q.empty() && q.front() == i - k) q.pop_front(); while (!q.empty() && arr[q.back()] > arr[i]) q.pop_back(); q.push_back(i); if (i >= k - 1) MyMin.push_back(arr[q.front()]); } for (int i = 0; i <= n - k; ++i) cout << MyMin[i] << ' '; cout << endl; for (int i = 0; i <= n - k; ++i) cout << MyMax[i] << ' '; return 0; }
区间合并(2022-12-六级)
给定 n 个闭区间 [ai; bi],其中i=1,2,...,n。任意两个相邻或相交的闭区间可以合并为一个闭区间。例如,[1;2] 和 [2;3] 可以合并为 [1;3],[1;3] 和 [2;4] 可以合并为 [1;4],但是[1;2] 和 [3;4] 不可以合并。
我们的任务是判断这些区间是否可以最终合并为一个闭区间,如果可以,将这个闭区间输出,否则输出no。
时间限制:1000
内存限制:65536
输入
第一行为一个整数n,3 ≤ n ≤ 50000。表示输入区间的数量。 之后n行,在第i行上(1 ≤ i ≤ n),为两个整数 ai 和 bi ,整数之间用一个空格分隔,表示区间 [ai; bi](其中 1 ≤ ai ≤ bi ≤ 10000)。
输出
输出一行,如果这些区间最终可以合并为一个闭区间,输出这个闭区间的左右边界,用单个空格隔开;否则输出 no。
样例输入
5 5 6 1 5 10 10 6 9 8 10
样例输出
1 10
#include <bits/stdc++.h>
using namespace std;
struct Nod {
int x, y;
friend bool operator<(Nod a, Nod b) {
if (a.x != b.x)
return a.x < b.x;
else
return a.y < b.y;
}
} node[50005];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> node[i].x >> node[i].y;
sort(node, node + n);
int lf = node[0].x;
int rt = node[0].y;
for (int i = 1; i < n; i++) {
if (lf <= node[i].x && node[i].x <= rt) {
rt = max(rt, node[i].y);
} else {
cout << "no";
return 0;
}
}
cout << lf << " " << rt;
return 0;
}电话号码(2022-12,六级)
给你一些电话号码,请判断它们是否是一致的,即是否有某个电话是另一个电话的前缀。比如:
Emergency 911
Alice 97 625 999
Bob 91 12 54 26
在这个例子中,我们不可能拨通Bob的电话,因为Emergency的电话是它的前缀,当拨打Bob的电话时会先接通Emergency,所以这些电话号码不是一致的。
时间限制:1000
内存限制:65536
输入
第一行是一个整数t,1 ≤ t ≤ 40,表示测试数据的数目。 每个测试样例的第一行是一个整数n,1 ≤ n ≤ 10000,其后n行每行是一个不超过10位的电话号码。
输出
对于每个测试数据,如果是一致的输出“YES”,如果不是输出“NO”。
样例输入
2 3 911 97625999 91125426 5 113 12340 123440 12345 98346
样例输出
NO YES
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct Trie {
int c[10], s;
Trie() {
memset(c, 0, sizeof(c));
s = 0;
}
} t[N];
int tot;
void clear(int x) {
t[x].s = 0;
for (int i = 0; i <= 9; i++)
if (t[x].c[i])
clear(t[x].c[i]), t[x].c[i] = 0;
}
char s[15];
bool bt(int x) {
int len = strlen(s + 1);
bool bk = false;
for (int i = 1; i <= len; i++) {
int y = s[i] - '0';
if (!t[x].c[y])
t[x].c[y] = ++tot;
else if (i == len)
bk = true;
x = t[x].c[y];
if (t[x].s)
bk = true;
}
t[x].s++;
return bk;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
bool bk = false;
clear(0);
tot = 0;
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%s", s + 1);
if (bk)
continue;
if (bt(0))
bk = true;
}
if (bk)
puts("NO");
else
puts("YES");
}
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 <bits/stdc++.h>
using namespace std;
int main() {
int n;
string s;
queue<string> qn[9];
queue<string> color[4];
queue<string> qs;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s;
int t = s[1] - '0' - 1;
qn[t].push(s);
}
for (int i = 0; i <= 8; i++) {
cout << "Queue" << i + 1 << ":";
while (!qn[i].empty()) {
s = qn[i].front();
switch (s[0]) {
case 'A':
color[0].push(s);
break;
case 'B':
color[1].push(s);
break;
case 'C':
color[2].push(s);
break;
case 'D':
color[3].push(s);
break;
}
qn[i].pop();
cout << s << " ";
}
cout << endl;
}
for (int i = 0; i <= 3; i++) {
cout << "Queue" << (char)('A' + i) << ":";
while (!color[i].empty()) {
s = color[i].front();
color[i].pop();
qs.push(s);
cout << s << " ";
}
cout << endl;
}
while (!qs.empty()) {
cout << qs.front() << " ";
qs.pop();
}
return 0;
}现代艺术
在对二维艺术作品感到厌烦之后,伟大的艺术牛Picowso决定从事创作一项更为小众的艺术形式,一维画。
尽管目前她的画作可以用一个由颜色组成的长度为N(1~100000)的数组表示,但她的创作风格依然保持不变:从一张空白的矩形画布上,不断地画上一些矩形,在一维的情况下,这些矩形就只是一个区间。她用N种颜色,颜色编号为1~N进行创作,每种颜色只使用一次,之后使用的颜色可以完全的覆盖之前在相同位置上的颜色。
令Picowso感到十分沮丧的是,她的竞争对手Moonet似乎弄明白了如何复制她的这些一维画作,Moonet会画一些不相交的间隔,等待这些颜色晾干,然后再画另外的一些间隔,直到画完。Moonet每次每种颜色最多只能画一个间隔,但是他可以一次画不同颜色不相交的多个间隔,只要这些间隔没有重叠部分。之后Moonet再进行下一轮绘制。请计算Moonet为了复制一幅画需要画几个回合。
时间限制:10000
内存限制:65536
输入
第一行是一个整数N,之后N行包含了N个整数,范围0到N表示纸带每个格点的颜色,0表示没有涂色。
输出
输出一行,需要复制这幅画作的最少回合数,如果这幅画不可能是Picowso的画作输出-1(比如说这幅画不可能是通过一次在一条上画一层的方法进行创作的)
样例输入
7 0 1 4 5 1 3 3
样例输出
2
提示
在这个样例中,第一轮涂成0111133,第二轮涂成0145133,所以共需两轮。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int end_pos[N], a[N];
int n, result, flag = 1;
char v[N];
stack<int> s;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i += 1) {
scanf("%d", &a[i]);
end_pos[a[i]] = i; // 记录每个颜色的终点位置
}
v[0] = 1; // 初始化 将0视为覆盖整个画布的第一种颜色
end_pos[0] = n + 1;
s.push(0);
for (int i = 1; i <= n && flag; i++) {
if (s.top() != a[i]) {
if (v[a[i]])
flag = 0; // 颜色被使用过 标记非法
s.push(a[i]); // 加入新的颜色
}
v[a[i]] = 1; // 标记该颜色被使用过
result = max(result, (int)s.size());
if (i == end_pos[a[i]]) {
s.pop(); // 该颜色最后一次被使用 弹出改颜色
}
}
if (!flag)
cout << -1;
else
cout << result - 1;
return 0;
}字符串插入
有两个字符串str和substr,str的字符个数不超过10,substr的字符个数为3。(字符个数不包括字符串结尾处的'\0'。)将substr插入到str中ASCII码最大的那个字符后面,若有多个最大则只考虑第一个。
时间限制:1000
内存限制:65536
输入
输入包括若干行,每一行为一组测试数据,格式为 str substr
输出
对于每一组测试数据,输出插入之后的字符串。
样例输入
abcab eee 12343 555
样例输出
abceeeab 12345553
#include<bits/stdc++.h>
using namespace std;
int main()
{
string str,substr;
while(cin>>str>>substr)
{
int maxn=0,maxid,i;
for(i=0;i<str.size();i++)
{
if((str[i]-'0')>maxn)
{
maxn=str[i]-'0';
maxid=i;
}
}
for(i=0;i<str.size();i++)
{
cout<<str[i];
if(i==maxid) cout<<substr;
}
cout<<endl;
}
return 0;
}机器翻译
VariantF的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换。对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译;如果内存中没有,软件就会在外存中的词典内查找,查出单词的中文含义然后翻译,并将这个单词和译义放入内存,以备后续的查找和翻译。
假设内存中有M 个单元,每单元能存放一个单词和译义。每当软件将一个新单词存入内存前,如果当前内存中已存入的单词数不超过M,软件会将新单词存入一个未使用的内存单元;若内存中已存入M 个单词,软件会清空最早进入内存的那个单词,腾出单元来,存放新单词。
假设一篇英语文章的长度为N 个单词。给定这篇待译文章,翻译软件需要去外存查找多少次词典?假设在翻译开始前,内存中没有任何单词。
时间限制:1000
内存限制:262144
输入
第一行为两个正整数M 和N,代表内存容量和文章的长度。 第二行为N 个非负整数,按照文章的顺序,每个数(大小不超过1000000)代表一个英文单词。文章中两个单词是同一个单词,当且仅当它们对应的非负整数相同。 对于50%的数据,1<=N、M<=1000; 对于100%的数据,1<=N、M<=1000000。
输出
一个整数,为软件需要查词典的次数。
样例输入
3 7 1 2 1 5 4 4 1
样例输出
5
提示
整个查字典过程如下:每行表示一个单词的翻译,冒号前为本次翻译后的内存状况: 空:内存初始状态为空。 1. 1:查找单词1 并调入内存。 2. 1 2:查找单词2 并调入内存。 3. 1 2:在内存中找到单词1。 4. 1 2 5:查找单词5 并调入内存。 5. 2 5 4:查找单词4 并调入内存替代单词1。 6. 2 5 4:在内存中找到单词4。 7. 5 4 1:查找单词1 并调入内存替代单词2。 共计查了5 次词典。
#include<cstdio>
int word[2000];
bool sch(int tgt,int range)//线性搜索,因为数据<1000,不会超时。
{
for(int i=0;i<range;i++)
{
if(word[i]==tgt)
{
return true;
}
}
return false;
}
int main()
{
int mem,num,tm,wor,ans=0;
scanf("%d %d",&mem,&num);
tm=0;
for(int i=0;i<2000;i++)
{
word[i]=-1;//数组初始化一定要初始化成-1!!!!
//字母代号有可能是0,所以初始化成0会出错!!!!
}
for(int i=0;i<num;i++)
{
scanf("%d",&wor);
//非常节省空间和时间的模拟
if(tm>=mem)
{
tm=0;
}
if(!sch(wor,mem))
{
//自己进行轮回。。。
ans++;
word[tm]=wor;
tm++;
}
}
printf("%d",ans);
}// 题解2
#include <bits/stdc++.h>
using namespace std;
int main() {
deque<int> v;
int m, n, ans = 0;
cin >> m >> n;
for (int i = 1, a; i <= n; i++) {
cin >> a;
if (v.empty()) {
v.push_back(a);
ans++;
} else {
auto it = std::find(v.begin(), v.end(), a);
if (it != v.end())
continue;
else {
if (v.size() == unsigned(m))
v.pop_front();
v.push_back(a);
ans++;
}
}
}
cout << ans;
return 0;
}栈基本操作
依次读入序列元素1,2,...,n进栈,每进一个元素,机器可要求下一个元素进栈或弹栈,如此进行。给定一个输入序列,判断栈空时弹出的元素构成的序列是否可能等于给定的序列,如果是则输出栈的操作过程,否则输出“NO”。
时间限制:1000
内存限制:65535
输入
输入分两行 第一行为n的值(即序列元素个数) 第二行为给定的输入序列(序列元素均为整型)
输出
如果输入序列能够由题目规定的操作得到,则输出对栈的操作过程 否则直接输出“NO”
样例输入
7 4 5 3 6 2 7 1
样例输出
PUSH 1 PUSH 2 PUSH 3 PUSH 4 POP 4 PUSH 5 POP 5 POP 3 PUSH 6 POP 6 POP 2 PUSH 7 POP 7 POP 1
提示
给定序列中有可能有不在1...n之间的数字
//解法1
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[100001],t=1,i;
int l1[100001],l2[100001],l=0;
stack <int> s;
for(i=1;i<=n;i++)
cin>>a[i];
i=1;
int f=0;
while(1)
{
s.push(t);
l++;
l1[l]=0;
l2[l]=t;
t++;
while(1)
{
if(s.size()==0) break;
if(a[i]!=s.top()) break;
i++;
l++;
l1[l]=1;
l2[l]=s.top();
s.pop();
}
if(s.size()==0 && t-1==n && i-1==n) break;
if(s.size()>0 && t-1==n && i-1<n)
{
cout<<"NO";
return 0;
}
}
for(i=1;i<=l;i++)
{
if(l1[i]==1) cout<<"POP ";
else cout<<"PUSH ";
cout<<l2[i]<<endl;
}
return 0;
}
//解法2
#include <bits/stdc++.h>
using namespace std;
int main()
{
queue<string> q;
stack<int> s;
string x="PUSH ",y="POP ";
int n;
cin>>n;
for(int i=1,j=1,a;i<=n;i++){
cin>>a;
if(a>n){
cout<<"NO";return 0;
}
if(s.empty()){
s.push(j);
q.push(x+char(j+'0'));
j++;
}
while(s.top()<a){
s.push(j);
q.push(x+char(j+'0'));
j++;
}
if(s.top()==a){
s.pop();
q.push(y+char(a+'0'));
}
else{
cout<<"NO";return 0;
}
}
if(!s.empty()){
cout<<"NO";return 0;
}
while(!q.empty()){
cout<<q.front()<<endl;
q.pop();
}
return 0;
}双端队列
定义一个双端队列,进队操作与普通队列一样,从队尾进入。出队操作既可以从队头,也可以从队尾。编程实现这个数据结构。
时间限制:1000
内存限制:65535
输入
第一行输入一个整数t,代表测试数据的组数。 每组数据的第一行输入一个整数n,表示操作的次数。 接着输入n行,每行对应一个操作,首先输入一个整数type。 当type=1,进队操作,接着输入一个整数x,表示进入队列的元素。 当type=2,出队操作,接着输入一个整数c,c=0代表从队头出队,c=1代表从队尾出队。 n <= 1000
输出
对于每组测试数据,输出执行完所有的操作后队列中剩余的元素,元素之间用空格隔开,按队头到队尾的顺序输出,占一行。如果队列中已经没有任何的元素,输出NULL。
样例输入
2 5 1 2 1 3 1 4 2 0 2 1 6 1 1 1 2 1 3 2 0 2 1 2 0
样例输出
3 NULL
//解法1
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int a,b,i;
int l[100001],head=1,tail=0;
for(i=1;i<=n;i++)
{
cin>>a>>b;
if(a==1)
{
tail++;
l[tail]=b;
}
else
{
if(b==0) head++;
else tail--;
}
}
if(tail-head<0 || head>tail) cout<<"NULL";
else
for(i=head;i<=tail;i++)
cout<<l[i]<<" ";
cout<<endl;
}
return 0;
}//解法2
//用deque模拟一下即可
#include <bits/stdc++.h>
using namespace std;
string s;
int main()
{
int n,m,type,x;
cin>>n;
for(int i=1;i<=n;i++){
cin>>m;
deque<int> q;
for(int j=1;j<=m;j++){
cin>>type>>x;
if(type==1){
q.push_back(x);
}else {
if(x==0)q.pop_front();
else q.pop_back();
}
}
if(q.empty()){
cout<<"NULL";continue;
}
while(!q.empty()){
cout<<q.front()<<" ";
q.pop_front();
}
cout<<endl;
}
return 0;
}生日相同 2.0
在一个有180人的大班级中,存在两个人生日相同的概率非常大,现给出每个学生的名字,出生月日。试找出所有生日相同的学生。
时间限制:1000
内存限制:65536
输入
第一行为整数n,表示有n个学生,n ≤ 180。此后每行包含一个字符串和两个整数,分别表示学生的名字(名字第一个字母大写,其余小写,不含空格,且长度小于20)和出生月(1 ≤ m ≤ 12)日(1 ≤ d ≤ 31)。名字、月、日之间用一个空格分隔
输出
每组生日相同的学生,输出一行,其中前两个数字表示月和日,后面跟着所有在当天出生的学生的名字,数字、名字之间都用一个空格分隔。对所有的输出,要求按日期从前到后的顺序输出。 对生日相同的名字,按名字从短到长按序输出,长度相同的按字典序输出。如没有生日相同的学生,输出”None”
样例输入
6 Avril 3 2 Candy 4 5 Tim 3 2 Sufia 4 5 Lagrange 4 5 Bill 3 2
样例输出
3 2 Tim Bill Avril 4 5 Candy Sufia Lagrange
//参考答案1
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 185
using namespace std;
struct ccc
{
char name[N];
int mouth;
int day;
}student[N];
bool com(ccc a,ccc b)//排序,日期从小到大输出
{
if(a.mouth==b.mouth)
{
return a.day<b.day;
}
else return a.mouth<b.mouth;
}
int main()
{
int n;
while(scanf("%d ",&n)!=EOF)
{
char tmp[N][N];int sum=0,x=0;
for(int i=0;i<n;i++)
{
scanf("%s %d%d",&student[i].name,&student[i].mouth,&student[i].day);
}
sort(student,student+n,com);
for(int i=0;i<n-1;i++)
{
while(student[i].day==student[i+1].day)//生日相同记录数量
{
strcpy(tmp[i],student[i].name);
strcpy(tmp[i+1],student[i+1].name);
sum++;i++;
}
if(sum>=1)//如果生日相同
{
x=1;
printf("%d %d ",student[i].mouth,student[i].day);
int a[N]={0};//学生名字长度
int min=1000;
for(int j=i-sum;j<i+1;j++)
{
a[j]=strlen(tmp[j]);
}
int m=sum+1,t;
while(m>0)//每次找到最小的名字输出
{
for(int j=i-sum;j<i+1;j++)
{
if(a[j]<min)//长度最小
{
min=a[j];t=j;
}
else if(a[j]==min)
{
if(strcmp(tmp[j],tmp[t])<0)//字典序最小
{
t=j;
}
}
if(j==i)
{
a[t]=1000;
}
}
if(m==1)
{
printf("%s\n",tmp[t]);
sum=0;
}
else printf("%s ",tmp[t]);
m--;min=1000;
}
}
}
if(x==0)
{
printf("None");
}
}
return 0;
}//参考答案2
#include<stdio.h>
#include<string.h>
struct stuent{
char name[100];
int birth[2];
}stu[200];
struct stuent tmp;
int main(){
int i,j,k;
int n;
int flag=0;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%s",stu[i].name);
scanf("%d%d",&stu[i].birth[0],&stu[i].birth[1]);
}
for(i=0;i<n;i++){
for(j=n-1;j>i;j--){
if(strlen(stu[j].name)<strlen(stu[j-1].name)){
tmp=stu[j];
stu[j]=stu[j-1];
stu[j-1]=tmp;
}
else if(strlen(stu[j].name)==strlen(stu[j-1].name)&&strcmp(stu[j].name,stu[j-1].name)<0){
tmp=stu[j];
stu[j]=stu[j-1];
stu[j-1]=tmp;
}
}
}
for(i=0;i<n;i++){
for(j=n-1;j>i;j--){
if(stu[j].birth[0]<stu[j-1].birth[0]){
tmp=stu[j];
stu[j]=stu[j-1];
stu[j-1]=tmp;
}
else if(stu[j].birth[0]==stu[j-1].birth[0]&&stu[j].birth[1]<stu[j-1].birth[1]){
tmp=stu[j];
stu[j]=stu[j-1];
stu[j-1]=tmp;
}
}
}
for(i=0;i<n;i=j){
for(j=i+1;j<n;j++){
if(stu[i].birth[0]==stu[j].birth[0]&&stu[i].birth[1]==stu[j].birth[1])
;
else break;
}
if((j-i)>1){flag=1;
printf("%d %d ",stu[i].birth[0],stu[i].birth[1]);
for(k=i;k<j;k++) printf("%s ",stu[k].name);
printf("\n");
}
}
if(!flag) printf("None");
return 0;
}//参考答案3
//结构体排序+队列的基本操作 模拟一下即可
#include <bits/stdc++.h>
using namespace std;
struct Birthday{
string name;
int moth,day,len_B;
}b[200];
bool cmp(Birthday &a,Birthday &b){
if(a.moth!=b.moth) return a.moth<b.moth;
else {
if(a.day!=b.day) return a.day<b.day;
else {
if(a.len_B!=b.len_B) return a.len_B<b.len_B;
else return a.name<b.name;
}
}
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>b[i].name>>b[i].moth>>b[i].day;
b[i].len_B=b[i].name.size();
}
sort(b,b+n,cmp);
queue<string> Name;
Birthday t=b[0];
int sign=1;
for(int i=1;i<n;i++){
if(b[i].moth==t.moth && b[i].day==t.day){
Name.push(b[i].name);
sign=0;
}
else {
if(!Name.empty()){
cout<<t.moth<<" "<<t.day<<" "<<t.name<<" ";
while(!Name.empty()){
cout<<Name.front()<<" ";Name.pop();
}
cout<<endl;
}
t=b[i];
}
}
if(!Name.empty()){
cout<<t.moth<<" "<<t.day<<" "<<t.name<<" ";
while(!Name.empty()){
cout<<Name.front()<<" ";Name.pop();
}
cout<<endl;
}
if(sign) cout<<"None";
return 0;
}合法出栈序列
给定一个由不同小写字母构成的长度不超过8的字符串x,现在要将该字符串的字符依次压入栈中,然后再全部弹出。
要求左边的字符一定比右边的字符先入栈,出栈顺序无要求。
再给定若干字符串,对每个字符串,判断其是否是可能的x中的字符的出栈序列。
时间限制:1000
内存限制:65536
输入
第一行是原始字符串x 后面有若干行,每行一个字符串
输出
对除第一行以外的每个字符串,判断其是否是可能的出栈序列。如果是,输出"YES",否则,输出"NO"
样例输入
abc abc bca cab
样例输出
YES YES NO
#include <bits/stdc++.h>
using namespace std;
string a,b;
int main()
{
cin>>a;
while(cin>>b){
stack<char> st;
int j=0;
for(int i=0;i<a.size();i++){
if(!st.empty())
if(st.top()==b[j]){
st.pop();j++;
}
st.push(a[i]);
}
while(!st.empty()&&st.top()==b[j]&&j<b.size()){
st.pop();j++;
}
if(st.empty())cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}括号画家(2023.9)
Candela是一名漫画家,她有一个奇特的爱好,就是在纸上画括号。这一天,刚刚起床的Candela画了一排括号序列,其中包含小括号()、中括号[]和大括号{},总长度为N。这排随意绘制的括号序列显得杂乱无章,于是Candela定义了什么样的括号序列是美观的:
(1) 空的括号序列是美观的;
(2) 若括号序列A是美观的,则括号序列(A)、[A]、{A}也是美观的;
(3) 若括号序列A、B都是美观的,则括号序列AB也是美观的;
例如 [(){}]() 是美观的括号序列,而 )({)[}]( 则不是。
现在Candela想知道她画出的括号序列是不是美观的。你能帮帮她吗?
时间限制:1000
内存限制:262144
输入
一个括号序列,长度不超过10000。
输出
如果它是美观的,输出Yes,否则输出No。
样例输入
{}[(){}]()样例输出
Yes
//青少年考级竞赛题库(tiku.scratchor.com)搜集整理,感谢网友提供代码!
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
stack<char>str;
//判断左右两个括号是否美观
bool beauty(char s1, char s2) {
switch (s1) {
case '{':
if (s2 == '}')
return true;
else
return false;
case '[':
if (s2 == ']')
return true;
else
return false;
case '(':
if (s2 == ')')
return true;
else
return false;
}
}
int main()
{
string Brackets;
char s;
int i = 0;
cin >> Brackets;
while (i < Brackets.length()) {
s = Brackets[i];
i++;
str.push(s); //将当前字符入栈
char s2 = str.top();
if (s2 == ']' || s2 == '}' || s2 == ')') //是右括号,进行判断是否与左括号美观
{
str.pop(); //将s2出栈
if (str.empty()) { //无左括号,肯定不美观
cout << "No" << endl;
return 0;
}
char s1 = str.top(); //s1是左括号
if (beauty(s1, s2)) { //美观,将s1出栈
str.pop();
}
else { //不美观
cout << "No" << endl;
return 0;
}
}
}
cout << "Yes";
}表达式求值
求一个可能包含加、减、乘、除、乘方运算的中缀表达式的值。
在计算机中,我们常用栈来解决这一问题。首先将中缀表达式转换到后缀表达式,然后对后缀表达式求值。
加、减、乘、除、乘方分别用+,-,*, /, ^来表示。表达式可以有圆括号()。
时间限制:1000
内存限制:65536
输入
第一行为测试数据的组数N。 接下来的N行,每行是一个中缀表达式。 每个表达式中,圆括号、运算符和运算数相互之间都用空格分隔,运算数是整数。一般运算数可正可负(负数的符号和数字之间无空格),指数一定为自然数(0和正整数)。不必考虑除0的情况。每个运算数均可由int放下。不必考虑溢出。中缀表达式的字符串长度不超过600。乘方的优先级比乘除都高,结合性是向左结合,如2 ^ 3 ^ 4表示( 2 ^ 3 ) ^ 4 = 4096。除法的商向下取整。
输出
对每一组测试数据输出一行,为表达式的值
样例输入
2 31 * ( 5 - ( -3 + 25 ) ) + 70 ^ 2 2 * 5 + 6 * ( 7 - 8 ) + 6
样例输出
4373 10
#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] == '-' && (i + 1 < s.size()) && s[i + 1] >= '0' && s[i + 1] <= '9')
t = "-";
else if (s[i] >= '0' && s[i] <= '9')
t += s[i];
else if (ops.find(s[i]) != string::npos)
t += s[i];
else if (s[i] == ' ') {
if (t.size() > 0)
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;
getline(cin, s);
int n;
n = atoi(s.c_str());
while (n--) {
getline(cin, s);
vector<string> vs = scaner(s);
vs = infix_Suffix(vs);
suffix_calc(vs);
}
return 0;
}多项式相加(2023.12)
我们经常遇到两多项式相加的情况, 在这里, 我们就需要用程序来模拟实现把两个多项式相加到一起。 首先, 我们会有两个多项式,每个多项式是独立的一行, 每个多项式由系数、 幂数这样的多个整数对来表示。
如多项式 2x20- x17+ 5x9- 7x7+ 16x5+ 10x4 + 22x2- 15
对应的表达式为: 2 20 -1 17 5 9 - 7 7 16 5 10 4 22 2 -15 0。
为了标记每行多项式的结束, 在表达式后面加上了一个幂数为负数的整数对。
同时输入表达式的幂数大小顺序是随机的。我们需要做的就是把所给的两个多项式加起来。
时间限制: 1000
内存限制: 65536
输入
输入包括多行。 第一行整数 n,表示有多少组的多项式需要求和。 (1 <n < 100) 下面为 2n 行整数, 每一行都是一个多项式的表达式。 表示 n组需要相加的多项式。 每行长度小于 300。
输出
输出包括 n 行, 每行为 1 组多项式相加的结果。 在每一行的输出结果中, 多项式的每一项用“[x y]” 形式的字符串表示, x 是该项的系数、 y 是该项的幂数。 要求按照每一项的幂从高到低排列, 即先输出幂数高的项、 再输出幂数低的项。 系数为零的项不要输出。
样例输入
2 -1 17 2 20 5 9 -7 7 10 4 22 2 -15 0 16 5 0 -1 2 19 7 7 3 17 4 4 15 10 -10 5 13 2 -7 0 8 -8 -1 17 2 23 22 2 6 8 -4 7 -18 0 1 5 21 4 0 -1 12 7 -7 5 3 17 23 4 15 10 -10 5 13 5 2 19 9 -7
样例输出
[ 2 20 ] [ 2 19 ] [ 2 17 ] [ 15 10 ] [ 5 9 ] [ 6 5 ] [ 14 4 ] [ 35 2 ] [ -22 0 ] [ 2 23 ] [ 2 19 ] [ 2 17 ] [ 15 10 ] [ 6 8 ] [ 8 7 ] [ -3 5 ] [ 44 4 ] [ 22 2 ] [ -18 0 ]
提示
第一组样例数据的第二行末尾的 8 -8, 因为幂次-8 为负数, 所以这一行数据结束, 8 -8 不要参与计算。
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
for (int i = 0; i != n; ++i) {
map<int, int> ploy;
int index, value, over = 0;
while (cin >> value >> index) {
if (index < 0)
over++;
else {
pair<map<int, int>::iterator, bool> ret =
ploy.insert(make_pair(index, value));
if (!ret.second)
ret.first->second += value;
}
if (over == 2)
break;
}
for (map<int, int>::reverse_iterator riter = ploy.rbegin();
riter != ploy.rend(); ++riter) {
if (riter->second != 0)
cout << "[ " << riter->second << ' ' << riter->first << " ] ";
}
cout << endl;
}
return 0;
}队列和栈(2023.12)
队列和栈是两种重要的数据结构,它们具有push k和pop操作。push k是将数字k加入到队列或栈中,pop则是从队列和栈取一个数出来。队列和栈的区别在于取数的位置是不同的。
队列是先进先出的:把队列看成横向的一个通道,则push k是将k放到队列的最右边,而pop则是从队列的最左边取出一个数。
栈是后进先出的:把栈也看成横向的一个通道,则push k是将k放到栈的最右边,而pop也是从栈的最右边取出一个数。
假设队列和栈当前从左至右都含有1和2两个数,则执行push 5和pop操作示例图如下:
push 5 pop
队列 1 2 -------> 1 2 5 ------> 2 5
push 5 pop
栈 1 2 -------> 1 2 5 ------> 1 2
现在,假设队列和栈都是空的。给定一系列push k和pop操作之后,输出队列和栈中存的数字。若队列或栈已经空了,仍然接收到pop操作,则输出error。
时间限制:1000
内存限制:65536
输入
第一行为m,表示有m组测试输入,m<100。 每组第一行为n,表示下列有n行push k或pop操作。(n<150) 接下来n行,每行是push k或者pop,其中k是一个整数。 (输入保证同时在队列或栈中的数不会超过100个)
输出
对每组测试数据输出两行,正常情况下,第一行是队列中从左到右存的数字,第二行是栈中从左到右存的数字。若操作过程中队列或栈已空仍然收到pop,则输出error。输出应该共2*m行。
样例输入
2 4 push 1 push 3 pop push 5 1 pop
样例输出
3 5 1 5 error error
#include <stdio.h>
#include <string.h>
#define N 150
int stack[N], ps;
int queue[N], qh, qt;
char cmd[5];
int main(void) {
int m, n, sflag, qflag, a, i;
scanf("%d", &m);
while (m--) {
scanf("%d", &n);
sflag = qflag = 0;
ps = 0, qh = 0;
qt = 0;
while (n--) {
scanf("%s", cmd);
if (cmd[1] == 'u') {
scanf("%d", &a);
stack[ps++] = a;
queue[qt++] = a;
} else if (cmd[1] == 'o') {
if (ps == 0)
sflag = 1;
if (qt - qh == 0)
qflag = 1;
ps--;
qh++;
}
}
if (qflag)
printf("error\n");
else {
for (i = qh; i < qt; i++)
printf("%d ", queue[i]);
printf("\n");
}
if (sflag)
printf("error\n");
else {
for (i = 0; i < ps; i++)
printf("%d ", stack[i]);
printf("\n");
}
}
return 0;
}奇怪的括号(2023.12)
某天小A和同学在课堂上讨论到:“栈这种数据结构真是太优美了,既简单用途又广泛。”小B仰慕小A许久,于是他拿出了自己在网上抄写的一道题问小A,如何判断括号是否匹配呢
时间限制:1000
内存限制:65536
输入
多组数据,每组数据占一行,且都是由(、)、[、]、*、/这六种字符组成。
输出
每组数据输出一行,如果括号能匹配成功,输出True,否则输出False。括号匹配规则是: ( 和 ) 匹配 [ 和 ] 匹配 /* 和 */ 匹配 如果含有冗余字符也算匹配失败,例如 /***/ 是匹配失败的因为中间多了一个*。
样例输入
()/*[()]*/ */**/
样例输出
True False
#include <bits/stdc++.h>
using namespace std;
string s;
int main() {
while (cin >> s) {
stack<char> st;
for (int i = 0; i < s.size(); i++) {
if (st.empty()) {
st.push(s[i]);
} else {
if (s[i] == ')' && st.top() == '(')
st.pop();
else if (s[i] == ']' && st.top() == '[')
st.pop();
else if (s[i] == '/' && st.top() == '*' && st.size() >= 3) {
st.pop();
char a = st.top();
st.pop();
char b = st.top();
st.pop();
if (!(a == '*' && b == '/')) {
st.push(b);
st.push(a);
st.push('*');
}
} else
st.push(s[i]);
}
}
if (st.empty())
cout << "True" << endl;
else
cout << "False" << endl;
}
return 0;
}中缀表达式的值(2023.12)
人们熟悉的四则运算表达式称为中缀表达式,例如(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;
}