一共包括六个程序，分别是：
l > 数制转换，
l > 括号匹配的检验，
l > 行编辑程序问题，
l > 迷宫求解，
l > 表达式求值，
l > 汉诺塔递归实现
这些栈的应用都是严蔚敏的数据结构那本书中的例子，但是那本书中的例子大都是用伪代码的形式写的，不是很容易理解和实现，对初学者造成了不小的困扰，在这里我们将其详尽的实现出来，以便初学者调试和运行，并从中有所收获。
上述的六个程序，每个程序的实现在一个文件中，每个程序都由C语言编写，只是借用C++中的两个东西，一是注释符‘//’，一是引用符‘&’。每个程序可以在C++兼容的编译器上直接运行，经过测试，运行情况良好，有什么问题，欢迎留言交流。
文件一：数制转换
/********************** 声明部分 **********************/#include#include#define STACK_INIT_SIZE 10 //定义最初申请的内存的大小#define STACK_INCREMENT 2 //每一次申请内存不足的时候扩展的大小#define OVERFLOW 0#define FALSE 0#define TRUE 1#define ERROR 0#define INFEASIBLE 0#define OK 1typedef int SElemType;typedef int Status;int Length;/********************** 结构类型部分 **********************/typedef struct SqStack{ SElemType *base; // 栈底指针 SElemType *top; // 栈顶指针 int stacksize;}SqStack; // 顺序栈/********************** 基本操作函数部分 **********************//********************** 构造一个空栈S **********************/Status InitStack(SqStack &S){ // 构造一个空栈S if (!(S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof (SElemType)))) exit(OVERFLOW); // 存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; //初始栈容量 return OK;}/********************** 输入栈元素 **********************/Status Push(SqStack &S, SElemType e){ if (S.top - S.base >= S.stacksize) // 栈满，追加存储空间 { //可能会改变栈底地址，新栈底指针S.base S.base = (SElemType *) realloc(S.base, //原栈底指针 (S.stacksize + STACK_INCREMENT) * sizeof (SElemType)); //新大小 if (!S.base) exit(OVERFLOW); // 存储分配失败 //给SqStack结构对象S的3个成员赋值 S.top = S.base + S.stacksize; S.stacksize += STACK_INCREMENT; } *S.top++ = e; //先把e压入栈顶，S.top再增1指向栈顶元素e的下一个位置 return OK;}/********************** 输出栈元素 **********************/void OutList(SqStack S){ S.top=S.base; // 从栈底开始输出 for(int i=0;i=0） = '); scanf('%u', &n); // 输入非负十进制整数n printf('\n请输入需要转换到的进制： '); scanf('%u', &m); // 输入非负十进制整数n printf('十进制数%u的八进制数是', n); while (n) // 只要n不等于0就循环 //从n为用户输入的十进制数开始，一直到n等于0为止 { Push(s, n % m); // n除以8的余数(8进制的低位)入栈 //把n除以8的余数压入栈s //先压入的余数是八进制的低位，后压入的余数是八进制的高位 n=n / m; //令n等于n整除以8的商，进入下轮循环 } //循环结束时，n等于0 while (!StackEmpty(s)) // 只要栈s没弹空就不断循环， //直到弹出栈底元素栈s为空为止 { Pop(s, e); // 弹出栈顶元素且赋值给e //依次弹出栈s的栈顶元素交给e带回 //先弹出的是八进制的高位，后弹出的是八进制的低位 printf('%d', e); // 依次输出e } //循环结束时，栈s为空 printf('\n');}/********************** 主函数部分 **********************/int main(){ /********************** 函数声明区 **********************/ Status InitStack(SqStack &S); Status Push(SqStack &S, SElemType e); void OutList(SqStack S); /********************** 函数执行区 **********************/ conversion(); return 0;}
文件二：括号匹配的检验
/********************** 声明部分 **********************/#include //输入输出函数头文件#include //内存申请函数头文件#define OVERFLOW false //异常抛出返回值#define FALSE false //异常抛出返回值#define TRUE true //异常抛出返回值#define ERROR false //异常抛出返回值#define INFEASIBLE false //异常抛出返回值#define OK true //程序正确执行抛出返回值typedef bool Status; //别名声明#define STACK_INIT_SIZE 100 // 存储空间初始分配量#define STACKINCREMENT 2 // 存储空间分配增量 typedef char SElemType;/********************** 结构类型部分 **********************/typedef struct SqStack{ //栈的数据元素类型在应用程序中定义typedef int SElemType; SElemType *base; // 栈底指针 //在栈构造之前和销毁之后，base为NULL SElemType *top; // 栈顶指针 //初值指向栈底，top = base可做栈空标记 //插入新栈顶元素时，top增1；删除栈顶元素时，top减1 //非空栈的top始终在栈顶元素的下一个位置上 int stacksize; // 当前已分配的存储空间，以元素为单位 //栈当前可使用的最大容量 int len;}SqStack;// 顺序栈/********************** 构造一个空栈S **********************/Status InitStack(SqStack &S){ // 构造一个空栈S //栈底指针S.base指向新分配的STACK_INIT_SIZE个SElemType大小的空间 if (!(S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof (SElemType)))) exit(OVERFLOW); // 存储分配失败 //必须给SqStack结构对象S的3个成员赋值 S.top = S.base; //空栈的栈顶指针S.top = 栈底指针S.base S.stacksize = STACK_INIT_SIZE; //初始栈容量 S.len = 0; return OK;}/********************** 返回栈顶元素 **********************/Status GetTop(SqStack S, SElemType &e){ // 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR if (S.top > S.base) { e = *(S.top - 1); //因为S.top指向栈顶元素的下一个位置， //所以栈顶元素就是e = *(S.top - 1) return OK; } else return ERROR;}/********************** 插入新的栈顶元素 **********************/Status Push(SqStack &S, SElemType e){ // 插入元素e为新的栈顶元素 if (S.top - S.base >= S.stacksize) // 栈满，追加存储空间 //如果栈长度大于栈容量 { //可能会改变栈底地址，新栈底指针S.base S.base = (SElemType *) realloc(S.base, //原栈底指针 (S.stacksize + STACKINCREMENT) * sizeof (SElemType)); //新大小 if (!S.base) exit(OVERFLOW); // 存储分配失败 //给SqStack结构对象S的3个成员赋值 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *(S.top)++ = e; //先把e压入栈顶，S.top再增1指向栈顶元素e的下一个位置 S.len++; return OK;}/********************** 删除栈顶元素 **********************/Status Pop(SqStack &S, SElemType &e){ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR if (S.top == S.base) //如果空栈，报错 return ERROR; e = *--S.top; //S.top先减1指向栈顶元素，再取值，交给e带回 S.len--; return OK;}Status IsEmpty(SqStack &S){ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR if (S.top == S.base) //如果空栈，报错 return TRUE; return FALSE;}void BraceMatch(){ char e,a[20]; int i=0; int flag=1; SqStack S; InitStack(S); printf('input the braces (<=20) and="" press="" '#'="" to="" show="" the="" end:\n');="" 输入字符="" do{="" scanf('%c',&e);="" a[i]="e;" i++;="" }while(e!='#' );="" printf('%s\n',a);="" i="0;" e="a[0];" while(e!='#' &&="" flag)="" {="" switch(e)="" {case="" '(':="" push(s,e);="" break;="" case="" '[':="" push(s,e);="" break;="" case="" '{':="" push(s,e);="" break;="" case="" ')':="" if(!isempty(s))="" {="" pop(s,e);="" if(e!='(' )flag="0;" }="" else="" flag="0;" break;="" case="" ']':="" if(!isempty(s))="" {="" pop(s,e);="" if(e!='[' )="" flag="0;" }="" else="" flag="0;" break;="" case="" '}':="" if(!isempty(s))="" {="" pop(s,e);="" if(e!='{' )="" flag="0;" }="" else="" flag="0;" break;="" }="" i++;="" e="a[i];" printf('the="" length="" of="" the="" stack="" is="" %d\n',s.len);="" }="" if(!isempty(s))="" flag="0;" if(flag)printf('match!\n');="" else="" printf('mis="" match!\n');="" }int="" main(){="" bracematch();="" return="">
文件三：行编辑程序问题
/********************** 声明部分 **********************/#include#include#define STACK_INIT_SIZE 10 //定义最初申请的内存的大小#define STACK_INCREMENT 2 //每一次申请内存不足的时候扩展的大小#define OVERFLOW false //异常抛出返回值#define FALSE false //异常抛出返回值#define TRUE true //异常抛出返回值#define ERROR false //异常抛出返回值#define INFEASIBLE false //异常抛出返回值#define OK true //程序正确执行抛出返回值typedef int SElemType; //别名声明，其实int可以用任意的名字代入typedef bool Status; //别名声明/********************** 结构类型部分 **********************/struct SqStack{ SElemType *base; // 栈底指针 //在栈构造之前和销毁之后，base为NULL SElemType *top; // 栈顶指针 //初值指向栈底，top = base可做栈空标记 //插入新栈顶元素时，top增1；删除栈顶元素时，top减1 //非空栈的top始终在栈顶元素的下一个位置上 int stacksize; // 当前已分配的存储空间，以元素为单位}; // 顺序栈/********************** 构造一个空栈S **********************/Status InitStack(SqStack &S){ // 构造一个空栈S //栈底指针S.base指向新分配的STACK_INIT_SIZE个SElemType大小的空间 if (!(S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof (SElemType)))) exit(OVERFLOW); // 存储分配失败 //必须给SqStack结构对象S的3个成员赋值 S.top = S.base; //空栈的栈顶指针S.top = 栈底指针S.base S.stacksize = STACK_INIT_SIZE; //初始栈容量 return OK;}/********************** 把S置为空栈 **********************/Status ClearStack(SqStack &S){ // 把S置为空栈 S.top = S.base; //空栈的栈顶指针S.top = 栈底指针S.base return OK;}/********************** 销毁栈S **********************/Status DestroyStack(SqStack &S){ // 销毁栈S，S不再存在 ClearStack(S); free(S.base); //释放栈底指针S.base //必须给SqStack结构对象S的3个成员赋值 S.base = NULL; S.top = NULL; S.stacksize = 0; return OK;}/********************** 插入新的栈顶元素 **********************/Status Push(SqStack &S, char e){ // 插入元素e为新的栈顶元素 if (S.top - S.base >= S.stacksize) // 栈满，追加存储空间 //如果栈长度大于栈容量 { //可能会改变栈底地址，新栈底指针S.base S.base = (SElemType *) realloc(S.base, //原栈底指针 (S.stacksize + STACK_INCREMENT) * sizeof (SElemType)); //新大小 if (!S.base) exit(OVERFLOW); // 存储分配失败 //给SqStack结构对象S的3个成员赋值 S.top = S.base + S.stacksize; S.stacksize += STACK_INCREMENT; } *(S.top)++ = e; //先把e压入栈顶，S.top再增1指向栈顶元素e的下一个位置 return OK;}/********************** 输出栈元素 **********************/int Length=0;void OutList(SqStack S){ S.top=S.base; // 从栈底开始输出 for(int i=0;i
文件四：迷宫求解
/********************** 声明部分 **********************/#include //输入输出函数头文件#include //内存申请函数头文件#define STACK_INIT_SIZE 10 //定义最初申请的内存的大小#define STACK_INCREMENT 2 //每一次申请内存不足的时候扩展的大小#define OVERFLOW false //异常抛出返回值#define FALSE false //异常抛出返回值#define TRUE true //异常抛出返回值#define ERROR false //异常抛出返回值#define INFEASIBLE false //异常抛出返回值#define OK true //程序正确执行抛出返回值typedef bool Status; //别名声明#define STACK_INIT_SIZE 10 // 存储空间初始分配量#define STACKINCREMENT 2 // 存储空间分配增量/* typedef int ElemType; */typedef struct{ int r; int c;}PosType;typedef struct{ int ord; /* 通道块在路径上的序号 */ PosType seat; /* 通道块在迷宫中的“坐标位置” */ int di; /* 从此通道块走向下一个通道块的“方向” */}SElemType;typedef struct{ char arr[10][10];}MazeType;/********************** 结构类型部分 **********************/typedef struct SqStack{ //栈的数据元素类型在应用程序中定义typedef int SElemType; SElemType *base; // 栈底指针 //在栈构造之前和销毁之后，base为NULL SElemType *top; // 栈顶指针 //初值指向栈底，top = base可做栈空标记 //插入新栈顶元素时，top增1；删除栈顶元素时，top减1 //非空栈的top始终在栈顶元素的下一个位置上 int stacksize; // 当前已分配的存储空间，以元素为单位 //栈当前可使用的最大容量}SqStack;// 顺序栈/********************** 构造一个空栈S **********************/Status InitStack(SqStack &S){ // 构造一个空栈S //栈底指针S.base指向新分配的STACK_INIT_SIZE个SElemType大小的空间 if (!(S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof (SElemType)))) exit(OVERFLOW); // 存储分配失败 //必须给SqStack结构对象S的3个成员赋值 S.top = S.base; //空栈的栈顶指针S.top = 栈底指针S.base S.stacksize = STACK_INIT_SIZE; //初始栈容量 return OK;}/********************** 返回栈顶元素 **********************/Status GetTop(SqStack S, SElemType &e){ // 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR if (S.top > S.base) { e = *(S.top - 1); //因为S.top指向栈顶元素的下一个位置， //所以栈顶元素就是e = *(S.top - 1) return OK; } else return ERROR;}/********************** 插入新的栈顶元素 **********************/Status Push(SqStack &S, SElemType e){ // 插入元素e为新的栈顶元素 if (S.top - S.base >= S.stacksize) // 栈满，追加存储空间 //如果栈长度大于栈容量 { //可能会改变栈底地址，新栈底指针S.base S.base = (SElemType *) realloc(S.base, //原栈底指针 (S.stacksize + STACKINCREMENT) * sizeof (SElemType)); //新大小 if (!S.base) exit(OVERFLOW); // 存储分配失败 //给SqStack结构对象S的3个成员赋值 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *(S.top)++ = e; //先把e压入栈顶，S.top再增1指向栈顶元素e的下一个位置 return OK;}/********************** 删除栈顶元素 **********************/Status Pop(SqStack &S, SElemType &e){ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR if (S.top == S.base) //如果空栈，报错 return ERROR; e = *--S.top; //S.top先减1指向栈顶元素，再取值，交给e带回 return OK;}Status IsEmpty(SqStack &S){ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR if (S.top == S.base) //如果空栈，报错 return TRUE; return FALSE;}int pass(MazeType MyMaze, PosType CurPos);void footPrint(MazeType &MyMaze, PosType CurPos);void markPrint(MazeType &MyMaze, PosType CurPos);PosType nextPos(PosType CurPos, int Dir);int pass( MazeType MyMaze,PosType CurPos){ if (MyMaze.arr[CurPos.r][CurPos.c]==' ') return 1; // 如果当前位置是可以通过，返回1 else return 0; // 其它情况返回0}void footPrint(MazeType &MyMaze,PosType CurPos){ MyMaze.arr[CurPos.r][CurPos.c]='*';}void markPrint(MazeType &MyMaze,PosType CurPos) { MyMaze.arr[CurPos.r][CurPos.c]='!';}PosType nextPos(PosType CurPos, int Dir) { PosType ReturnPos; switch (Dir) { case 1: ReturnPos.r=CurPos.r; ReturnPos.c=CurPos.c+1; break; case 2: ReturnPos.r=CurPos.r+1; ReturnPos.c=CurPos.c; break; case 3: ReturnPos.r=CurPos.r; ReturnPos.c=CurPos.c-1; break; case 4: ReturnPos.r=CurPos.r-1; ReturnPos.c=CurPos.c; break; } return ReturnPos;}/* 迷宫函数 *//* 判断是否存在一条从开口到结尾的路径 */int mazePath(MazeType &maze, PosType start, PosType end){ SqStack s; InitStack(s); PosType curpos = start; // 设定'当前位置'为'入口位置' SElemType e; int curstep = 1; // 探索第一步 do { if (pass(maze,curpos)) { // 当前位置可通过，即是未曾走到过的通道块 footPrint(maze,curpos); // 留下足迹 e.di =1; e.ord = curstep; e.seat= curpos; Push(s,e); // 加入路径 if (curpos.r == end.r && curpos.c==end.c) return TRUE; // 到达终点（出口） curpos = nextPos(curpos, 1); // 下一位置是当前位置的东邻 curstep++; // 探索下一步 } else { // 当前位置不能通过 if (!IsEmpty(s)) { Pop(s,e); while (e.di==4 && !IsEmpty(s)) { markPrint(maze,e.seat); Pop(s,e); // 留下不能通过的标记，并退回一步 } // while if (e.di<4) {="" e.di++;="" push(s,="" e);="" 换下一个方向探索="" curpos="nextPos(e.seat," e.di);="" 当前位置设为新方向的相邻块="" }="" if="" }="" if="" }="" else="" }="" while="" (!isempty(s)="" );="" return="" false;}="" mazepathint="" main(){="" printf('hello="" world!');="" mazetype="" maze;="" maze.arr="{" {'0','0','0','0','0','0','0','0','0','0'},="" {'0','="" ','="" ','0','="" ','="" ','="" ','0','="" ','0'},="" {'0','="" ','="" ','0','="" ','="" ','="" ','0','="" ','0'},="" {'0','="" ','="" ','="" ','="" ','0','0','="" ','="" ','0'},="" {'0','="" ','0','0','0','="" ','="" ','="" ','="" ','0'},="" {'0','="" ','="" ','="" ','0','="" ','="" ','="" ','="" ','0'},="" {'0','="" ','0','="" ','="" ','="" ','0','="" ','="" ','0'},="" {'0','="" ','0','0','0','="" ','0','0','="" ','0'},="" {'0','0','="" ','="" ','="" ','="" ','="" ','="" ','="" ','0'},="" {'0','0','0','0','0','0','0','0','0','0'}="" };="" postype="" start="{1,1};" postype="" end="{8,8};" if(mazepath(maze,start,end))="" printf('you="" can="" go="" through="" the="" maze~~\n');="" else="" printf('there="" is="" no="" path~~\n');="" return="">
文件五：表达式求值
/********************** 声明部分 **********************/#include //输入输出函数头文件#include //内存申请函数头文件#define STACK_INIT_SIZE 10 //定义最初申请的内存的大小#define STACK_INCREMENT 2 //每一次申请内存不足的时候扩展的大小#define OVERFLOW false //异常抛出返回值#define FALSE false //异常抛出返回值#define TRUE true //异常抛出返回值#define ERROR false //异常抛出返回值#define INFEASIBLE false //异常抛出返回值#define OK true //程序正确执行抛出返回值typedef int SElemType; //别名声明，其实int可以用任意的名字代入typedef bool Status; //别名声明#define STACK_INIT_SIZE 10 // 存储空间初始分配量#define STACKINCREMENT 2 // 存储空间分配增量/********************** 结构类型部分 **********************/struct SqStack{ //栈的数据元素类型在应用程序中定义typedef int SElemType; SElemType *base; // 栈底指针 //在栈构造之前和销毁之后，base为NULL SElemType *top; // 栈顶指针 //初值指向栈底，top = base可做栈空标记 //插入新栈顶元素时，top增1；删除栈顶元素时，top减1 //非空栈的top始终在栈顶元素的下一个位置上 int stacksize; // 当前已分配的存储空间，以元素为单位 //栈当前可使用的最大容量}; // 顺序栈/********************** 构造一个空栈S **********************/Status InitStack(SqStack &S){ // 构造一个空栈S //栈底指针S.base指向新分配的STACK_INIT_SIZE个SElemType大小的空间 if (!(S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof (SElemType)))) exit(OVERFLOW); // 存储分配失败 //必须给SqStack结构对象S的3个成员赋值 S.top = S.base; //空栈的栈顶指针S.top = 栈底指针S.base S.stacksize = STACK_INIT_SIZE; //初始栈容量 return OK;}/********************** 返回栈顶元素 **********************/Status GetTop(SqStack S, SElemType &e){ // 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR if (S.top > S.base) { e = *(S.top - 1); //因为S.top指向栈顶元素的下一个位置， //所以栈顶元素就是e = *(S.top - 1) return OK; } else return ERROR;}/********************** 插入新的栈顶元素 **********************/Status Push(SqStack &S, SElemType e){ // 插入元素e为新的栈顶元素 if (S.top - S.base >= S.stacksize) // 栈满，追加存储空间 //如果栈长度大于栈容量 { //可能会改变栈底地址，新栈底指针S.base S.base = (SElemType *) realloc(S.base, //原栈底指针 (S.stacksize + STACKINCREMENT) * sizeof (SElemType)); //新大小 if (!S.base) exit(OVERFLOW); // 存储分配失败 //给SqStack结构对象S的3个成员赋值 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *(S.top)++ = e; //先把e压入栈顶，S.top再增1指向栈顶元素e的下一个位置 return OK;}/********************** 删除栈顶元素 **********************/Status Pop(SqStack &S, SElemType &e){ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR if (S.top == S.base) //如果空栈，报错 return ERROR; e = *--S.top; //S.top先减1指向栈顶元素，再取值，交给e带回 return OK;}/********************** 判断两符号的优先关系 **********************/SElemType Precede(SElemType t1, SElemType t2){ SElemType f; //栈元素f，准备存放<、=、>供函数返回值使用 switch (t2) { case '+': case '-': if (t1 == '(' || t1 == '#') //(、# < +、-="" f='<' ;="" else="" 其余=""> +、- f = '>'; break; case '*': case '/': if (t1 == '*' || t1 == '/' || t1 == ')') //*、/、) > *、/ f = '>'; else //其余 < *、/="" f='<' ;="" break;="" case="" '(':="" if="" (t1="=" ')')="" )后面不能紧跟(，紧跟报错="" {="" printf('error1\n');="" exit(error);="" }="" else="" 其余="">< (="" f='<' ;="" break;="" case="" ')':="" switch="" (t1)="" {="" case="" '(':="" f='=' ;="" (=")" break;="" case="" '#':="" #后面不能紧跟)，紧跟报错="" printf('error2\n');="" exit(error);="" default:="" 其余=""> ) f = '>'; } break; case '#': switch (t1) { case '#': f = '='; //# = # break; case '(': //(后面不能紧跟#，紧跟报错 printf('ERROR3\n'); exit(ERROR); default: //其余 > # f = '>'; } } return f;}/********************** 判断是否为运算符 **********************/Status In(SElemType c){ // 判断c是否为运算符 switch (c) { case'+': case'-': case'*': case'/': case'(': case')': case'#': return TRUE; default: return FALSE; }}/********************** 计算函数 **********************/SElemType Operate(SElemType a, SElemType theta, SElemType b) //栈元素a、theta、b{ // 二元运算c = a theta b SElemType c; //栈元素c，准备存放运算结果，供函数返回值使用 a = a - 48; b = b - 48; switch (theta) { case '+': c = a + b + 48; //运算完毕后再把数字转换成字符 break; case '-': c = a - b + 48; break; case '*': c = a * b + 48; break; case '/': c = a / b + 48; } return c; //返回运算结果}/********************** 主算法函数 **********************/SElemType EvaluateExpression() // 算法3.4{ // 算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈 SqStack OPTR, OPND; //顺序栈OPTR、OPND SElemType a, b, c, x, theta; //栈元素a、b、c、x、theta InitStack(OPTR); //构造空栈OPTR，准备装运算符 Push(OPTR, '#'); //栈OPTR的栈底元素是# InitStack(OPND); //构造空栈OPND，准备装操作数 //初始化循环变量 c = getchar(); //输入字符c GetTop(OPTR, x); //取OPTR的栈顶元素交给x //只要栈顶元素x、或输入字符c不为#，就循环 while (c != '#' || x != '#') { if (In(c)) // 如果c是7种运算符之一，In(c)返回TRUE switch (Precede(x, c)) //比较栈顶元素x、输入字符c的优先权 { case '<': 如果栈顶元素x优先权低于输入字符c="" push(optr,="" c);="" 输入字符c入运算符栈optr="" c="getchar();" 接收下个字符，准备下轮循环="" 接收不到就用原来在c中的值参加下轮和x的比较="" break;="" case="" '=': // 如果栈顶元素x优先权等于输入字符c Pop(OPTR, x); //栈OPTR的栈顶元素出栈，赋给栈顶元素x //消括号(、)，只有(和)、#和#的优先权相等； //但是#不用这消，而是用while循环的判断条件消 //(的优先权最高，)的优先权最低， //如果(在栈顶、)在输入，则( = )； //如果)在栈顶、(在输入，则报错 c = getchar(); //接收下个字符，准备下轮循环 //接收不到就用原来在c中的值参加下轮和x的比较 break; case '>': // 如果栈顶元素x优先权高于输入字符c Pop(OPTR, theta); // 栈顶元素x出运算符栈OPTR，赋给theta Pop(OPND, b); //操作数出操作数栈OPND，赋给b Pop(OPND, a); //操作数出操作数栈OPND，赋给a Push(OPND, Operate(a, theta, b)); //运算结果Operate(a, theta, b)入操作数栈OPND break; } else if (c >= '0' && c <= '9')="" 如果c在0到9之间，是操作数="" {="" push(opnd,="" c);="" 操作数c入操作数栈opnd="" c="getchar();" 接收下个字符，准备下轮循环="" }="" else="" 如果c既不是7种运算符也不是0到9的操作数，那么c是非法字符，报错="" {="" printf('error4\n');="" exit(error);="" }="" gettop(optr,="" x);="" 只要运算符栈optr的栈顶元素x或当前读入字符c不为#，="" 就不断地取运算符栈optr的栈顶元素赋给x="" }="" 循环结束时，操作数栈opnd的栈顶元素是运算结果="" gettop(opnd,="" x);="" 取操作数栈opnd的栈顶元素（运算结果）赋给x="" return="" x;="" 返回运算结果}int="" main(){="" printf('请输入算术表达式（中间值及最终结果要在0～9之间），并以#结束\n');="" printf('%c\n',="" evaluateexpression());="" 算术表达式求值="" return="">
文件六：汉诺塔递归实现
/*********** 汉诺塔 *********/#include int c = 0; // 全局变量，搬动次数//x源塔，第n个圆盘（编号n），z目标塔void move(char x, int n, char z){ // 将编号为n的圆盘从塔座x搬到塔座z printf('第%i步: 将%i号盘从%c移到%c\n', ++c, n, x, z);}//n个圆盘（编号从1到n），x源塔，y辅助塔，z目标塔void hanoi(int n, char x, char y, char z){ // 将塔座x上按直径由小到大且自上而下编号为1至n的n个圆盘 // 按规则搬到塔座z上，y作辅助塔 if (n == 1) move(x, 1, z); // 将编号为1的圆盘从塔座x搬到塔座z else { hanoi(n - 1, x, z, y); // 将塔座x上编号为1至n - 1的圆盘搬到塔座y，z作辅助塔 move(x, n, z); // 将编号为n的圆盘从塔座x搬到塔座z hanoi(n - 1, y, x, z); // 将塔座y上编号为1至n - 1的圆盘搬到塔座z，x作辅助塔 }}int main(){ int n; printf('3个塔座为a、b、c，圆盘最初在a座，借助b座移到c座。请输入圆盘数：'); scanf('%d', &n); hanoi(n, 'a', 'b', 'c'); // 将塔座a上编号为1至n的n个圆盘搬到塔座c上，b作辅助塔 return 0;}
