題目描述 一個簡單的行編輯程序的功能是：接收用戶從終端輸入的程序或數據，並存入用戶的數據區。由於用戶在終端上進行輸入時，不能保證不出差錯，因此，若在編輯程序中，“每接收一個字符即存入用戶數據區”的做法顯然不是很恰當。較好的做法是，設立一個輸入緩沖區，用以接收用戶輸入的一行字符，然後逐行存入用戶數據區。允許用戶輸入出差錯，並在發現有誤時可以及時更正。例如，當用戶發現剛剛鍵入的一個字符是錯的時，可補進一個退格符“#”，以表示前一個字符無效；如果發現當前鍵入的行內錯誤較多或難以補救，則可以鍵入一個退行符“@”，以表示當前行中的字符均無效。例如假設從終端接收了這樣的兩行字符： 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;
}
