实验3 栈的基本操作
四、参考程序
程序1：题1 栈的基本操作函数
#include
/* 栈的最大容量 */
/* 定义栈的类型为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( 栈空\nreak;
程序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
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