7.1~7.2 栈&队列

（1）7.1-A （**）

题目描述

读入一个只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。

输入

测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。

输出

对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。

样例输入 Copy

30 / 90 - 26 + 97 - 5 - 6 - 13 / 88 6 + 51 / 29 + 79 87 + 57 * 92 0

样例输出 Copy

12178.21

题解：

（1）涉及了栈，队列，难度较大。
（2）巧妙地构建了结构体，输入的字符不是操作数就是操作符，因此使用bool类型标记是什么
（3）记得去掉输入里的空格（erase）
（4）操作符的优先级在主函数里通过1，2巧妙涉及
（5）P248

代码：

  1. //
  2. // Created by 23011 on 4/2/2022.
  3. //
  5. // 7-1-A
  6. #include <iostream>
  7. #include <cstdio>
  8. #include <string>
  9. #include <stack>
  10. #include <queue>
  11. #include <map>
  12. using namespace std;
  13. struct node{
  14.     double num;  // 操作数
  15.     char op;    // 操作符
  16.     bool flag;  // true表示操作数，false表示操作符
  17. };
  18. string str;
  19. stack<node> s;
  20. queue<node> q;
  21. map<char, int> op;
  23. void Change ()     // 将中缀表达式转换为后缀表达式
  24. {
  25.     double num;
  26.     node temp;
  27.     for(int i = 0; i < str.length(); ){
  28.         if(str[i] >= '0' && str[i] <= '9'){ // 如果是数字
  29.             temp.flag = true;   // 标记是数字
  30.             temp.num = str[i++] - '0';  // 记录这个操作数的第一个数位
  31.             while (i < str.length() && str[i] >= '0' && str[i] <= '9'){
  32.                 temp.num = temp.num * 10 + (str[i] - '0');  // 更新这个操作数
  33.                 ++i;
  34.             }
  35.             q.push(temp);   // 将这个操作数压入后缀表达式的队列
  36.         }
  37.         else{
  38.             temp.flag = false;  // 标记是操作符
  39.             // 只要操作符栈的栈顶元素比该操作符优先级高
  40.             // 就把操作符栈顶元素弹出到后缀表达式队列中
  41.             while (!s.empty() && op[str[i]] <= op[s.top().op]){
  42.                 q.push(s.top());
  43.                 s.pop();
  44.             }
  45.             temp.op = str[i];
  46.             s.push(temp);   // 把该操作符压入操作符栈
  47.             ++i;
  48.         }
  49.     }
  50.     // 如果操作符栈中还有操作符，就把它弹出到后缀表达式队列中
  51.     while (!s.empty()){
  52.         q.push(s.top());
  53.         s.pop();
  54.     }
  55. }
  56. double Cal ()   // 计算后缀表达式
  57. {
  58.     double temp1, temp2;
  59.     node cur, temp;
  60.     while (!q.empty())     // 只要后缀表达式队列非空
  61.     {
  62.         cur = q.front();   // cur记录队首元素
  63.         q.pop();
  64.         if(cur.flag){
  65.             s.push(cur);        // 如果是操作数，直接入栈
  66.         }
  67.         else{   // 如果是操作符
  68.             temp2 = s.top().num;    // 弹出第二操作数
  69.             s.pop();
  70.             temp1 = s.top().num;    // 弹出第一操作数
  71.             s.pop();
  72.             temp.flag = true;   // 临时记录操作数
  73.             if(cur.op == '+')
  74.                 temp.num = temp1 + temp2;
  75.             else if(cur.op == '-')
  76.                 temp.num = temp1 - temp2;
  77.             else if(cur.op == '*')
  78.                 temp.num = temp1 * temp2;
  79.             else    temp.num = temp1 / temp2;
  80.             s.push(temp);    // 把该操作数压入栈
  81.         }
  82.     }
  83.     return s.top().num;     // 栈顶元素就是后缀表达式的值
  84. }
  85. int main()
  86. {
  87.     op['+'] = op['-'] = 1;  //设定操作符的优先级
  88.     op['*'] = op['/'] = 2;
  89.     while (getline(cin, str), str != "0"){
  90.         for(string::iterator it = str.end(); it != str.begin(); --it){
  91.             if(*it == ' '){     //把表达式中的空格全去掉，勿忽略
  92.                 str.erase(it);
  93.             }
  94.             while (!s.empty()){
  95.                 s.pop();    // 初始化栈
  96.             }
  97.         }
  98.         Change();
  99.         printf("%.2f\n",Cal()); // 计算后缀表达式
  100.     }
  101.     return 0;
  102. }

7.3 链表

（1）A1032 （静态链表）

To store English words, one method is to use linked lists and store a word letter by letter. To save some space, we may let the words share the same sublist if they share the same suffix. For example, loading and being are stored as showed in Figure 1.
image.png
Figure 1
You are supposed to find the starting position of the common suffix (e.g. the position of i in Figure 1).

Input Specification:

Each input file contains one test case. For each case, the first line contains two addresses of nodes and a positive N (≤105), where the two addresses are the addresses of the first nodes of the two words, and N is the total number of nodes. The address of a node is a 5-digit positive integer, and NULL is represented by −1.
Then N lines follow, each describes a node in the format:
Address Data Next
whereAddress is the position of the node, Data is the letter contained by this node which is an English letter chosen from { a-z, A-Z }, and Next is the position of the next node.

Output Specification:

For each case, simply output the 5-digit starting position of the common suffix. If the two words have no common suffix, output -1 instead.

Sample Input 1:

11111 22222 9
67890 i 00002
00010 a 12345
00003 g -1
12345 D 67890
00002 n 00003
22222 B 23456
11111 L 00001
23456 e 67890
00001 o 00010

Sample Output 1:

67890

Sample Input 2:

00001 00002 4
00001 a 10001
10001 s -1
00002 a 10002
10002 t -1

Sample Output 2:

-1

题解：

（1）以结构体形式存储节点，并设立bool flag; 初始化为false，把第一条链表遍历一遍，flag全改为true，然后从头遍历链表2，出现flag为true即为答案。
（2）这种题要有敏感度，一看就知道要用静态链表做。
（3）scanf使用%c是可以读入空格的，虽然scanf以空格和回车作为结束，但是此时空格还在缓冲区里。必须是%d %c %d，不能是%d%c%d
（4）格式输出%05d，宽度为5，不足5位高位补0

代码：

  1. #include <cstdio>
  2. const int maxn = 100010;
  3. struct node{
  4.     int next_ptr;
  5.     char data;
  6.     bool flag;
  7. }Node[maxn];
  8. int main()
  9. {
  10.     for(int i = 0; i < maxn; ++i)
  11.     {
  12.         Node[i].flag = false;
  13.     }
  14.     int s1, s2, n;
  15.     scanf("%d%d%d",&s1, &s2, &n);
  16.     int address, next;
  17.     char c;
  18.     for(int i = 0; i < n; ++i)
  19.     {
  20.         scanf("%d %c %d",&address, &c, &next);   // &c????
  21.         Node[address].data = c;
  22.         Node[address].next_ptr = next;
  23.     }
  24.     for(int p = s1; p != -1; p = Node[p].next_ptr)
  25.     {
  26.         Node[p].flag = true;
  27.     }
  28.     int p;
  29.     for(p = s2; p != -1; p = Node[p].next_ptr)
  30.     {
  31.         if(Node[p].flag == true)
  32.         {
  33.             printf("%05d\n",p);
  34.             break;
  35.         }
  36.     }
  37.     if(p == -1)
  38.     {
  39.         printf("-1");
  40.     }
  41.     return 0;
  42. }

（2）A1052

A linked list consists of a series of structures, which are not necessarily adjacent in memory. We assume that each structure contains an integer key and a Next pointer to the next structure. Now given a linked list, you are supposed to sort the structures according to their key values in increasing order.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive N (<105) and an address of the head node, where _N_ is the total number of nodes in memory and the address of a node is a 5-digit positive integer. NULL is represented by −1.
Then N lines follow, each describes a node in the format:
Address Key Next
where Address is the address of the node in memory, Key is an integer in [−105,105], and Next is the address of the next node. It is guaranteed that all the keys are distinct and there is no cycle in the linked list starting from the head node.

Output Specification:

For each test case, the output format is the same as that of the input, where N is the total number of nodes in the list and all the nodes must be sorted order.

Sample Input:

5 00001
11111 100 -1
00001 0 22222
33333 100000 11111
12345 -1 33333
22222 1000 12345

Sample Output:

5 12345
12345 -1 00001
00001 0 11111
11111 100 22222
22222 1000 33333
33333 100000 -1

题解：

（1）需要设立cnt记录有效节点个数，因为可能存在无效节点。而最后排序后，输出的循环要Node[0]~Node[cnt-1]而不是n-1
（2）运行时如果神奇的发现printf语句根本没执行，可以查看越界问题或者scanf格式问题，此代码之前的问题是const int maxn开小了
（3）好好看看cmp函数，巧妙运用bool类型中true(1) > false(0)，来实现把有效节点塞到结构体数组最前面，方便输出
（4）结束时的地址就是-1，不要被%05d格式化

代码：

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4. const int maxn = 100010;
  5. struct node{
  6.     int data;
  7.     int addr;
  8.     int next_ptr;
  9.     bool flag;  // 结构体数组开得很大，flag判断节点是否在链表上
  10. }Node[maxn];
  11. bool cmp (node a, node b)
  12. {
  13.     if(a.flag == false || b.flag == false)
  14.         return a.flag > b.flag;
  15.     else
  16.         return a.data < b.data;
  17. }
  18. int main()
  19. {
  20.     for(int i = 0; i < maxn; ++i)
  21.     {
  22.         Node[i].flag = false;
  23.     }
  24.     int n, begin;  // 节点数量和首元素地址
  25.     scanf("%d%d",&n, &begin);
  26.     int address, next;
  27.     int key;
  28.     for(int i = 0; i < n; ++i)
  29.     {
  30.         scanf("%d", &address);
  31.         scanf("%d%d",&Node[address].data, &Node[address].next_ptr);
  32.         Node[address].addr = address;
  33.     }
  34.     int cnt = 0, p = begin;
  35.     // 枚举链表，对flag标记，同时计数有效节点个数
  36.     while (p != -1)
  37.     {
  38.         Node[p].flag = true;
  39.         cnt++;
  40.         p = Node[p].next_ptr;
  41.     }
  42.     if(cnt == 0){   //  特判
  43.         printf("0 -1");  // 没有有效节点
  44.     }
  45.     else{
  46.         sort(Node,Node + maxn, cmp);
  47.         printf("%d %05d\n", cnt, Node[0].addr);
  48.         for(int i = 0; i < cnt; ++i){
  49.             // 防止-1被%05d化，提前判断
  50.             if(i != cnt - 1){
  51.                 printf("%05d %d %05d\n", Node[i].addr, Node[i].data, Node[i+1].addr);
  52.             }
  53.             else{
  54.                 printf("%05d %d -1\n", Node[i].addr, Node[i].data);
  55.             }
  56.         }
  57.     }
  58.     return 0;
  59. }