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

1、1、实验目的(1)掌握栈“后进先出”的特点：(2)掌握栈的典型应用一-后缀表达式求值。2、实验内容用键盘输入个整数后缀式达式(操作数的范。9,运算符只含人_、含、1,而且中间不可(1)围是以有空格)，使用循环程序从左向右读入衣达式；如果读入的是运算符，立即从操作数计算操作数运算的值，并将计算结果(2)如果读入的是操作数，直接进入操作数栈;(3)栈取出所需的操作数，存回操作数栈：(4)检验程序运行结果。3、实验要求(1)分析后缀表达式求值的算法思想，用c(CH)语言完成程序设计.(2)上机调试通过实验程序。(3)给出具体的算法分析，包括时间复杂度和空间复杂度等。(4)撰写实验报告(把输入实验数据

2、及运行结果用抓图的形式粘贴到实验报告上)o(5)本程序调试通过以后，添加到原教材验证性实验3的菜单中去.4、实验步骤与源程序实验步骤我先从具体的问题中抽象出适当的数学模型，然后设计出相应的算法，其中，需要设计个函数来求后 缀衣达式，设计另外一个函数来求后缀衣达式的值，最后，编写主函数，串接程序，并调试程序，得出实验 结果。源代码sin clude<stdio. h> typed" struct *. char data.Xajjle n:int top:;opstack;typed" struct (float data.Xaxle n;int top:stac

3、k：void tran s (char str., char exp.) /求后缀表达式. ops tack op:char ch:op. top;T;ch=stri:while (ch!=> 0*)(switch (ch)caseop. op*:op. data .op. top.=ch;break:case )wnile (op. data.op. top !=* (')expLtj=op. data.op. top.op.top:op. top:break:case + ：case 一wnile (op. top !=1 Ide op. data .op. top. !=*

4、 (* ):exp.T'=op. data.op. top.op.top:op. top-op. data.op. topj=ch;break:case* * ：casewhile (op. top= / I o> top二二才expLtj=op. data.op. top.op. top-tfop.op. data.op. topj=ch;break:， ， casebreak:default：while (ch>= 0> 曲 ch<= 9>>(expCt=ch：一；ch=stri：输入为空格.则跳过expt=>一;ch=str i:whil

5、e (op. top !=-l)expltl=op. data lop. topj :一；op. top:expCt 0float cocnpvalue(char exp.)/后缀表达式求值 stack zz：float d;char ch:int t=0:st.top=-l;ch=expt:tfwhile(ch!=' 01) 5witch(ch)(皿'+'：st. catalst. top-ll=st. catalst. toaT：八.dataLst. top:st.top;break:casest. cata.st. top-1. =5t. data.st. top

6、-1.-st. datalst. top：;st.top;break:casest. catalst. top-ll=st. catalst. top-ll*zt. dataLst. top:st.top;break:casei£(zz. caxalzt. top!=0) st. datalst. top-ll=zt. datatst. top-11/st. dataLst. top：st.top:?衣达式中有除数为零.本次计算无效:" >break;default：d=0:while (ch) 0* 心 ch<= 9') d=10*dch-* 0* ：

7、ch=expt：tf | St. topi； st. dataLzt. top =d: | ch=expt;tf |ru:ur n st. data.st. top; * Avoid mai n()： char str n» exps n：prin tfn 请输入一个算术表达式："):printfCq 提示：操作数的范围是“I ”运算符只含+,*./和括号，中间不可以有空格B)： 2CT5(5tr)； prin原算木表这式为：%sn*» str);:ran 5 (str, exps);m-f(飞其后缀衣达式为, '>8 n" , exps)

8、;prin其运算的结果为：%enn*. compvalue (exps);* A5、测试数据与实验结果(可以抓图粘贴)请输入盲个算术丢达甘二*一1一1'一提不I操祜薮的罪围臭运算符只含和括号，中间不可以有空格7+12/6-1 *3*9原算术表达式为：7+12/6-1*3-9其后缰表达式为匕7 12 t 7 9 *4苴运算的结果为756、结果分析与实验体会本次实验是参考了范例程序，经过自己的改写，从而实现要求。先做简单的输出，步步的再做其它格 式的设置。在实验的过程中，我加深了时后缀农达式算法的理解，读入操作数时，直接输出到后缀表达式， 读入运算符，则压入运算符号栈，而且，若后进的运算符优先级高与先进的，则继续进栈，若后进的运算符 优先级不高于先进的，则将运算符号栈内高于或等于后进运算符级别的运算符依次弹出并输出到后缀表达 式，刻于括号，遇到开括号就进栈，遇到闭括号，则把窕近的开括号以及其后进栈的运算符依次弹出，并输 出到后缀农达式，