猪脚说第九期

老规矩：若针对这些题目，同学们有更好更简洁的方法，欢迎来找助教讨论，助教请喝奶茶😍😍。

题外话：同学们对前面的题解没有多大反应啊。也不知道有问题的同学看懂了没有。我们欢迎大家随时与我们讨论。事实上，进入栈和队列以及后续学习之后，编程题的思维难度并不大，只要弄清楚细节问题，其本质上都是相关数据结构的基本操作。

栈操作（栈-基本题）

本题是非常基础的栈操作题，主要目的是让大家熟悉栈的操作。基本的出栈、入栈操作可以封装成函数。

#include <stdio.h>
#define MAXSIZE 101
struct zhan{
    int num[MAXSIZE];
    int pointer;
}stem;
int pushzhan(struct zhan *s, int digit){
    if(s->pointer == MAXSIZE){
        printf("error ");
        return 0;
    }//如果栈满，则输出error
    s->pointer++;
    s->num[s->pointer]=digit;
    return 1;
}//入栈操作
int quitzhan(struct zhan *s){
    if(s->pointer == -1){
        printf("error ");
        return 0;
    }//若栈空
    int digit = s->num[s->pointer];
    s->pointer--;
    printf("%d ", digit);
    return 1;
}//出栈操作
int main() {
    int op, follow;
    stem.pointer=-1;//初始化栈顶
    while(1){
        scanf("%d", &op);
        if(op == -1)
            break;
        else if(op == 0)
            quitzhan(&stem);
        else if(op == 1){
            scanf("%d", &follow);
            pushzhan(&stem, follow);
        }
    }
    printf("\n");
    return 0;
}

C程序括号匹配检查

这道题其实是很基本的出、入栈操作练习题，难度不大，但要考虑的细节非常多，另外注意转义字符。
- 不处理括号：
  - 字符常量：'('
  - 字符串常量："( in string"
  - 单行注释：// ( in single-line comment
  - 多行注释：/* ( in multi-line comment */
- 错误优先级：
  - {}不能在()中
  - 右括号无匹配的左括号
  - 最后剩余为匹配的左括号
- 其他细节问题：
  - 保存括号的同时需要保存括号所在行数，或者使用count变量，每读一行count++，当读到第一个不匹配的括号时，直接跳出所有循环（因为该题中不匹配括号只有一个）进行输出，题解代码采取后一种思路。且需要注意：就算是多行注释或空行内容，行数也是要对应增加的
  - 应该使用一种方式（如另定义一个数组）存储所有括号，以便在全部匹配时进行输出
解释一下参考代码中的几个变量：
- isErr：是否错误（已判断出不匹配的字符）
- isStr1：是否在字符串中
- isStr2：是否在字符中
- isCmnt1：是否在单行注释中
- isCmnt2：是否在多行注释中

#include <stdio.h>
struct node{
    char ch;
    int line;
}st[210];//括号栈
int top = -1;
int main() {
    FILE *in = fopen("example.c", "r");
    struct node tmp;
    char s[201]={0}, save[201]={0}; //save数组记录已匹配的括号，用于最后输出
    int i, j, k=0, count=0, isErr=0, isStr1=0, isStr2=0, isCmnt1=0, isCmnt2=0;
    while(fgets(s,200,in)!=NULL && !isErr){//当前没有判断到未匹配符号时，才继续读入
        count++;//成功读入后，count再执行++操作
        for(j = 0; s[j]!='\0' && !isErr; j++){
            if(isStr1 && s[j] != '\"')
                continue;//如果在字符串或字符串常量中则跳过当前字符
            if(isStr2 && s[j] != '\'')
                continue;//如果在字符或字符常量中则跳过当前字符
            if(isCmnt1){
                isCmnt1 = 0;
                break;
            }//如果是单行注释则跳过本行
            if(isCmnt2 && (s[j] != '*' || s[j+1] != '/'))
                continue; //如果在多行注释中则跳过当前字符
            else
                isCmnt2 = 0;
            tmp.ch = s[j];
            tmp.line = count;
            switch (s[j]){
                case '(':
                    save[k++] = s[j];
                    st[++top] = tmp;
                    break;//左括号直接入栈
                case ')':
                    save[k++] = s[j];
                    if (top < 0 || st[top].ch != '('){
                        st[++top] = tmp;
                        isErr = 1;
                    }//由于每一对左、右小括号、左、右大括号已经弹出，因此右括号之前若还有除左括号之外的括号，则该右括号不匹配
                    else
                        top--;//右括号与左括号匹配成功，则右括号不入栈，同时弹出左括号
                    break;
                case '{':
                    save[k++] = s[j];
                    if (st[top].ch == '('){
                        isErr = 1;
                    }//大括号不能出现在小括号中
                    else
                        st[++top] = tmp;
                    break;
                case '}':
                    save[k++] = s[j];
                    if (top < 0 || st[top].ch != '{'){
                        st[++top] = tmp;
                        isErr = 1;
                    }
                    else
                        top--;//匹配成功，消除左、右大括号
                    break;
                case '\"':
                    isStr1 ^= 1;
                    break;
                case '\'':
                    isStr2 ^= 1;
                    break;//使用按位异或运算判断是否是成对的单引号或双引号
                case '/':
                    if (s[j+1] == '/')
                        isCmnt1 = 1;//单行注释
                    else if (s[j+1] == '*')
                        isCmnt2 = 1;//多行注释
                    break;
            }
        }
    }
    if (top >= 0)//栈顶即为未匹配字符
        printf("without maching \'%c\' at line %d", st[top].ch, st[top].line);
    else{
        for(i = 0; i < k; i++)
            printf("%c", save[i]);
    }
    printf("\n");
    return 0;
}

计算器（表达式计算-后缀表达式实现，结果为浮点）

中缀表达式转后缀表达式的模版题，这里直接给出一个模版，已封装成Change(char s[])函数
注意运算符优先级的问题，一定要认真学习转后缀的思想和方法
本题还可以将括号中的内容看作子表达式，采用递归的方法求值，且该递归思想常用于后缀转中缀
注意本题为浮点数运算，定义数据类型的时候一定要写对

#include <stdio.h>
#include <ctype.h>
#include <string.h>
int top=-1;
double num[201], ans[201];
char op[201];
void Change(char s[]){
    int i, j=0, stacktop=-1;
    char stack[201] = {0};
    for(i = 0; s[i] != '\0';){
        while(isdigit(s[i])){
            num[j] = num[j] * 10 + s[i++] - '0';
            if(!isdigit(s[i]))
                j++;
        }
        if(s[i] == '\0')
            break;
        if(s[i] == '(')
            stack[++stacktop] = s[i];
        else if(s[i] == '+' || s[i] == '-'){
            while(stacktop > -1){
                if(stack[stacktop] == '(')
                    break;
                else
                    op[j++] = stack[stacktop--];
            }
            stack[++stacktop] = s[i];
        }
        else if(s[i] == '*' || s[i] == '/'){
            while(stacktop > -1){
                if(stack[stacktop]=='('||stack[stacktop]=='+'||stack[stacktop]=='-')
                    break;
                else
                    op[j++] = stack[stacktop--];
            }
            stack[++stacktop] = s[i];
        }
        else if(s[i] == ')'){
            while(stack[stacktop] != '(')
                op[j++] = stack[stacktop--];
            stacktop--;
        }
        i++;
    }
    while(stacktop>-1)
        op[j++] = stack[stacktop--];
}//将一个中缀表达式s数组转化成后缀表达式；
 //数字存储在num中，运算符存储在op中，且按顺序存储，例如 1+2= 的存储方式为：
 //num[0]=1, num[1]='2', op[2]='+'
int main(int argc, const char * argv[]) {
    int i, j=0, k=0;
    char x[201]={0}, s[201]={0};
    gets(x);
    for(i = 0; x[i] != '\0'; i++){
        if(x[i] != ' ' && x[i] != '=')
            s[j++] = x[i];
    }//消除x数组中的空格，存储与s数组中
    s[j] = '\0';
    Change(s);
    for(i = 0; s[i] != '\0'; i++){
        if(num[i] != 0){
            top++;
            ans[top] = num[i];
        }
        else if(op[i] != '\0'){
            switch(op[i]){
                case '+':
                    ans[top-1] = ans[top-1] + ans[top];
                    break;
                case '-':
                    ans[top-1] = ans[top-1] - ans[top];
                    break;
                case '*':
                    ans[top-1] = ans[top-1] * ans[top];
                    break;
                case '/':
                    ans[top-1] = ans[top-1] / ans[top];
                    break;
            }
            ans[top] = 0;
            top--;
        }
        if(num[i] == 0 && op[i] == '\0')
            break;
    }//基于出、入栈思想对后缀表达式进行运算
    printf("%.2lf\n", ans[top]);
    return 0;
}

文本编辑操作模拟（简）

重大灾难区，~~助教看到这题就想吐~~，主要错误集中在：

最最最重要的！字符串操作不注意结束符'\0'，使用字符串处理库函数不知道使用规则
~~（究竟多难忘～眼中的对方～是火山呢还是一座宝藏～）——歌曲《最最重要》~~
~~一键查询助教精神状态~~
在插入和删除函数里定义了局部数组然后返回。局部数组是不可以作为函数的返回值的！！！如果要返回一个字符数组，则需使用malloc动态分配一块空间，这块空间可作为函数返回值
部分同学在插入和删除操作时，将记录操作子串的字符数组改变了。那么在执行撤销操作的时候，自然会出问题，推荐做法为将每一次操作的结果都保存在结构体数组中
需要注意，如果多次输入操作3（即撤销操作），需要判断是否已经没有操作可以撤销（此时应该什么都不变），因此此题最好还是使用栈实现，当栈为空时，什么操作都不执行即可

#include <stdio.h>
#include <string.h>
#define MAXSIZE 515
struct zhan{
    int op;
    int pos;
    char str[MAXSIZE];
    char final[MAXSIZE];
}oper[MAXSIZE];//str数组为操作时输入的字符串，final数组为当前操作完成后，应储存的总字符串；
               //oper数组中每一个元素都对应一次操作，无论是插入还是删除，只有撤销时才退栈
int Top=0;
void insert_oper(int pos, char str[]){
    int len;
    len = strlen(str);
    strcpy(oper[Top].final, oper[Top-1].final);
    strcpy(oper[Top].final+pos, str);
    strcpy(oper[Top].final+pos+len, oper[Top-1].final+pos);//请理解通过strcpy函数实现插入
}//插入操作
void delete_oper(int pos, int n){
    int len;
    len = strlen(oper[Top-1].final);
    if(n > len-pos)
        n = len-pos;//若需要删除的个数大于之后字符的总个数，则全部删完即可
    strcpy(oper[Top].final, oper[Top-1].final);
    strcpy(oper[Top].final+pos, oper[Top-1].final+pos+n);//请理解通过strcpy函数实现删除
    oper[Top].final[len-n] = '\0';//一定要注意'\0'的处理
}//删除操作
void return_insert_oper(int pos, int n){
    int len;
    len = strlen(oper[Top+1].final);
    strcpy(oper[Top].final, oper[Top+1].final);
    strcpy(oper[Top].final+pos, oper[Top+1].final+pos+n);
    oper[Top].final[len-n] = '\0';
}//撤销插入操作
void return_delete_oper(int pos, char str[]){
    int len;
    len = strlen(str);
    strcpy(oper[Top].final, oper[Top+1].final);
    strcpy(oper[Top].final+pos, str);
    strcpy(oper[Top].final+pos+len, oper[Top+1].final+pos);
}//撤销删除操作
int main() {
    char s[MAXSIZE]={0}, str1[MAXSIZE]={0};
    int i, n, op1, pos1, n1, len1;
    fgets(s, 515, stdin);
    scanf("%d", &n);
    for(i = 0; i < n; i++){
        Top++;
        scanf("%d %d %s", &oper[Top].op, &oper[Top].pos, oper[Top].str);
    }//将已经执行过的操作存储在结构体中
    strcpy(oper[Top].final, s);//此时栈顶操作完后，储存的总字符串即为s数组
    while(1){
        memset(str1, 0, sizeof(char));//一定要初始化！
        scanf("%d", &op1);
        if(op1 == -1){
            puts(oper[Top].final);//直接输出栈顶储存的总字符串，即为最终字符串
            break;
        }
        else if(op1 == 1){
            Top++;//除了撤销的操作，都入栈
            scanf("%d %s", &pos1, str1);
            insert_oper(pos1, str1);
        }
        else if(op1 == 2){
            Top++;//除了撤销的操作，都入栈
            scanf("%d %d", &pos1, &n1);
            delete_oper(pos1, n1);
        }
        else if(op1 == 3){
            if(Top == 0)
                continue;//若撤销之前本身没有任何操作，则什么都不用执行，直接continue
            else if(Top > n)//此时已存在现有操作，则直接退栈
                Top--;//执行撤销操作时，退栈
            else{//当没有任何现有操作而执行撤销时，则需逆向已有操作处理
                if(oper[Top].op == 1){
                    Top--;
                    len1 = strlen(oper[Top+1].str);
                    return_insert_oper(oper[Top+1].pos, len1);
                }
                else if(oper[Top].op == 2){
                    Top--;
                    return_delete_oper(oper[Top+1].pos, oper[Top+1].str);
                }
            }
        }
    }
    return 0;
}

银行排队模拟（生产者-消费者模拟）

这道题确实非常考验大家的理解能力，以及对细节的把握程度，以及对队列的掌握情况。

解决复杂的题目，实质上是一个翻译过程，即将题目表述和每一处细节翻译成代码，因此建议大家画流程图。

上面这张图非常完整地体现了该题的整个流程，如果还有不清楚的同学可以结合这张图想一想。易错点为：

在没有新客户来的时候，是不需要增加窗口的；在没有人接受服务的时候，是不需要减少窗口的
在减少窗口时，只考虑当前减少窗口的逻辑，而不需要考虑减少后的结果，否则将陷入死循环。例如当前有三个窗口，一共有25个人，25 / 3 > 7，这时需要增加窗口，但增加窗口后又考虑平均人数小于7而减少窗口是不必要的
所有客户全部到来后，之后的所有周期都是没有客户到来的，因此这些后续周期不能增加窗口；也有可能某些周期的所有窗口都正在服务复杂业务，导致没有新的客户接受服务，则此时是不需要减少窗口的
一个客户，不论他的业务类型需要被服务多少个周期，他的等待周期的计数在他接受服务的那一刻起就停止了，也就意味着，当前队列的等待人数是不包括正在接受服务的客户的
举一个例子，假设最后一个周期到来了5位客户，此时算上这5位客户，还在等待的人一共有38位。显然需要开设5个窗口。假设这些窗口都服务的是简单业务，则在当前周期结束后，等待的人数还有33人，此时应减少一个窗口，还剩下4个窗口。所以说，有些同学简单通过33 / 4 > 7来判断此时应该开5个窗口是错误的
另外，这道题对于窗口的增减确实比较繁琐，大家在编写代码时涉及到窗口增减的操作时，一定要注意是总开放窗口还是可用窗口。对于结构体来说，可以代表人，也可以代表窗口。

  #include <stdio.h>
  struct Node{
      int timein;//入队时间
      int timeout;//出对时间
      int type;//业务类型
  }people[801];
  int judge, front=0, rear=-1, window=3, win_able=3;
  void print(int i){
      int j;
      judge=0;//judge变量用于判断当前周期是否有客户接受服务
      for(j=0;j<win_able;j++){
          judge=1;//若有客户接受服务，则置为1
          if(rear+1==front)
              break;
          people[front++].timeout=i;//一旦客户接受服务，则等待时间的计数已经停止，至于他需要被服务多久，是不算进等待时间里的
          printf("%d : %d\n", front, i-people[front-1].timein);
      }//只有可用的窗口可以去服务用户
      win_able=window;
      for(j=0;j<front;j++){
          if(people[j].type>0)
              people[j].type--;
      }//过了一个周期，所有业务类型--
      for(j=0;j<front;j++){
          if(people[j].type>0){
              win_able--;
              if(win_able==0)
                  break;//可用窗口为0，则不用再--了
          }
      }//从最开始到现在为止接受过服务的人，有多少人类型不为0，则代表有多少个窗口是不可用的
  }
  int main() {
      int i, j, k=0, n, num[51]={0}, flag[51]={0};
      scanf("%d", &n);
      for(i=0;i<n;i++){
          scanf("%d", &num[i]);
          if(num[i]==0)
              flag[i]=1;
      }
      for(i=0;i<n;i++){
          for(j=0;j<num[i];j++)
              scanf("%d", &people[k++].type);
      }//先完成全部的输入数据的存储
      for(j=0;flag[j];j++);//找到第一个有客户到来的周期
      for(i=j;i<n;i++){
          for(k=0;k<num[i];k++)
              people[++rear].timein=i;//此客户的入队时间一定与当前大循环的循环变量值相同
          while(((rear-front+1)/window>=7)&&(window<5)&&(!flag[i])){
              window++;
              win_able++;
          }//判断是否需要开设新窗口，开设新窗口时，可用窗口也跟着变多，但不能超过5个
          print(i);
          while(((rear-front+1)/window<7)&&(window>3)&&judge){
              window--;
              win_able--;
          }//判断是否需要关闭窗口，但不能关闭已有窗口，即不能小于3个
      }//对每一个时间周期单独处理
      while(front<rear+1){
          print(i);
          while(((rear-front+1)/window<7)&&(window>3)&&judge){
              window--;
              win_able--;
          }
          i++;
      }//有客户到来的时间周期结束，还有在队列中的人，再进行出队操作
      return 0;
  }
  1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

## 函数调用关系

~~本题为2020级期末考试真题~~

本题难度并不大，主要坑点在题面中也已经用红字标注。

```C
#include <stdio.h>
#include <string.h>
struct function{
    char name[21];
    char division[11][21];
    int count;//该主函数下调用的函数的个数
}information[101];//主函数全部保存在结构体中，在结构体的division数组中，保存在该主函数下的调用函数
int top=-1, total=0;
int main(){
    int i, j, op;
    char stack[201][21]={0}, temp[21]={0};
    for(i=0;i<101;i++)
        information[i].count=0;//初始化所有主函数的count为0
    while(1){
        scanf("%d", &op);
        if(op==8){
            scanf("%s", temp);
            for(i=0;i<total;i++){
                if(strcmp(information[i].name,temp)==0)
                    break;
            }
            if(i==total)
                strcpy(information[total++].name,temp);//保存每一个非重复出现的函数
            if(top>=0){
                for(i=0;i<total;i++){
                    if(strcmp(information[i].name,stack[top])==0)
                        break;
                }//查看当前位于栈顶的函数在information数组中的具体位置
                for(j=0;j<information[i].count;j++){
                    if(strcmp(information[i].division[j],temp)==0)
                        break;
                }
                if(j==information[i].count){
                    strcpy(information[i].division[j],temp);
                    information[i].count++;
                }//查看当前输入的函数在栈顶函数中的存在性，若不存在，则将其加入栈顶函数的分函数
            }
            strcpy(stack[++top],temp);//将当前输入的函数入栈
        }
        else
            top--;//退栈
        if(top==-1)
            break;//栈空则退出循环
    }
    for(i=0;i<total;i++){
        if(information[i].count>0){
            printf("%s:", information[i].name);//输出含有分函数的主函数
            for(j=0;j<information[i].count-1;j++)
                printf("%s,", information[i].division[j]);//按调用顺序输出分函数
            printf("%s\n", information[i].division[j]);
        }
    }
    return 0;
}

Author: diandian, Riccardo