栈的应用实验报告

（一） 栈的应用

1、实验目的：

（1）掌握栈的特点及其存储方法；

       （2）掌握栈的常见算法以及程序实现；

     （3）了解递归的工作过程。

2、实验内容：表达式求值问题。

这里限定的表达式求值问题是： 用户输入一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法数学表达式，计算该表达式的运算结果。

算术表达式求值过程是： STEP 1：先将算术表达式转换成后缀表达式。

                       STEP 2：然后对该后缀表达式求值。

3、实验说明：在设计相关算法中用到栈，这里采用顺序栈存储结构。

中缀表达式exp ==》后缀表达式postexp伪代码如下：

初始化运算符栈op;

将'='进栈;

从exp读取字符ch;

while (ch!='\0')

{   if (ch不为运算符)

　　　将后续的所有数字均依次存放到postexp中,并以字符'#'标志数值串结束;

     else

         switch(Precede(op栈顶运算符,ch))

         {

         case '':    //栈顶运算符应先执行,所以出栈并存放到postexp中

 退栈运算符并将其存放到postexp中; break;

        }

}

若字符串exp扫描完毕,则将运算符栈op中'='之前的所有运算符依次出栈并存放到postexp中。最后得到后缀表达式postexp;

 对后缀表达式postexp求值伪代码如下：

while (从postexp读取字符ch,ch!='\0')

{    若ch为数字,将后续的所有数字构成一个整数存放到数值栈st中。

     若ch为“+”,则从数值栈st中退栈两个运算数,相加后进栈st中。

     若ch为“－”,则从数值栈st中退栈两个运算数,相减后进栈st中。

     若ch为“*”,则从数值栈st中退栈两个运算数,相乘后进栈st中。

     若ch为“/”,则从数值栈st中退栈两个运算数,相除后进栈st中(若除数为零,则提示相应的错误信息)。}

若字符串postexp扫描完毕,则数值栈op中的栈顶元素就是表达式的值。