《数据结构实验与实训教程（第4版）》程序代码(4)

实验3 栈的基本操作

四、参考程序

程序1：题1 栈的基本操作函数

#include #define MAXN 10

/* 栈的最大容量 */

/* 定义栈的类型为int */

int push( int *stack, int maxn, int *toppt, int x ) /* 进栈函数 */

{ if( *toppt >= maxn ) /* 1 */ return 1;

2 /* 元素进栈 */

++(*toppt); /* 栈顶指针+1 */ return 0; /* 进栈成功 */ }

int pop( int *stack, int *toppt, int *cp ) /*出栈函数*/ { if( 3 ) /* 栈空，出栈失败，返回1 */ return 1; --(*toppt); /* 栈顶指针-1 */ 4 return 0; /* 出栈成功 */ }

void OutputStack( int *stack, int toppt ) /* 输出栈元素 */ { int i; for( i = 5 ; i >= 0; i-- ) printf( \ printf( \}

程序2：题2 主函数 void main() {

15

int s[MAXN], i; /* 定义栈 */ int top = 0; /* 设置为空栈 */ int op; while( 1 ) { printf( \请选择操作，1：进栈 2：出栈 0：退出 \

fflush( stdin ); /* 清空标准输入缓冲区 */ scanf( \switch( op ) {

case 0: /* 退出 */ return; case 1: /* 进栈 */ printf( \请输入进栈元素：\ scanf( \ if( 1 ) { /* 进栈成功 */ printf( \进栈成功，栈内元素为:\\n\ OutputStack( s, top );

} else printf( \栈满\\n\ break; case 2: /* 出栈 */ if( 2 ) { /* 出栈成功 */ printf( \出栈元素为: [%d] , 栈内元素为:\\n\ }

}

}

3 } else printf( \栈空\\n\break;

程序3：题3 配对函数

int correct( char *exp, int max ) /* 传入参数为表达式、表达式长度,返回0:成功,返回1:错误*/ {

int flag = 0; char s[MAXN]; int top = 0; /* 括号匹配标志，0: 正确 */ /* 定义栈 */

/* 栈指针为0，表示空栈 */

16

char c; int i; for( i = 0; 1 ; i++ ) {

/* 循环条件为表达式未结束且括号匹配 */ if( exp[i]=='(' || exp[i]=='[' || exp[i]=='{' } push( s, MAXN, &top, exp[i] );

if( exp[i]==')' || exp[i]==']' || exp[i]=='}' ) {/* 遇到},},}, 出栈 */ 2 /* 置出栈结果, 栈空出错 */

if( ( exp[i]==')' && c!='(' ) || ( exp[i]==']' && c!='[' )

|| ( exp[i]=='}' && c!='{' ) ) /* 括号不匹配 */

flag = 1; } } if( 3 ) /* 栈不为空，表明还有(,[,{符号没匹配 */ flag = 1; return flag; }

void main() { char s[MAXN], c; /* 定义栈 */ char exp[1024]; int top = 0; /* 设置为空栈 */ while( 1 ) { printf( \请输入表达式, 输入0退出: \ gets( exp ); /* 从标准输入中读取表达式 */ exp[MAXN] = '\\0'; /* 表达式长度 <= MAXN */

if( strcmp( exp, \

4 if( 5 ) printf( \表达式内容为：\\n%s\\n表达式括号不匹配\\n\ else printf( \表达式括号匹配\\n\

} }

程序4：题4 波兰表达式 #include #include #define MAXN 100 /* 栈的最大容量 */

17

int pushc( )/* char型元素进栈函数 */ { /*编写进栈子程序*/ }

int popc( char *stack, int *toppt, char *cp ) /* char型元素出栈函数 */ { }

/*编写出栈子程序*/

int eval( ) /* 算术运算 */ { /*编写算术运算子程序*/ }

int operate( char *str, int *exp ) /* 计算后缀表达式的值, 返回0:成功 -1:表达式错误 -2:栈满 */ { char c; int opd1, opd2, temp, c1; int s[MAXN]; int i;

int top = 0;

for( i = 0; str[i] != '\\0'; i++ ){ c = str[i]; if( c >= '0' && c <= '9' ){ /* 数字进栈 */ c1 = c - '0'; /* 将字符转换成数字值 */

if( push( s, MAXN, &top, c1 ) != 0 ){ printf( \表达式太长, 栈满\ return -2; }

}

else if( c == '+' || c == '-' || c == '*' || c == '/' ) { /* 运算符 */ pop( s, &top, &opd1 );

if( pop( s, &top, &opd2 ) != 0 ) return -1;

temp = eval( c, opd2, opd1 ); 1 ;

18

} else return -1; }

2 /* 取出结果 */

if( top != 0 ) /* 栈非空 */ return -1; return 0;

}

int trans( char *sin, char *sout ) /* 将中缀表达式转换成后缀, 返回0: 处理成功 */ { char s[MAXN], c; /* 定义栈, 栈元素 */ 3 /* 设置为空栈 */ int off = 0; /* 数组下标 */

int i;

for( i = 0; sin[i] != '\\0'; i++ ) /* 遇到休止符, 表示表达式输入结束 */ if( sin[i] >= '0' && sin[i] <= '9' ) /* 输入数字, 进数组 */ sout[ 4 ] = sin[i]; else switch( sin[i] ) { case '(': /* 左括号, 括号入栈 */ pushc( s, MAXN, &top, sin[i] );

break; case ')': /* 右括号, 将栈中左括号前的元素出栈, 存入数组 */ while( 1 ){ if( popc( s, &top, &c ) != 0 ){ /* 栈空 */ printf( \表达式括号不匹配\\n\ return -1;

} if( c == '(' ) /* 找到匹配的括号 */ break;

sout[ off++ ] = c; }

break;

/* 栈顶元素入数组 */

case '+': /* 为'+','-'，将栈中左括号前的元素出栈, 存入数组 */ case '-': while( top > 0 && s[top-1] != '(' ) { 5

19