http://hncu.acmclub.com/index.php?app=problem_title&id=111&problem_id=1741
题目描述
一个简单的行编辑程序的功能是：接收用户从终端输入的程序或数据，并存入用户的数据区。由于用户在终端上进行输入时，不能保证不出差错，因此，若在编辑程序中，“每接收一个字符即存入用户数据区”的做法显然不是很恰当。较好的做法是，设立一个输入缓冲区，用以接收用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时可以及时更正。例如，当用户发现刚刚键入的一个字符是错的时，可补进一个退格符“#”，以表示前一个字符无效；如果发现当前键入的行内错误较多或难以补救，则可以键入一个退行符“@”，以表示当前行中的字符均无效。例如假设从终端接收了这样的两行字符：
whil##ilr#e(s#*s)
outcha@ putchar(*s=#++);
则实际有效的是下列两行：
while(*s)
putchar(*s++);
为此，可设这个输入缓冲区为一个栈结构，每当从终端接收了一个字符之后先作如下判别：如果它不是退格符也不是退行符，则将该字符压入栈顶；如果是一个退格符，则从栈顶删去一个字符；如果它是一个退行符，则将字符栈清为空栈。上述处理过程可用下面算法描述之：
图：行编辑程序算法
输入格式
若干行程序或者数据，每行不超过200个字符。
输出
经过行编辑程序处理过后的输出。
样例输入
whil##ilr#e(s#*s)
outcha@ putchar(*s=#++);
样例输出
while(*s)
putchar(*s++);
#include<string.h>
#include<ctype.h>
#include<malloc.h> /* malloc()等 */
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<stdlib.h> /* atoi() */
#include<math.h> /* floor(),ceil(),abs() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */ #define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */
#define STACKINCREMENT 2 /* 存储空间分配增量 */
typedef char SElemType; /* 定义栈元素类型为整型 */
typedef struct SqStack
{
SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */
SElemType *top; /* 栈顶指针 */
int stacksize; /* 当前已分配的存储空间，以元素为单位 */
} SqStack; /* 顺序栈 */ Status InitStack(SqStack *S)
{
/* 构造一个空栈S */
(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW); /* 存储分配失败 */
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
return OK;
} Status Push(SqStack *S,SElemType e)
{
/* 插入元素e为新的栈顶元素 */
if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */
{
(*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW); /* 存储分配失败 */
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top)++=e;
return OK;
} Status Pop(SqStack *S,SElemType *e)
{
/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
if((*S).top==(*S).base)
return ERROR;
*e=*--(*S).top;
return OK;
} Status ClearStack(SqStack *S)
{
/* 把S置为空栈 */
(*S).top=(*S).base;
return OK;
} Status DestroyStack(SqStack *S)
{
/* 销毁栈S，S不再存在 */
free((*S).base);
(*S).base=NULL;
(*S).top=NULL;
(*S).stacksize=0;
return OK;
} Status StackTraverse(SqStack S,Status(*visit)(SElemType))
{
/* 从栈底到栈顶依次对栈中每个元素调用函数visit()。 */
/* 一旦visit()失败，则操作失败 */
while(S.top>S.base)
visit(*S.base++);
printf("\n");
return OK;
} void LineEdit() // 算法3.2
{
//利用字符栈S，从终端接收一行并传送至调用过程的数据区。
char ch, *temp;
SqStack S;
InitStack(&S); //构造空栈S
ch = getchar(); //从终端接收第一个字符
while (ch != EOF) //EOF为全文结束符
{
while (ch != EOF && ch != '\n')
{
switch (ch)
{
case '#':
Pop(&S, &ch);
break; // 仅当栈非空时退栈
case '@':
ClearStack(&S);
break; // 重置S为空栈
default:
Push(&S, ch);
break; // 有效字符进栈,未考虑栈满情形
}
ch = getchar(); // 从终端接收下一个字符
}
temp = S.base;
while (temp != S.top)
{
printf("%c", *temp);
++temp;
}
// 将从栈底到栈顶的栈内字符传送至调用过程的数据区；
ClearStack(&S); // 重置S为空栈
printf("\n");
if(ch != EOF)
{
ch = getchar(); // 读取下一行的第一个字符
}
}
DestroyStack(&S);
} int main()
{
LineEdit();
return 0;
}