编译原理逆波兰表达式c语言版.docx

1、编译原理逆波兰表达式c语言版中国计量学院编译原理设计课程论文题目：中缀表达式的逆波兰表示学生姓名 ： 学 号 ：学生专业 ： 班 级 ： 二级学院 ： 一、摘要 编译原理是计算机科学与技术专业最重要的一门专业基础课程，内容庞大，涉及面广，知识点多。由于该课程教、学难度都超级大，往往费了大量时间而达不到预期教学效果俗语说：学习的最好方式是实践。本课程设计正是基于此，力求为学生提供一个理论联系实际的机缘，通过布置必然难度的课题，要求学生独立完成。咱们这次课程设计的主要任务是编程实现对输入合法的中缀表达式进行词法分析、语法分析，构造相应的逆波兰式，计算后缀表达式的值输出结果。逆波兰式也叫后缀表达式，

2、即将运算符写在操作数以后。通过实践，成立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培育独立学习、吸取他人经验、探索前言知识的习惯，树立团队协作精神。同时，课程设计可以充分弥补课堂教学及普通实验中知识深度与广度有限的缺点，更好地帮忙学生从全局角度把握课程体系。 关键字： 逆波兰式；语法分析；中缀表达式二、实验综述 在通常的表达式中，二元运算符老是置于与之相关的两个运算对象之间，所以，这种表示法也称为中缀表示。对中缀表达式的计值，并非按运算符出现的自然顺序来执行其中的各个运算，而是按照算符间的优先关系来肯定运算的顺序，另外，还应顾及括号规则。因此，要从中缀表达式直接产生目

3、标代码一般比较麻烦。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。 三、实验意义 对于实现逆波兰式算法，难度并非大，但为何要将看似简单的中缀表达式转换为逆波兰式，原因就在于这个简单是相对人类的思维结构来讲的，对计算机而言中缀表达式是超级复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行 四、系统分析 词法分析大体原理 ：词法分析程序完成的是编译第一阶段的工作。词法分析的作用是把符流的程序变成单词序列，输出在一个中间文件上，这个文件作为语法分析程序的输入而继续编译进程。

4、 递归下降的原理 由于时间和技术的限制，语法分析采用递归下降的方式。递归下降法是语法分析中最易懂的一种方式。它的主要原理是，对每一个非终极符按其产生式结构构造相应语法分析子程序，其中终极符产生匹配命令，而非终极符则产生进程挪用命令。因为文法递归相应子程序也递归，所以称这种方式为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。 五、算法实现 将一个普通的中序表达式转换为逆波兰表达式的一般算法是：1 、首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。 2 、读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号

5、“#”。 3 、从左至右扫描该算术表达式，从第一个字符开始判断，若是该字符是数字，则分析到该数字串的结束并将该数字串直接输出。 4、 若是不是数字，该字符则是运算符，此时需比较优先关系。 做法如下：将该字符与运算符栈顶的运算符的优先关系相较较。若是，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。 5 、重复上述操作1-2直至扫描完整个简单算术表达式，肯定所有字符都得正确处置，咱们即可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。 转换的大体思路： 1 在表达式字符串的末尾加一个代表结束的辅助符，比如“#”。 2 从头开始扫描表达式，并判断当前的每一个字符。 3 取

6、当前的一个字符，若是当前字符是代表数字，则进逆波兰式的栈，若是是运算符，则转入4，若是是“#”，则结束。 4 比较当前运算符与临时栈中的栈顶运算符，若是栈顶运算符比当前运算符优先级高，则弹出一个运算符放进逆波兰式栈中，并继续4。不然把当前运算符进临时栈，转入2六、测试结果七、总结 在这次的课程设计中，让我深深地表现到编程不是一件简单的事情，它需要设计者具有全面的专业知识、缜密的思维、严谨的工作态度和较高的分 析问题、解决问题的能力，而我在很多方面还有欠缺。 通过编程实现了预期的目标，虽然如此，在程序实现的进程中出现过许多没有想到的功能，本来设计的思路和方式，到真正的程序中运行的时候就达不到预想

7、的效果。因此，我感觉编程序实际操作是超级重要的，不亲自实践就不会发现问题，咱们只有不断的发现问题，不断的解决问题，才能使一个程序尽可能的完善。 当我即将完成这个设计的时候我终于认清楚了以前老师常常提起的一个问题，那就是：一个软件开发的进程中编码不是重要的，重要的是对分析系统和系统模型的成立。有了一个好的系统模型以后，咱们再将其划分成几个模块，那样做起来就会容易患多。 由于经验不足，时间有限，虽然在一周的时间里顺利的完成了系统的分析、设计和调试的工作，可是仍然有许多不足的地方，我会在未来的软件设计进程中引以为戒。在做课程设计期间，有目的的去学习一些将要用到的东西，仔细的考虑工作流程的规律和步骤，

8、充分的利用手中的开发工具，使自己的开发在代码上实现少而精准，能够尽可能简单的进行操作。 通过这个课程设计让我有了深刻的了解，增加了自己的动手能力，而且我熟悉到团队合作也十分重要。通过这次课程设计不仅锻炼了我学习能力，在团队合作上也有很大提高附录：源代码#include/*标准输入输出头文件*/#include/*控制台输入输出*/#include/*数学库函数*/#include/*系统函数，分派、释放内存等*/#include/*字符串处置*/#define MaxSize 99char calcMaxSize,exprMaxSize;int i,t;struct char dataMaxS

9、ize;/*构造了一个字符串*/ int top;Sym;/*符号*/struct double dataMaxSize;/*构造一个双精度数组*/ int top;Num;/*数*/double ston(char x,int *p)/*概念一函数*/ int j=*p+1,i; double n=0; char sign=x*p;/*字符串*/ if(sign=+|sign=-) *p=*p+1; while(xj=0&xj=9) j+; for(i=*p;i=0&xj=9) j+; for(i=*p;ij;i+) n=n+pow,i-*p+1)*(xi-0); *p=j; if(sign

10、=-) return(-n); return(n);void InitStack() =-1;void SymPush() if=0) expr+t=; else printf(Sym栈空n); return; void NumPush() if=0) if(expri!= ) switch(expri) case +:=+;break; case -:=;break; case *:=*;break; case /:=/;break; case %:=(int)%(int);break; case :=pow,);break; ; else printf(Num栈空n); return; i

11、nt main(void) loop1: i=0,t=-1; system(cls); printf(*n); printf(*中缀表达式变逆波兰表达式*n); printf(*n); printf(请输入中缀表达式：); InitStack(),gets(calc); while(calci!=0&calci!=) if(calci=0&calci=0&calci=0&calci-1=0 & !=() SymPop(); expr+t= ; SymPush(); else if(calci=*|calci=/|calci=%) while=0&=*|=/|=%|=) SymPop(); ex

12、pr+t= ; SymPush(); else if(calci=) while=0&=) SymPop(); expr+t= ; SymPush(); else i+; while=0) SymPop(); expr+t= ; expr+t=+=0; printf(后缀表达式：%sn,expr); for(i=0;expri!=0;i+) if(expri=0&expri=0&expri+1=9) NumPush(); else NumPop(); printf(运算结果为：%gn,0); printf(Continue(y/n)?); switch(getch() case y:system(cls);goto loop1; case n: default :exit(0); getch(); return(0);