编译原理波兰式和四元式.docx

实验三波兰式和四元式及计算 课程编译原理 实验名称波兰式和四元式 第页 班级 11 计本 学号姓名 实验日期： 2013 年 月 日报告退发 (订正、重做 ) 一、实验目的： 将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式， 并 计算用逆波兰式来表示的算术表达式的值。 二、实验说明 1、逆波兰式定义 将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表 达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置 反映运算顺序。采用逆波兰式可以很好的表示简单算术表达式，其优点在于 易于计算机处理表达式。 2、产生逆波兰式的前提 中缀算术表达式 3、逆波兰式生成的实验设计思想及算法 1 / 7 (1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原 则。 (2)读入一个用中缀表示的简单算术表达式，为方便起见 ,设该简单算术表达 式的右端多加上了优先级最低的特殊符号“ #”。 (3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数 字，则分析到该数字串的结束并将该数字串直接输出。 (4)如果不是数字，该字符则是运算符，此时需比较优先关系。 做法如下： 将该字符与运算符栈顶的运算符的优先关系相比较。 如果， 该字 符优先关系高于此运算符栈顶的运算符， 则将该运算符入栈。 倘若不是的话， 则 将此运算符栈顶的运算符从栈中弹出，将该字符入栈。 (5)重复上述操作 (1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得 到正确处理， 我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示 的简单算术表达式。 3、逆波兰式计算的实验设计思想及算法 (1)构造一个栈，存放运算对象。 (2)读入一个用逆波兰式表示的简单算术表达式。 (3)自左至右扫描该简单算术表达式并判断该字符， 如果该字符是运算对 象，则将该字符入栈。若是运算符，如果此运算符是二目运算符，则将对栈 顶部的两个运算对象进行该运算，将运算结果入栈，并且将执行该运算的两 个运算对象从栈顶弹出。如果该字符是一目运算符，则对栈顶部的元素实施 该运算，将该栈顶部的元素弹出，将运算结果入栈。 (4)重复上述操作直至扫描完整个简单算术表达式的逆波兰式， 确定所有 字符都得到正确处理，我们便可以求出该简单算术表达式的值。 2 / 7 三、实验要求 （一）准备： 1.阅读课本有关章节， 2.考虑好设计方案； 3.设计出模块结构、测试数据，初步编制好程序。 （二）上课上机： 将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。 （三）程序要求： 程序输入/输出示例： 输出的格式如下： (1)逆波兰式的生成及计算程序，编制人：姓名，学号，班级 (2)输入一以#结束的中缀表达式 (包括 +— */ （）数字 #)：在此位置输入符号串如 4*(28+87*6-75)/8 (3)逆波兰式为： 428876*+75-*8/ (4)逆波兰式 test428876*+75-*8/= 计算结果为 备注： (1)在生成的逆波兰式中如果两个数相连则用 分隔； 237.5 分隔，如 28 和 87，中间用 (2)在此位置输入符号串为用户自行输入的符号串 注意： 1.表达式中允许使用运算符（ +-*/）、分割符（括号） 、数字，结束符 #； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好） ； 3.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达 式， 同时以分号分割。 同时将预期的输出结果写在另一个文本文件中， 以便和输 出进行对照； 3 / 7 （四）代码实现 using System; using System.Collections.Generic; using System.ComponentModel; using using using using using System.Data; System.Drawing; System.Linq; System.Text; System.Windows.Forms; namespaceWindowsFormsApplication1 { publicpartialclass { public Form7() Form7: Form { InitializeComponent(); } privatevoid