北航DS第四次作业——栈与队

北航这计算机老师感觉语文都不咋地，PPT思路讲不明白，一堆判断过程不说；题目巨冗长还写不清楚，甚至前后矛盾。

T1 栈操作基本题

#include<stdio.h>
int a[1000];
int shang,now;
int ding=-1;

int main(){
    scanf("%d",&now);
    while(now!=-1){
        if(now==0){
            if(ding>=0) printf("%d ",a[ding--]);
            else printf("error ");
        }else{
            if(shang==1){
                if(ding>=99){
                    printf("error ");
                }else{
                    a[++ding] = now;
                }
            }
        }
        shang = now;
        scanf("%d",&now);
    }
    return 0;
}

T2 计算器

问题描述

从标准输入中读入一个算术运算表达式，如：24 / ( 1 + 5/3 + 36 / 6 / 2 - 2) * ( 12 / 2 / 2 )= ，计算表达式结果，并输出。

要求：

1、表达式运算符只有+、-、*、/，表达式末尾的=字符表示表达式输入结束，表达式中可能会出现空格；
2、表达式中会出现圆括号，括号可能嵌套，不会出现错误的表达式；
3、表达式中出现的操作数都是十进制整数常量；但要求运算结果为浮点型，例如：5/2结果应为2.5。
4、要求采用逆波兰表达式来实现表达式计算。

输入形式

从键盘输入一个以=结尾的算术运算表达式。操作符和操作数之间可以有空格分隔。

输出形式

在屏幕上输出计算结果，小数点后保留两位有效数字。

样例输入

24 / ( 1 + 5/3 + 36 / 6 / 2 - 2) * ( 12 / 2 / 2 ) =

样例输出

19.64

样例说明

按照运算符及括号优先级依次计算表达式的值。

部分思路

//示例代码
if(shuru[i]=='*'||shuru[i]=='/'){
                    while(zhanlen>=0){
                        if(zhan[zhanlen]=='+'||zhan[zhanlen]=='-'||zhan[zhanlen]=='*'||zhan[zhanlen]=='/'){
                            if(zhan[zhanlen]=='+'||zhan[zhanlen]=='-') break;
                            shizi[++slen] = zhan[zhanlen--];
                            break;
                        }else{
                            if(zhan[zhanlen]=='('){
                                break;
                            }
                            shizi[++slen] = zhan[zhanlen--];
                        }
                    }
                }

题解代码

#include<stdio.h>
#include<string.h>
#include<ctype.h>

char shuru[99999999],shizi[99999999];
char zhan[99999999];
int zhanlen=-1;
double ans[99999999];
int anslen = -1;

int main(){
    gets(shuru);
    int len = strlen(shuru);
    int slen = -1;//shizi的长度
    int panduan = 0;
    for(int i=0;i<=len;i++){
        if(shuru[i]==' '||shuru[i]=='=') continue;
        if(isdigit(shuru[i])){
            shizi[++slen] = shuru[i];
            panduan = 1;
        }else{
            if(panduan == 1){
                shizi[++slen] = ' ';
                panduan = 0;
                if(i==len) break;
            }
            if(shuru[i]==')'){
                while(zhanlen>=0){
                    if(zhan[zhanlen]=='('){
                        zhanlen--;
                        break;
                    }else{
                        shizi[++slen] = zhan[zhanlen--];
                    }
                }
            }else{
                if(shuru[i]=='+'||shuru[i]=='-'){
                    while(zhanlen>=0){
                        if(zhan[zhanlen]=='+'||zhan[zhanlen]=='-'){
                            shizi[++slen] = zhan[zhanlen--];
                            break;
                        }else{
                            if(zhan[zhanlen]=='('){
                                break;
                            }
                            shizi[++slen] = zhan[zhanlen--];
                        }
                    }
                }else if(shuru[i]=='*'||shuru[i]=='/'){
                    while(zhanlen>=0){
                        if(zhan[zhanlen]=='+'||zhan[zhanlen]=='-'||zhan[zhanlen]=='*'||zhan[zhanlen]=='/'){
                            if(zhan[zhanlen]=='+'||zhan[zhanlen]=='-') break;
                            shizi[++slen] = zhan[zhanlen--];
                            break;
                        }else{
                            if(zhan[zhanlen]=='('){
                                break;
                            }
                            shizi[++slen] = zhan[zhanlen--];
                        }
                    }
                }
                zhan[++zhanlen] = shuru[i];
            }
        }
    }
    while(zhanlen>=0){
        shizi[++slen] = zhan[zhanlen--];
    }
    long long shuzi = -1;
    for(int i=0;i<=slen;i++){
        if(isdigit(shizi[i])){
            if(shuzi == -1){
                shuzi = shizi[i] - '0';
            }else{
                shuzi *= 10;
                shuzi += shizi[i] - '0';
            }
        }
        else if(shizi[i]==' '){
            if(shuzi != -1) {
                ans[++anslen] = (double)shuzi;
                shuzi = -1;
            }
        }else{
            double b;
            if(shizi[i]=='*'){
                b = ans[anslen] * ans[anslen-1];
                anslen --;
                ans[anslen] = b; 
            }else if(shizi[i]=='/'){
                b = ans[anslen-1] / ans[anslen];
                anslen --;
                ans[anslen] = b; 
            }else if(shizi[i]=='+'){
                b = ans[anslen-1] + ans[anslen];
                anslen --;
                ans[anslen] = b; 
            }else if(shizi[i]=='-'){
                b = ans[anslen-1] - ans[anslen];
                anslen --;
                ans[anslen] = b; 
            }
        }
    }
    printf("%.2lf",ans[anslen]);
    return 0;
}

T3 函数调用关系

问题描述

给定某能正常运行结束的用户函数调用栈信息（当一个函数被调用时将入栈，当调用返回时，将出栈）。编写程序，对函数调用栈信息进行分析，依据函数入栈和出栈信息，分析函数调用关系，即一个函数调用了哪些不同函数。并按运行时调用序输出调用关系。

说明：

1. 在一个函数中，同一函数有可能被调用多次，输出调用关系时只输出一次；若一个函数没有调用其它函数，则不输出调用关系；
2. 函数运行时调用序是指函数在调用栈中的出现序。
3. 程序中不存在递归调用。函数名符合C语言标识符的规定，函数名长度不超过20，每个函数最多调用不超过10个不同函数，程序中用户定义的函数个数不超过100。

算法提示：当一个函数入栈时，它就是当前栈顶函数调用的一个函数。

输入形式

假设用8表示函数入栈操作；用0表示当前函数出栈。当操作为8（入栈）时，输入形式为：

<操作> <函数名>

当操作为0（出栈）时，输入形式为：

<操作>

所有入栈操作和出栈操作都是从标准输入分行输入，假设调用栈中函数个数最多不超过200。开始时，调用栈为空，当调用栈再次为空时，输入结束。

输出形式

按运行时调用先后顺序输出函数调用关系到标准输出，每行为一个函数的调用关系信息，包括：函数名及被调用函数，函数与被调用函数间用一个英文冒号“:”分隔，被调用函数间用一个英文逗号“,”分隔，最后一个函数名后跟一个回车。若一个函数没有调用其它函数，则不输出。

样例输入

8 main
8 input
0
8 mysqrt
0
8 findA
0
8 findB
8 area
8 mysin
0
8 mycos
0
8 mysqrt
0
0
0
8 findC
8 area
8 mysin
0
0
8 mysqrt
8 max
0
0
0
8 output
0
0

样例输出

main:input,mysqrt,findA,findB,findC,ouput
mysqrt:max
findB:area
area:mysin,mycos,mysqrt
findC:area,mysqrt

样例说明

按照运行时调用函数的先后顺序，依次输出了main、mysqrt、findB、area和findC的函数调用关系。其中main函数调用了6个函数，按照运行时调用序依次输出。注意：mysqrt函数先于findB等函数出现在栈中，虽然mysqrt调用max较晚，但要先输出其调用关系。

题解代码

#include<stdio.h>
#include<string.h>
#include<ctype.h>

typedef struct fuct{
    char name[25];
    int sum;
    int dy[12];
}f;
f fuc[109];
int fnum = -1;//fnum初始为-1,0是1个

int zhan[399];
int ding = -2;

int find(char s[]){
    for(int i=0;i<=fnum;i++){
        if(strcmp(fuc[i].name,s)==0){
            return i;
        }
    }
    return -1;
}

int main(){
    int op;
    char s[25];
    while(ding!=-1){
        if(ding==-2){
            ding=-1;
        }
        scanf("%d",&op);
        if(op==8){
            ding++;
            scanf(" %s",s);
            int p = find(s);//p是当前字符串的位置
            if(p==-1){
                fnum++;
                strcpy(fuc[fnum].name,s);
                fuc[fnum].sum = 0;
                p = fnum;
            }
            if(ding!=0){
                fuc[zhan[ding-1]].sum++;
                int yep=0;
                for(int z=1;z<=fuc[zhan[ding-1]].sum-1;z++){
                    if(fuc[zhan[ding-1]].dy[z]==p) yep=1;
                }
                if(yep==0) fuc[zhan[ding-1]].dy[fuc[zhan[ding-1]].sum] = p;
                else fuc[zhan[ding-1]].sum--;
                zhan[ding] = p;
            }else{
                zhan[ding] = p;
            }
        }else if(op==0){
            ding--;
        }
    }
    for(int i=0;i<=fnum;i++){
        if(fuc[i].sum!=0){
            printf("%s:",fuc[i].name);
            int j;
            for(j=1;j<fuc[i].sum;j++){
                printf("%s,",fuc[fuc[i].dy[j]].name);
            }
            printf("%s",fuc[fuc[i].dy[j]].name);
            printf("\n");
        }
    }
    return 0;
}

T4 文本编辑操作模拟

问题描述

编写一程序模拟文本编辑操作。首先从标准输入读取一行字符串（字符个数不超过512），该行字符串是已经过n（大于0，小于等于10）步编辑操作后的结果。然后从下一行读取n，以及已发生过的n步编辑操作，编辑操作分行输入，输入格式为：

op pos str

其中op为编辑操作命令编码（在此只有插入和删除操作，1表示插入或2表示删除操作）；pos表示插入或删除的位置；str表示已经插入或删除的字符串（中间没有空格）。各数据间以一个空格分隔。

然后在空一行后，再分行输入当前将要进行的编辑操作，包括如下四种操作（操作编码分别为：1表示插入，2表示删除操作，3表示撤销（即undo操作），-1表示结束）：

1 pos str

表示将在pos位置插入字符串str（中间没有空格），各数据间以一个空格分隔；

2 pos n

表示将从pos位置开始删除n个字符（各数据间以一个空格分隔），若要删除的字符个数多于已有字符个数（即在文本中从pos开始的字符个数小于n），则按实际字符数删除即可。（提示：为了能够撤销删除操作，应按“2 pos str”形式保存命令。）

表示撤销最近执行的插入或删除操作，可以进行多次撤销操作，注意：也可以撤销之前已经发生过的n步编辑操作中的操作。

-1

表示退出编辑操作，在屏幕上输出最终编辑后的文本。

要求：

1、上述所有输入的编辑操作中的字符串str都不包含空白字符（空格符、制表符或换行符）；
2、插入操作中的位置pos大于等于0，并且小于等于当前文本的字符个数；0位置表示文本第一个字符的位置；若pos为当前文本的字符个数，则表示在文本最后插入字符串；
3、删除操作中的位置pos大于等于0，并且小于当前文字的字符个数；
4、若已无操作可撤销，则再进行撤销操作无效；
5、文本在编辑过程中，总字符个数不会超过512。

输入形式

先从键盘输入一行字符串，表示已经经过n步编辑操作后的文本串，然后在下一行输入一个正整数n，并分行输入n步插入或删除操作（表示按时间先后顺序已进行的操作），格式如上所述。随后空一行，再分行输入将要进行的编辑操作，格式如上所述。直到输入-1操作为止。

输出形式

在屏幕上输出最终编辑后的文本内容。

样例输入

A Stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle.???
4
1 20 ainer
2 0 ???
1 85 -
1 99 (LIFO)
3
2 110 10
1 110 Objects
2 98 1
2 0 1
2 108 10
3
3
3
-1

样例输出

A Stack is a container of objects that are inserted and removed according to the last-in first-out  principle.Objects

样例说明

第一行输入的文本串是先后经过下面4次编辑操作后得到的：先在20位置插入了字符串ainer，然后删除了开始位置的字符串???，随后在85位置插入了一个字符-，最后在99位置插入了字符串(LIFO)。

随后输入了撤销操作，即撤销先前最后进行的“1 99 (LIFO)”操作，也就是将99位置的6个字符删除；

2 110 10：将文本串最后的字符串???删除；

1 110 Objects：在文本串末尾插入字符串Objects；

随后执行了三次删除操作，又执行了三次撤销操作，最后输入的-1表示编辑操作结束，在屏幕上输出最终编辑后的文本串。

题解代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char s[513];
typedef struct {
    int op;
    int pos;
    char str[513];
} opt;
opt stack[1024];
int top = -1;

void insert(int pos, char *str) {
    top++;
    stack[top].op = 1;
    stack[top].pos = pos;
    strcpy(stack[top].str, str);
    char temp[513] = {0};
    strncpy(temp, s, pos);
    strcat(temp, str);
    strcat(temp, s + pos);
    strcpy(s, temp);
}

void delete(int pos, int n) {
    int len = strlen(s);
    if (pos >= len) return;
    int end = pos + n;
    if (end > len) end = len;
    char deleted[513] = {0};
    strncpy(deleted, s + pos, end - pos);
    top++;
    stack[top].op = 2;
    stack[top].pos = pos;
    strcpy(stack[top].str, deleted);
    char temp[513] = {0};
    strncpy(temp, s, pos);
    strcat(temp, s + end);
    strcpy(s, temp);
}

void undo() {
    if (top == -1) return;
    opt op = stack[top--];
    if (op.op == 1) {
        int len = strlen(op.str);
        char temp[513];
        strncpy(temp, s, op.pos);
        strncpy(temp + op.pos, s + op.pos + len, strlen(s) - op.pos - len + 1);
        strcpy(s, temp);
    } else {
        char temp[513] = {0};
        strncpy(temp, s, op.pos);
        strcat(temp, op.str);
        strcat(temp, s + op.pos);
        strcpy(s, temp);
    }
}

int main() {
    fgets(s, 513, stdin);
    s[strcspn(s, "\n")] = '\0';
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int op, pos;
        char str[513];
        scanf("%d %d %s", &op, &pos, str);
        top++;
        stack[top].op = op;
        stack[top].pos = pos;
        strcpy(stack[top].str, str);
    }
    int cmd;
    while (scanf("%d", &cmd) == 1 && cmd != -1) {
        if (cmd == 1) {
            int pos;
            char str[513];
            scanf("%d %s", &pos, &str);
            insert(pos, str);
        } else if (cmd == 2) {
            int pos, num;
            scanf("%d %d", &pos, &num);
            delete(pos, num);
        } else if (cmd == 3) {
            undo();
        }
    }
    printf("%s\n", s);
    return 0;
}

T5 银行排队模拟（生产者-消费者模拟） - 分类别

此题目尤其锻炼语文阅读理解能力。

问题描述

一个系统模仿另一个系统行为的技术称为模拟，如飞行模拟器。模拟可以用来进行方案论证、人员培训和改进服务。计算机技术常用于模拟系统中。

生产者-消费者（Server-Custom）是常见的应用模式，见于银行、食堂、打印机、医院、超市等提供服务和使用服务的应用中。这类应用的主要问题是消费者如果等待（排队）时间过长，会引发用户抱怨，影响服务质量；如果提供服务者（服务窗口）过多，将提高运管商成本。（经济学中排队论）

假设某银行网点有五个服务窗口，分别为三个对私、一个对公和一个外币窗口。银行服务的原则是先来先服务。通常对私业务人很多，其它窗口人则较少，可临时改为对私服务。假设当对私窗口等待服务的客户（按实际服务窗口）平均排队人数超过（大于或等于）7人时，等待客户将可能有抱怨，影响服务质量，此时银行可临时将其它窗口中一个或两个改为对私服务，当平均排队客户少于7人时，将立即恢复原有业务。设计一个程序用来模拟银行服务。

说明：

1. 增加服务窗口将会增加成本或影响其它业务，因此，以成本增加或影响最小为原则来增加服务窗口，即如果增加一个窗口就能使得按窗口平均等待服务人数小于7人，则只增加一个窗口。一旦按窗口平均等待服务人数小于7人，就减少一个所增加的窗口。
2. 为了简化问题，假设新到客户是在每个服务周期开始时到达。
3. 根据客户业务服务时间将客户分为3类：1（简单业务）、2（普通业务）、3（复杂业务），分别对应花费1-3个时间周期。
4. 当等待服务人数发生变化时（新客户到达或有客户已接受服务），则及时计算按实际服务窗口平均等待服务人数，并按相应策略调整服务窗口数（增加或减少额外的服务窗口，但对私窗口不能减少）。注意：只在获取新客户（不管到达新客户数是否为0）时，才按策略调整服务窗口数。进一步讲，增加服务窗口只在有客户到达的周期内进行（也就是说增加窗口是基于客户的感受，银行对增加窗口是不情愿的，因为要增加成本，一旦不再有新客户来，银行是不会再增加服务窗口的）；一旦有客户去接受服务（即等待客户减少），银行将根据策略及时减少服务窗口，因此，在每个周期内，有客户去接受服务后要马上判断是否减少服务窗口（因为能减少成本，银行是积极的）。
5.服务窗口的类别不固定，即：对私服务窗口也可根据需要转为对公或外币窗口。

本问题中假设对公和对外币服务窗口在改为对私服务时及服务期间没有相应因公或外币服务新客户到达（即正好空闲），同时要求以增加成本或影响最小为前提，来尽最大可能减少对私服务客户等待时间。

输入形式

首先输入一个整数表示时间周期数，然后下一行输入每个时间周期到达的客户人数；再依次分行输入每个时间周期到达的因私业务的客户类别。注：一个时间周期指的是银行处理一笔业务的平均处理时间，可以是一分钟、三分钟或其它。每行中的整数之间以一个空格分隔。

例如：

6
2 5 8 11 15 6
1 3
2 2 1 3 2
........

说明：共有6个时间周期，第1个周期来了2个客户（序号分别为1、2，业务分别为简单业务和复杂业务），第2个时钟周期来了5人（序号分别为3、4、5、6、7，业务分别为普通业务、普通业务、简单业务、复杂业务和普通业务），以此类推。

输出形式

每个客户等待服务的时间周期数。输出形式如下：

用户序号 : 等待周期数

说明：客户序号与等待周期数之间用英文冒号:分隔，冒号（:）两边各有一个空格，等待周期数后直接为回车。

样例输入

4
2  5  13  11
1 3
2 2 1 3 2
1 1 1 1 3 3 2 2 1 2 3 1 1
3 3 2 1 3 1 1 3 1 3 3

样例输出

样例说明

样例输入表明有四个时间周期，第一个周期来了2人（序号1-2）；第二个周期来了5人（序号3-7）；第三个周期来了13人（序号8-20）；第四个周期来了11人（序号21-31）。由于第一个时间周期内只来了2人，银行（有三个服务窗口）能及时提供服务，因此客户等待时间为0；第二个时间周期内来了5人，银行一个周期内一次只能服务3人，而且第一个周期内有一位办理复杂业务的客户，所以这时只有两个空闲窗口可以提供服务，前2人等待时间为0，另外3人需要等待；其它类推。

题目思路

//主要算法：
for(clock=1; ; clock++){//在每个时间周期内（下面用的是i代替clock）
  if(客户等待队列⾮空)//!isnull()
    将每个客户的等待时间增加⼀个时间单元；
  if(clock <= simulationtime且有新用户进入)//i<=t&&clowd[i]>0
    如果有新客户到来（从输⼊中读⼊本周期内新来客户数），将其⼊队；//读入到数组里，且把指针压到队列里
    根据等待服务客户数重新计算服务窗⼝数；//double类型平均值大于等于7.0则增加窗口，并循环
  if(客户等待队列⾮空)
    先排序一下，看看哪些窗口空着；//sort函数
    从客户队列中取（出队）相应数⽬（按实际服务窗⼝数）客户获得服务；
    然后根据等待服务客户数重新计算服务窗⼝数；
  else 结束模拟
 }

题解代码

#include<stdio.h>
int t;//周期
int clowd[1000];
int nowid = 0;

typedef struct people{
    int id;
    int type;
    int time;
}pp,*ptr;

pp p[999999];
ptr dui[999999];
int tou = 0;
int wei = -1;

int isnull(){
    if(tou-wei>0) return 1;
    return 0;
}

int chuang[6] = {0,0,0,0,0,0};
int cks = 3;
int sort(){
    for(int i=1;i<=5;i++){
        for(int j=1;j<=4;j++){
            if(chuang[j]<chuang[j+1]){
                int temp = chuang[j];
                chuang[j] = chuang[j+1];
                chuang[j+1] = temp;
            }
        }
    }
    int sum = 0;
    for(int i=1;i<=cks;i++){
        if(chuang[i]==0){
            sum++;
        }
    }
    return sum;
}

int main(){
    scanf("%d",&t);
    for(int i=1;i<=t;i++){
        scanf("%d",&clowd[i]);
    }
    for(int i=1;;i++){
        for(int j=1;j<=5;j++){
            if(chuang[j]>0) chuang[j]--;
        }
        if(!isnull()){
            for(int j=tou;j<=wei;j++){
                dui[j]->time++;
            }
        }
        if(i<=t&&clowd[i]>0){
            for(int j = 1;j<=clowd[i];j++){
                nowid++;
                p[nowid].id = nowid;
                p[nowid].time = 0;
                scanf("%d",&p[nowid].type);
                wei++;
                dui[wei] = &p[nowid];
            }
            int ren = wei - tou + 1;
            double avr = (double)ren/cks;
            while(avr>=7.0f&&cks<5){
                cks++;
                avr = (double)ren/cks;
            }
        }
        if(!isnull()){
            int kong = sort();
            for(int j=cks-kong+1;j<=cks;j++){
                chuang[j] = dui[tou++]->type;
                if(isnull()) break;
            }
            int ren = wei - tou + 1;
            double avr = (double)ren/cks;
            while(avr<7.0f&&cks>3){
                cks--;
                avr = (double)ren/cks;
            }
        }else{
            if(i>t) break;
        }
    }
    for(int i=1;i<=nowid;i++){
        printf("%d : %d\n",p[i].id,p[i].time);
    }
    return 0;
}

T6(附加) C程序括号匹配检查

问题描述

编写一程序检查C源程序文件中{}、()等括号是否匹配,并输出第一个检测到的不匹配的括号及所对应括号所在的行号（程序中同一类括号只有一个不匹配）。

注意：

1.除了括号可能不匹配外，输入的C源程序无其它语法错误。
2.字符常量、字符串常量及注释中括号不应被处理，注释包括单行注释//和多行/* */注释
3.字符常量和字符串常量中不包含转义字符\'和\"；
4.程序中出现有意义括号的个数不超过200个；

不匹配判断规则：

1.当检测的程序括号为'{'时，若其前序尚未匹配的括号为'('时，输出该'('左括号及所在行号；
2.当遇到一个不匹配的右括号')'或'}'时，输出该右括号及所在行号；
3.当程序处理完毕时，还存在不匹配的左括号时，输出该左括号及所在行号。

输入形式

打开当前目录下文件example.c，查询其括号是否匹配。该文件中每行字符数不超过200。

输出形式

若存在括号不匹配时，应输出首先能判断出现不匹配的括号及其所在的行号。当出现括号不匹配时，按下面要求输出相关信息：

without maching <x> at line <n>

其中<x>为‘{’, ‘}’， ‘(’, ‘)’等符号，<n>为该符号所在的行号。

若整个程序括号匹配，则按下面所示顺序输出括号匹配情况，中间没有空格。

(){(()){}}

样例输入1

若当前目录下输入文件example.c中内容如下：

#include<stdio.h>
int main(){
printf("{ hello world }\n"); // }
)

样例输出1

without maching ')' at line 4

样例输入2

若当前目录下输入文件example.c中内容如下：

#include<stdio.h>
int main(){
printf("{ hello world }d\n"); /* }*/

样例输出2

without maching '{' at line 2

样例输入3

若当前目录下输入文件example.c中内容如下：

#include<stdio.h>
int main(){
printf("{ hello world }d\n"); /* }*/
}

样例输出3

(){()}

样例说明

样例1：在注释部分和字符串中的括号不考虑，在将程序处理之后得到的括号序列是（）{（）），遇到右括号时与最近的左括号匹配，发现最后一个小括号和大括号不匹配。

样例2：处理之后的括号序列是（）{（），在最后缺少了右大括号，那么应该输出与之相对应的左括号不匹配。

题解代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>

FILE *in;
char kuohao[999999];
int hangshu[999999];
int len = 0;
int hang = 1;

char zhan[999999];
int zhanshu[999999];
int ding = -1;

int main(){
    in = fopen("example.c", "r");
    int ct = (int)fgetc(in);
    char c = (char)ct;
    int state = 0;
    while(ct!=EOF){
        //printf("%c",c);
        if(c=='\n') hang++;
        if(state==1){
            if(c=='\n'){
                state = 0;
            }
        }else if(state==2){
            if(c=='*'){
                state=3;
            }
        }else if(state==3){
            if(c=='/'){
                state=0;
            }else if(c!='*'){
                state = 2;
            }
        }else if(state==4){
            if(c=='\''){
                state=0;
            }
        }else if(state==5){
            if(c=='\"'){
                state=0;
            }
        }else{
            if(c=='/'){
                if(state==-1){
                    state = 1;
                }else{
                    state = -1;
                }
            }else if(c=='*'){
                if(state==-1){
                    state = 2;
                }
            }else{
                if(state==-1){
                    state = 0;
                }
                if(c=='\''){
                    state = 4;
                }else if(c=='\"'){
                    state = 5;
                }
            }
            if(state==0){
                if(c=='{'||c=='}'||c=='('||c==')'){
                    kuohao[++len] = c;
                    hangshu[len] = hang;
                }
            }
        }
        ct = (int)fgetc(in);
        c = (char)ct;
    }
    // for(int i=1;i<=len;i++){
    //     printf("%c",kuohao[i]);
    // }
    for(int i=1;i<=len;i++){
        if(ding<0){
            zhan[++ding] = kuohao[i];
            zhanshu[ding] = hangshu[i];
            if(kuohao[i]==')'||kuohao[i]=='}'){
                printf("without maching '%c' at line %d\n",kuohao[i],hangshu[i]);
                return 0;
            }
        }else{
            char zd = zhan[ding];
            if(kuohao[i]==')'){
                if(zd=='('){
                    ding--;
                }else{
                    printf("without maching '%c' at line %d\n",kuohao[i],hangshu[i]);
                    return 0;
                }
            }else if(kuohao[i]=='}'){
                if(zd=='{'){
                    ding--;
                }else{
                    printf("without maching '%c' at line %d\n",kuohao[i],hangshu[i]);
                    return 0;
                }
            }else if(kuohao[i]=='('){
                zhan[++ding] = kuohao[i];
                zhanshu[ding] = hangshu[i];
            }else if(kuohao[i]=='{'){
                if(zd=='('){
                    printf("without maching '%c' at line %d\n",zhan[ding],zhanshu[ding]);
                    return 0;
                }else{
                    zhan[++ding] = kuohao[i];
                    zhanshu[ding] = hangshu[i];
                }
            }
        }
    }
    if(ding>=0){
        printf("without maching '%c' at line %d\n",zhan[0],zhanshu[0]);
    }else{
        for(int i=1;i<=len;i++){
            printf("%c",kuohao[i]);
        }
    }
    return 0;
}

T7(附加) Web浏览

这题上课写的，写的完全屎山

问题描述

一般的浏览器都可以通过“后退”或“前进”查看历史访问记录，编写程序模拟实现该功能，并统计浏览爱好（即：访问次数最多的网站）。

假设浏览器缺省打开的网页为：https://www.baidu.com/，（即：打开浏览器第一个访问的网页都是https://www.baidu.com/）。

输入的网页地址格式只有两种：

（1）https://....../ 表示某网站地址，网站名为位于“https://”和“/”之间的字符串，例如：www.buaa.edu.cn
（2）https://....../.../.../...... 表示某网站下的网页地址，例如：https://www.buaa.edu.cn/bhgk/jrbh.htm

上述两种格式都是以“https://”开始，且网页地址中没有空白符，最多不超过80个字符。

为了实现该功能，假设有两个栈存放网页访问历史记录：“后退栈”和“前进栈”，这两个栈初始都为空，其作用见输入形式中描述。

输入形式

从控制台输入如下命令和网页地址：

VISIT：表示访问某网页，该命令与后面网页地址间以一个空格分隔；其功能是：先将当前网页压入“后退栈”，然后将VISIT后的网页地址指定为新的当前网页，同时清空“前进栈”。所输入的网页地址格式只有上述两种，且输入的网页地址与当前网页地址是不同的。该命令个数少于100。

<<：由两个英文小于字符组成，中间无空格；表示后退命令，其功能是：先将当前网页压入“前进栈”，然后从“后退栈”弹出网页，使其成为新的当前网页。如果执行该命令前“后退栈”为空，则忽略该命令（即当前网页、“前进栈”、“后退栈”都不变）。“后退栈”最多能存入100个网页，且不会满。

>>：由两个英文大于字符组成，中间无空格；表示前进命令，其功能是：先将当前网页压入“后退栈”，然后从“前进栈”弹出页面，使其成为新的当前页面。如果执行该命令前“前进栈”为空，则忽略该命令（即当前网页、“前进栈”、“后退栈”都不变）。“前进栈”最多能存入100个网页，且不会满。

QUIT：表示退出浏览器，后跟参数1或0，QUIT和参数间以一个空格分隔。其后参数若为1：表示只输出所浏览过的网页；其后参数若为0：表示除输出所浏览过的网页外，还要输出浏览次数最多的网站和浏览次数。

输出形式

按行输出所浏览过的网页，若QUIT后参数为0，还要输出浏览次数最多的网站名和浏览次数，网站名定义见上述“问题描述”中网页地址格式（1），网站名和浏览次数之间以一个空格分隔。浏览次数最多的网站不会出现多个。

样例输入

VISIT https://www.buaa.edu.cn/
VISIT https://www.taobao.com/
<<
<<
<<
>>
VISIT https://www.buaa.edu.cn/jgsz/jxkyjg.htm
<<
<<
>>
>>
>>
QUIT 0

样例输出

https://www.baidu.com/
https://www.buaa.edu.cn/
https://www.taobao.com/
https://www.buaa.edu.cn/
https://www.baidu.com/
https://www.buaa.edu.cn/
https://www.buaa.edu.cn/jgsz/jxkyjg.htm
https://www.buaa.edu.cn/
https://www.baidu.com/
https://www.buaa.edu.cn/
https://www.buaa.edu.cn/jgsz/jxkyjg.htm
www.buaa.edu.cn 7

样例说明

初始浏览器打开的当前网页为https://www.baidu.com/，“前进栈”和“后退栈”都为空，然后依次执行输入的命令：

1、前两个为访问命令，先将https://www.baidu.com/和https://www.buaa.edu.cn/分别压入“后退栈”，同时分别访问网页https://www.buaa.edu.cn/和https://www.taobao.com/；
2、执行两个“后退”命令：先将https://www.taobao.com/和https://www.buaa.edu.cn/分别压入“前进栈”，同时分别访问“后退栈”弹出的网页https://www.buaa.edu.cn/和https://www.baidu.com/；
3、第五个命令为“后退”命令，此时“后退栈”为空，忽略该命令；
4、第六个命令为“前进”命令，先将https://www.baidu.com/压入“后退栈”，同时访问“前进栈”弹出的网页https://www.buaa.edu.cn/；
5、第七个命令为访问命令，先将网页https://www.buaa.edu.cn/压入“后退栈”，同时访问网页https://www.buaa.edu.cn/jgsz/jxkyjg.htm，并清空“前进栈”；

后面的“后退”和“前进”命令同上。

最后输入退出命令，后跟参数0，表示先按时间序依次输出浏览器访问过的网页，并且要统计输出访问次数最多的网站，网站www.buaa.edu.cn访问次数最多，为7次。若后跟参数为1，则只输出访问过的网页。

题解代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
typedef struct wangye{
    char url[300];
    int num;
}wy;
wy all[3999];
int allsum = 0;

wy aaa[3999];
int aaasum = 0;

int chai(int i){
    char *ss = all[i].url + 8;
    char *sss;
    for(sss=ss;*(sss)!='/';sss++){
    }
    *sss = '\0';
    char ab[300];
    strcpy(ab,ss);
    strcpy(all[i].url,ab);
}

int find(char s[]){
    for(int i=1;i<=allsum;i++){
        if(strcmp(s,all[i].url)==0){
            return i;
        }
    }
    return 0;
}

int find2(char s[]){
    for(int i=1;i<=aaasum;i++){
        if(strcmp(s,aaa[i].url)==0){
            aaa[i].num++;
            return i;
        }
    }
    return 0;
}

int qian[99999],hou[99999];
int qtou=0,qwei=-1,htou=0,hwei=-1;

int history[99999];
int hlen = 0;

int main(){
    char a[999];
    strcpy(all[++allsum].url,"https://www.baidu.com/");
    all[allsum].num++;
    //hou[++hwei] = allsum;
    history[++hlen] = allsum;
    int dangqian = 1;
    while(1){
        gets(a);
        int w;
        if(a[0]=='Q'){
            for(int i=1;i<=hlen;i++){
                printf("%s\n",all[history[i]].url);
            }
            if(a[5]=='0'){
                for(int i=1;i<=allsum;i++){
                    chai(i);
                }
                for(int i=1;i<=hlen;i++){
                    if(find2(all[history[i]].url)==0){
                        aaasum++;
                        strcpy(aaa[aaasum].url,all[history[i]].url);
                        aaa[aaasum].num++;
                    }
                }
                int max = 0,maxi;
                for(int i=1;i<=aaasum;i++){
                    if(aaa[i].num>max){
                        maxi = i;
                        max = aaa[i].num;
                    }
                }
                printf("%s %d",aaa[maxi].url,max);
            }
            break;
        }else if(a[0]=='V'){
            char *aa = a + 6;
            w = find(aa);
            if(w==0){
                strcpy(all[++allsum].url,aa);
                w = allsum;
            }
            all[w].num++;
            qtou = 0;
            qwei = -1;
            if(hwei-htou+1==100){
                htou++;
                hwei++;
                hou[hwei] = dangqian;
            }else{
                hou[++hwei] = dangqian;
            }
            history[++hlen] = w;
            dangqian = w;
        }else if(a[0]=='<'){
            if(htou-hwei>0){
                continue;
            }else{
                hwei--;
                w = hou[hwei+1];
                history[++hlen] = w;
                if(qwei-qtou+1==100){
                    qtou++;
                    qwei++;
                    qian[qwei] = dangqian;
                }else{
                    qian[++qwei] = dangqian;
                }
                dangqian = w;
            }
        }else if(a[0]=='>'){
            if(qtou-qwei>0){
                continue;
            }else{
                qwei--;
                w = qian[qwei+1];
                history[++hlen] = w;
                if(hwei-htou+1==100){
                    htou++;
                    hwei++;
                    hou[hwei] = dangqian;
                }else{
                    hou[++hwei] = dangqian;
                }
                dangqian = w;
            }
        }
    }
    return 0;
}

T8(附加) 火车货运调度模拟

问题描述

某火车货场由A、B、C三段组成，见下图。现有一列货车停在A段上，由多个货物车厢组成，每节车厢信息包括编号和货物发往的目的地（车厢编号是唯一的，各节车厢发往的目的地可以相同，也可以不同）。当前停在A段的货车车厢发往目的地编组是乱的，需要按目的地由远至近进行重新编组，即车厢离车头越近其目的地越远，这样方便到达目的地时卸货（卸下相关车厢）。编组过程中车厢只能依次从A中移动至B或C中，或从B或C中移至A中，从B中不能直接移至C中，从C中也不能直接移至B中。编写一程序模拟货运车厢编组。

假设A、B、C三段交叉路口为各段的顶端，编组规则如下：

1. 初始时所有车厢位于A中且均未完成编组，车头距离顶端最远；首先将其所有车厢从顶开始依次推进至B中。
2. 从B中找到发往地最远的车厢中离顶最近的车厢，假设其为M。将M至顶的所车厢依次推进至A中，此时M一定位于A中顶端。
3. 若A中M之后（即：M与车头之间）不存在未完成编组的车厢，则车厢M的编组完成了；若A中M之后存在未完成编组的车厢，则将M推进至 C中，将A中M之后所有未完成编组的车厢依次推进至B中，再将M由C中推进至A中，这样就完成了车厢M的编组；
4. 重复步骤2-3，直到B中无车厢。

输入形式

先从控制台输入目的地个数（大于等于1，小于等于50），然后分行输入一组由地名（用不含空白符的英文字符串表示，字符个数不超过20）和里程（用大于等于1小于等于10000的整数表示）构成的发往目的地（由近至远序）里程表，地名和里程之间以一个空格分隔；在里程表之后输入车厢个数（大于等于1，小于等于50），然后分行输入一组由车厢编号（由四位数字组成）和发往目的地（目的地肯定在上述里程表中出现）构成的车厢信息，车厢编号和目的地之间以一个空格分隔，并且是从车头处开始依次输入每节车厢信息。

输出形式

假设一节车厢从某段推出称为一次pop操作，推进某段称为一次push操作。程序运行输出第一行为从车头开始编好组的车厢编号，中间用一个空格隔开，最后一个车厢编号后也有一个空格。第二行输出编组过程中A段中push操作的次数。

样例输入

10
shijiazhuang 280
xingtai 390
xinxiang 610
zhengzhou 689
wuchang 1221
chibi 1339
yueyang 1434
changsha 1559
shaoguan 2057
guangzhou 2273
12
0039 guangzhou
5217 xingtai
0262 yueyang
7205 wuchang
3211 guangzhou
4893 shijiazhuang
2283 shaoguan
0890 guangzhou
8729 wuchang
6839 shijiazhuang
2122 changsha
3280 wuchang

样例输出

0039 3211 0890 2283 2122 0262 7205 8729 3280 5217 4893 6839
45

样例说明

首先输入由10个地名及其里程组成的里程表，然后输入了12节需要编组的车厢的编号和发往的目的地，即初始时处于A中的车厢，其中0039编号的车厢离车头最近。按照上面编组规则，首先将所有车厢推进至B中，这时0039车厢位于B的顶端，3280车厢位于底端，B中所有车厢中最远目的地为guangzhou、且离顶最近的车厢为0039，将其推进至A中，这时A中只有其一节车厢，其后没有未编组的车厢，0039车厢编组完成（即完成第一节车厢编组），此时A的push操作次数为1；接下来，B中剩余的11个车厢中，最远目的地依然为guangzhou，其离顶最近的车厢为3211，将该车厢及其上的3节车厢依次推进到A中，此时，3211车厢与火车头之间有三节车厢未完成编组，于是按规则将3211推进至C中，将7205、0262和5217依次推进至B中，再将C中的3211推进至A中，这时3211车厢编组完成（即完成第二节车厢编组），此时A的push操作次数为6；再依次按照上述步骤对B中剩余的车厢完成编组，直到B中无车厢。最后从车头开始将所有完成编组的车厢编号依次输出，由此得到一组发往目的地距离（从车头开始）由远至近的车厢序列。完成编组过程中A的push操作次数共有45次。

题解代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>


typedef struct zhandian{
    char name[99];
    int juli;
}zd;
zd a[999];

typedef struct chexiang{
    char bianhao[6];
    int zhan;
    int id;
}cx;
cx b[999];

int num;
int all;

void sort(){
    for (int i = 1; i < all; i++) {
        for (int j = 1; j < all; j++){
            if (a[b[j].zhan].juli < a[b[j+1].zhan].juli) {
                cx temp = b[j];
                b[j] = b[j + 1];
                b[j + 1] = temp;
            }
        }
    }
}


int main(){
    scanf("%d",&num);
    for(int i=1;i<=num;i++){
        scanf(" %s %d",a[i].name,&a[i].juli);
    }
    scanf("%d",&all);
    for(int i=1;i<=all;i++){
        char nowzhan[99];
        scanf(" %s %s",b[i].bianhao,nowzhan);
        b[i].id = i;
        for(int j=1;j<=num;j++){
            if(strcmp(a[j].name,nowzhan)==0){
                b[i].zhan  =  j;
                break;
            }
        }
    }
    sort();
    for(int i=1;i<=all;i++){
        printf("%s ",b[i].bianhao);
    }
    printf("\n");
    int ans = 0;
    for(int i=1;i<=all;i++){
        int s = 0;
        for(int j=1;j<i;j++){
            if(b[j].id<b[i].id) s++;
        }
        int k = b[i].id-s-1;
        if(k==0){
            ans++;
        }else{
            ans += 2+k;
        }
    }
    printf("%d",ans);
}

T9(附加) 老鼠回家-无回路

问题描述

老鼠离家去找食物，要经过不断探索才能找到食物。某老鼠非常聪明，在原路返回时能够避免找食物时多走的冤枉路，找到直接回家的路。

编写程序，读入该老鼠找食物过程中的轨迹记录，然后分析出其原路回家的最佳路径（即：走过的路，但不包括冤枉路）。在此冤枉路指的是原路返回的路；而且假设老鼠走过的路不会形成环。

算法提示：使用栈保存老鼠走过的轨迹；每当读入老鼠新的轨迹时，检查栈顶元素，判断新轨迹能否与栈顶轨迹抵消（全部或部分），然后进行入栈或出栈操作，示例见样例说明。

输入形式

输入为一系列老鼠轨迹。老鼠轨迹以行进方向和步数对来表示。行进方向包括：1-上、2-下、3-左、4-右，步数为一个整数值，行进方向和步数为0时表示输入结束。例如：1-4，表示向上行进4步，1和4之间为英文减号“-”。各行进步数间以一个空格分隔。最后的0-0后为换行符。老鼠行走的总步数不超过1000步。

以上图为例（图中数字为路的长度，以老鼠的步数为单位），老鼠从家开始找食物的轨迹输入如下：

1-2 3-4 1-7 2-3 4-3 3-3 2-4 4-4 1-6 4-2 2-2 1-2 3-4 1-3 0-0

输出形式

按照上述要求输出老鼠从食物回家的最佳路径，输出格式同输入，最后一步后有无空格均可。

样例输入

1-2 3-4 1-7 2-3 4-3 3-3 2-4 4-4 1-6 4-2 2-2 1-2 3-4 1-3 0-0

样例输出

2-3 4-2 2-8

样例说明

老鼠从家出发，开始向上走，经过14次轨迹后找到食物，最后输出原路回家的最佳路径。

题解代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
int lu[9999][2];
int i = 0;

int zhan[9999][2];
int ding = -1;

int main(){
    scanf(" %d-%d",&lu[i][0],&lu[i][1]);
    while(lu[i][0]!=0&&lu[i][1]!=0){
        i++;
        scanf(" %d-%d",&lu[i][0],&lu[i][1]);
    }
    for(int j=0;j<i;j++){
        if(ding<0){
            zhan[++ding][0] = lu[j][0];
            zhan[ding][1] = lu[j][1];
        }else{
            int q = zhan[ding][0];
            if(q==1&&lu[j][0]==2){
                if(zhan[ding][1]>lu[j][1]){
                    zhan[ding][1] -= lu[j][1];
                }else if(zhan[ding][1]<lu[j][1]){
                    zhan[ding][1] -= lu[j][1];
                    zhan[ding][1] = -zhan[ding][1];
                    zhan[ding][0] = 2;
                }else ding--;
            }else if(q==2&&lu[j][0]==1){
                if(zhan[ding][1]>lu[j][1]){
                    zhan[ding][1] -= lu[j][1];
                }else if(zhan[ding][1]<lu[j][1]){
                    zhan[ding][1] -= lu[j][1];
                    zhan[ding][1] = -zhan[ding][1];
                    zhan[ding][0] = 1;
                }else ding--;
            }else if(q==3&&lu[j][0]==4){
                if(zhan[ding][1]>lu[j][1]){
                    zhan[ding][1] -= lu[j][1];
                }else if(zhan[ding][1]<lu[j][1]){
                    zhan[ding][1] -= lu[j][1];
                    zhan[ding][1] = -zhan[ding][1];
                    zhan[ding][0] = 4;
                }else ding--;
            }else if(q==4&&lu[j][0]==3){
                if(zhan[ding][1]>lu[j][1]){
                    zhan[ding][1] -= lu[j][1];
                }else if(zhan[ding][1]<lu[j][1]){
                    zhan[ding][1] -= lu[j][1];
                    zhan[ding][1] = -zhan[ding][1];
                    zhan[ding][0] = 3;
                }else ding--;
            }else if(q==lu[j][0]){
                zhan[ding][1]+=lu[j][1];
            }else{
                ding++;
                zhan[ding][0] = lu[j][0];
                zhan[ding][1] = lu[j][1];
            }
        }
    }
    for(int i=ding;i>=0;i--){
        if(zhan[i][0]==1||zhan[i][0]==3)zhan[i][0]++;
        else zhan[i][0]--;
        printf("%d-%d ",zhan[i][0],zhan[i][1]);
    }
    return 0;
}

来自北京