数据结构 实验3 后缀表达式求值.doc

《算法设计与分析 》实验报告 - PAGE 1 - 实验目的 掌握栈“后进先出”的特点； 掌握栈的典型应用——后缀表达式求值。 实验内容 用键盘输入一个整数后缀表达式（操作数的范围是0～9，运算符只含?、?、*、/，而且中间不可以有空格），使用循环程序从左向右读入表达式； 如果读入的是操作数，直接进入操作数栈； 如果读入的是运算符，立即从操作数栈取出所需的操作数，计算操作数运算的值，并将计算结果存回操作数栈； 检验程序运行结果。 实验要求 分析后缀表达式求值的算法思想，用C（C++）语言完成程序设计。 上机调试通过实验程序。 给出具体的算法分析，包括时间复杂度和空间复杂度等。 撰写实验报告（把输入实验数据及运行结果用抓图的形式粘贴到实验报告上）。 本程序调试通过以后，添加到原教材验证性实验3的菜单中去。 实验步骤与源程序 = 1 \* GB2 ⑴ 实验步骤 我先从具体的问题中抽象出适当的数学模型，然后设计出相应的算法，其中，需要设计一个函数来求后缀表达式，设计另外一个函数来求后缀表达式的值，最后，编写主函数，串接程序，并调试程序，得出实验结果。 = 2 \* GB2 ⑵ 源代码 #includestdio.h #define Maxlen 88 typedef struct { char data[Maxlen]; int top; }opstack; typedef struct { float data[Maxlen]; int top; }stack; void trans(char str[],char exp[]) // 求后缀表达式 { opstack op; char ch; int i=0,t=0; op.top=-1; ch=str[i]; i++; while(ch!=\0) { switch(ch) { case(: op.top++;op.data[op.top]=ch; break; case): while(op.data[op.top]!=() { exp[t]=op.data[op.top]; op.top--; t++; } op.top--; break; case+: case-: while(op.top!=-1 op.data[op.top]!=() { exp[t]=op.data[op.top]; op.top--; t++; } op.top++; op.data[op.top]=ch; break; case*: case/: while(op.top==/||op.top==*) { exp[t]=op.data[op.top]; op.top--; t++; } op.top++; op.data[op.top]=ch; break; case : // 输入为空格,则跳过 break; default: while(ch=0 ch=9) { exp[t]=ch; t++; ch=str[i];