实验报告
课程名称：数据结构与算法分析 实验名称：后缀表达式的计算
实验日期 3.20 班级： 数媒1401 姓名： 范业嘉 学号 1030514108
一、实验目的
熟练掌握栈和队列的存储结构设计及基本操作的实现；学会分析实际问题中具有栈特点的数据结构；
了解表达式的前缀、中缀、后缀等计算机内表示形式。
二、实验内容与要求
按常规形式输入算术表达式（例如：输入2*(6-4)+8/4），要求能够： ⑴生成表达式的后缀表示，并输出；
⑵基于表达式的后缀表示，对该表达式求值； ⑶编写一个主程序对表达式求值函数进行测试；
三、数据结构设计
顺序栈
#define MAXSIZE 100 typedef struct {
ElemType elem[MAXSIZE]; int length; }SqStack; SqStack S; 此外还有链栈 Typefef struct{ Float /char data； Float/char *next； }sqstack；
四、算法设计
1.表达式求值基本操作
(1)表达式起始符＃入运算符栈； ⑵读表达式中字符；
⑶若当前字符为＃，且运算符栈中栈顶元素也是＃，则表达 式计算结束，返回运算结果，否则执行⑷；
⑷若当前字符不是运算符，则入运算数栈，并读下一字符； 否则与运算符栈中栈顶元素进行优先级比较：
*栈顶优先级低
当前运算符入栈，并读下一字符；
*两者优先级同
必为左右括号相遇，令栈顶元素出栈，读下一字符；
*栈顶优先级高
完成栈顶运算，结果入运算数栈；
1 / 2
⑸反复执行⑶、⑷，直至计算完成。
2.前缀表达式的计算
（1） 初始化两个栈：运算符栈S1和储存中间结果的栈S2； （2） 从右至左扫描中缀表达式； （3） 遇到操作数时，将其压入S2；
（4） 遇到运算符时，比较其与S1栈顶运算符的优先级：
*如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入S1； *否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1；
*否则，将S1栈顶的运算符弹出并压入到S2中，再次转到①与S1中新的栈顶运算符相比较；
（5） 遇到括号时：
*如果是右括号“)”，则直接压入S1； *如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；
（6） 重复步骤2至5，直到表达式的最左边； （7） 将S1中剩余的运算符依次弹出并压入S2；
（8） 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。
五．测试结果
六、心得体会（包括对于本次实验的小结，实验过程中碰到的问题等）
1.刚开始对怎么进行运算符优先级的比较是一点头绪也没有的，后来到网上查了一下资料，看的似懂非懂的就把它copy下来了，虽然程序勉勉强强写出来了，但是关于运算符优先级这块儿，我还是希望老师上课能再讲一讲。
2.写了几次数据结构的作业，也有一点收获，比如接触一个新的结构时，其基本操作可以写的比较顺手。 3.数据结构写不好确实可能是c语言没有学好，可是上学期末因为课时紧，所以c语言后来指针并没有学完，更别说结构体和链表了，现在c++老师还没有讲到这块儿，所以都是靠我们自学在写数据结构，我希望老师上课的时候多讲讲程序代码，课件上也可以有一些。
2 / 2