[工学]第3章 栈和队列jqj.ppt

(2) 后缀表达式求值 从左至右扫描：先找运算符，再找操作数。 循环队列示意图 int isoperator( char op ) // 判断运算符 { switch ( op ) { case +: case - : case *: case / : return 1; // 是运算符 default: return 0; // 不是运算符 } } int getvalue( char op, int operand1, int operand2 ) // 计算表达式值 { switch( op ) { case *: return(operand1*operand2); case /: return(operand1/operand2); case +: return(operand1+operand2); case -: return(operand1-operand2); default: return 0; } } void main( ) // 主函数 { char exp[100]; int operand1=0; // 定义操作数1 int operand2=0; // 定义操作数2 int result=0; // 定义操作结果 int pos=0; printf(“\t\n 请输入后缀表达式：”); gets(exp); // 读取后缀表达式 printf(“\t\n\n 后缀表达式[%s]的结果是：”, exp); while ( exp[pos] !=\0 exp[pos] !=\n ) // 分析表达式字符串 { if ( isoperator(exp[pos]) ) // 是运算符，取两个操作数 { operand=pop( operand, operand2); operand=pop( operand, operand1); operand=push(operand, getvalue(exp[pos],operand1,operand2) ); // 计算结果入栈 } else operand=push( operand, (int)exp[pos] ); // 是操作数，压入操作数栈 pos++; // 移到下一个字符位置 } operand=pop(operand, result); // 弹出结果 printf(“%d\n”, result); // 输出 } 3.3 栈与递归的实现 在程序设计中，子程序的调用及返回地址是用栈完成的。 C（或C++）的函数嵌套调用： 调用子函数前，先将返回地址保存到栈中，然后转去执行子函数； 当子函数执行到return语句（或函数结束）时， 从栈中弹出返回地址，从该地址处继续执行。 1. 子程序调用 例： 主函数调用子函数a()时， 在调用之前先将a函数的返回地址压入栈中； 在子函数a()中调用子函数b()时，又将b函数的返回地址压入栈中； 在子函数b()中调用子函数c()时，又将c函数的返回地址压入栈中； …… 返回地址栈： 当执行完子函数c( )后，就从栈顶弹出c函数返回地址， 回到子函数b( )； 当执行完子函数b( )后，就从栈顶弹出b函数返回地址， 回到子函数