首页 › 题库 › C/C++编程考级 › C/C++编程六级

C/C++编程六级 题库

共 76 道题 ,第 2 / 4 页 · 按题型筛选,点「查看答案」核对解析
21 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

波兰表达式

波兰表达式是一种把运算符前置的算术表达式,例如普通的表达式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;
}
题目详情
22 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

括号配对

字符串中可能有三种成对的括号,"( )"、"[ ]"、"{ }"。请判断字符串的括号是否都正确配对。无括号也算正确配对。括号交叉算不正确配对,例如"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;
}
题目详情
23 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

扑克牌排序(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;
}
题目详情
24 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

滑动窗口

给定一个长度为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;
}
题目详情
25 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

区间合并(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;
}
题目详情
26 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

电话号码(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;
}

  

题目详情
27 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

扑克牌排序

假设这里有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;
}
题目详情
28 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

现代艺术

在对二维艺术作品感到厌烦之后,伟大的艺术牛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;
}
题目详情
29 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

字符串插入

有两个字符串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;
}
题目详情
30 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

机器翻译

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;
}
题目详情
31 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

栈基本操作

依次读入序列元素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;
}
题目详情
32 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

双端队列

定义一个双端队列,进队操作与普通队列一样,从队尾进入。出队操作既可以从队头,也可以从队尾。编程实现这个数据结构。

时间限制: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;
}
题目详情
33 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

生日相同 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;
}
题目详情
34 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

合法出栈序列

给定一个由不同小写字母构成的长度不超过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;
}


题目详情
35 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

括号画家(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";
}


题目详情
36 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

表达式求值

求一个可能包含加、减、乘、除、乘方运算的中缀表达式的值。

在计算机中,我们常用栈来解决这一问题。首先将中缀表达式转换到后缀表达式,然后对后缀表达式求值。

加、减、乘、除、乘方分别用+,-,*, /, ^来表示。表达式可以有圆括号()。

时间限制: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;
}
题目详情
37 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 5 数论

多项式相加(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;
}
题目详情
38 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

队列和栈(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;
}
题目详情
39 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

奇怪的括号(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;
}
题目详情
40 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

中缀表达式的值(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;
}
题目详情