编译原理课程设计表达式求值.doc

《编译原理课程设计表达式求值.doc》由会员分享，可在线阅读，更多相关《编译原理课程设计表达式求值.doc（18页珍藏版）》请在三一文库上搜索。

1、湖南人文科技学院计算机系课程设计说明书 课 程 名 称: 编译原理 课 程 代 码： 1-10 题 目: 表达式求值 年级/专业/班:学 生 姓 名 学 号: 04356134 、04356110 、 04356122 指 导 教 师: 开 题 时 间: 2007 年 6 月 11 日完 成 时 间: 2007 年 6 月 25日目 录摘要2一、引言3二、设计任务与目的 3三、设计方案与实施1、总体设计42、详细设计43、程序清单64、程序调试与体会155、运行结果（截图）15四、结论15五、致谢16六、参考文献16摘要 在程序设计中，对表达式求值是程序设计语言编译中的一个最基本问题。与人们习

2、惯用的中缀表达式相比，后缀表达式不需要括号，没有优先级的差别，对表达式的计算是按照运算符出现的顺序进行计算的。因此非常适合串行工作的计算机进行处理。本课程设计将具体分析实现这中缀表达式到后缀表达式的转换，并给出求值算法和程序。关键词: 中缀表达式 后缀表达式 转换 计算Abstract In the design process, the evaluation of notation is a basic problem in the programming language complier. Unlike the frequently-used infix notation, postfi

3、x notation doesnt need brackets and has no priority differences of grades. Instead, the calculation is carried out in accordance with the order of the operators. Therefore, postfix notation are very suitable for the computers which process in a serial way. This course will be designed to achieve the

4、 transformation from infix notation into postfix notation by specific analysis and will give the methods of calculation and the procedures. Key words: infix notation postfix notation Conversion Calculation编译原理课程设计 -表达式求值一、 引言中缀表示法是算术表达式的常规表示法。称它为 中缀表示法是因为每个操作符都位于其操作数的中间，这种表示法只适用于操作符恰好对应两个操作数的时候（在操作符

5、是二元操作符如加、减、乘、除以及取模的情况下）。对以中缀表示法书写的表达式进行语法分析时，需要用括号和优先规则排除多义性,后缀表达式求值比直接对中缀表达式求值简单。在后缀表达式中，不需要括号，而且操作符的优先级也不再起作用了。后缀表达式较中缀表达式更加适合串行工作的计算机进行数据处理二、设计的目的与任务 任务：对任一输入的中缀表达式转换成相应的逆波兰式并对其求值. 目的：掌握中缀表达式转换后缀表达式（逆波兰式）的基本语法结构与转换方法。三：设计方案 1、总体设计 主要解决两个问题：（1）中缀表达式到后缀表达式的转换（2）后缀表达式的计算后缀表达式相对于输入表达式来说，起优点在于不需要括号。所以

6、方便的计算机的处理，通常对于后缀表达式才用栈的数据结果来实现，从左往右扫描表达式，如果遇到的是数字，则把数字压入栈中；若遇到的是运算符号，则提取栈的的2个元素进行计算，将计算结果压栈，若最后栈内只剩下一个数字，这就是后缀表达式的计算结果。2、详细设计建立两个栈：第一个位数字栈，第二个运算符栈！对输入的字符串一致读入： 1）如果是数字，就压入第一个栈， 2）如果是算符，（1）把这个算符于第二个栈的栈顶元素比较，若级别高，则再读入一个数字，用刚才读入的算符把这个数字和第一个栈的栈顶数字运算，结果压入第一个栈 ； （2）若低，则把它压入第二个栈3）当字符串读完后，就是弹栈了，弹出的表达式即为后缀表达

7、式。4）取两个数字和一个算符运算结果压入数字栈，循环一直到两栈空，最后弹出的数值即为表达式的值。3、程序清单#include#include#define TRUE 1#define FALSE 0#define MAXNUM 100typedef int DataType;struct SeqStack DataType sMAXNUM;int t;typedef struct SeqStack *PSeqStack;PSeqStack createEmptyStack_seq() PSeqStack pastack;pastack = (PSeqStack)malloc(sizeof(st

8、ruct SeqStack);if (pastack = NULL)printf(Out of space!n);elsepastack-t = -1;return pastack; int isEmptyStack_seq(PSeqStack pastack) return pastack-t = -1; void push_seq(PSeqStack pastack, DataType x) if (pastack-t = MAXNUM - 1) printf(Overflow!n);else pastack-t = pastack-t + 1; pastack-spastack-t =

9、x; void pop_seq(PSeqStack pastack) if (pastack-t = -1) printf(Underflow!n);else pastack-t = pastack-t - 1; DataType top_seq(PSeqStack pastack) return pastack-spastack-t; int infixtoSuffix(const char * infix, char * suffix) /*将中缀表达式转换为后缀表达式，顺利转换返回true，若转换过程中发现中缀表达式非法则返回false*/int state_int = FALSE; /

10、*state_int记录状态，等于true表示刚读入的是数字字符，等于false表示刚读入的不是数字字符，设置这个变量是为了在每输出一个整数后输出一个空格，以免连续输出的两个整数混在一起。*/char c, c2;PSeqStack ps = createEmptyStack_seq(); /*运算符栈*/int i, j = 0;if (infix0 = 0) return FALSE; /*不允许出现空表达式*/for (i = 0; infixi != 0; i+) c = infixi; switch (c) case : case t: case n: if (state_int =

11、 TRUE) suffixj+ = ;/*状态从true转换为false时输出一个空格*/ state_int = FALSE; break; /*遇到空格或制表符忽略*/ case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: case 9: state_int = TRUE; suffixj+ = c; /*遇到数字输出*/ break; case (: if (state_int = TRUE) suffixj+ = ;/*状态从true转换为false时输出一个空格*/ state_int = FA

12、LSE; push_seq(ps, c); /*遇到左括号，入栈*/ break; case ): if (state_int = TRUE) suffixj+ = ;/*状态从true转换为false时输出一个空格*/ state_int = FALSE; c2 = ); while (!isEmptyStack_seq(ps) c2 = top_seq(ps);/*取栈顶*/ pop_seq(ps); /*出栈*/ if (c2 = () break; suffixj+ = c2; if (c2 != () free(ps); suffixj+ = 0; return FALSE; bre

13、ak; case +: case -: if (state_int = TRUE) suffixj+ = ; state_int = FALSE; while(!isEmptyStack_seq(ps) c2 = top_seq(ps); if (c2 = + | c2 = - | c2 = * | c2 = /) pop_seq(ps); suffixj+ = c2; else if(c2=() break; push_seq(ps, c); break; case *: case /: if (state_int = TRUE) suffixj+ = ; state_int = FALSE

14、; while (!isEmptyStack_seq(ps) c2 = top_seq(ps); if (c2 = * | c2 = /) pop_seq(ps); suffixj+ = c2; else if(c2=+|c2=-|c2=() break; push_seq(ps, c); break; default: free(ps); suffixj+ = 0; return FALSE; if (state_int = TRUE) suffixj+ = ;while (!isEmptyStack_seq(ps) c2 = top_seq(ps); pop_seq(ps); if (c2

15、 = () free(ps); suffixj+ = 0; return FALSE; suffixj+ = c2; free(ps);suffixj+ = 0;return TRUE; int calculateSuffix(const char * suffix, int * presult) int state_int = FALSE; PSeqStack ps = createEmptyStack_seq(); int num = 0, num1, num2;int i;char c;for (i = 0; suffixi != 0; i+) c = suffixi; switch (

16、c) case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: case 9: if (state_int = TRUE) num = num * 10 + c - 0; else num = c - 0; state_int = TRUE; break; case : caset: case n: if (state_int = TRUE) push_seq(ps, num); state_int = FALSE; break; case +: case -: case *: case /: if (sta

17、te_int = TRUE) push_seq(ps, num); state_int = FALSE; if (isEmptyStack_seq(ps) free(ps); return FALSE; num2 = top_seq(ps); pop_seq(ps); if (isEmptyStack_seq(ps) free(ps); return FALSE; num1 = top_seq(ps); pop_seq(ps); if (c = +) push_seq(ps, num1 + num2); if (c = -) push_seq(ps, num1 - num2); if (c =

18、 *) push_seq(ps, num1 * num2); if (c = /) push_seq(ps, num1 / num2); break; default: free(ps); return FALSE; *presult = top_seq(ps); pop_seq(ps);if (!isEmptyStack_seq(ps) free(ps); return FALSE; free(ps);return TRUE; void getline(char * line, int limit) char c;int i = 0;while (i limit - 1 & (c = get

19、char() != EOF & c != n) linei+ = c;linei = 0; void main() char c, infixMAXNUM, suffixMAXNUM;int result;int flag = TRUE;while (flag = TRUE) printf(Plese input an infix expression!nInput:); getline(infix, MAXNUM); if(infixtoSuffix(infix, suffix) = TRUE) printf(suffix:%sn, suffix); else printf(Invalid

20、infix!n); printf(nContinue? (y/n); scanf(%c, &c); if (c = n | c = N) flag = FALSE; while (getchar() != n); printf(n); continue; if(calculateSuffix(suffix, &result) = TRUE) printf(Result:%dn, result); else printf(Invalid suffix!n); printf(nContinue? (y/n); scanf(%c, &c); if (c = n | c = N) flag = FAL

21、SE; while (getchar() != n); printf(n);4、程序调试与体会 要特别认真注意对二个栈的处理,并对输出结果与理论结果进行比较,其中数字的输入和算符的比较要多加仔细。5、运行结果（截图）四、结 论通过输入（2+3）*（4+5），运行，我们可以得出其后缀表达式为：2 3+4 5+*值为45，结果和理论一致。五、致 谢谢谢老师给了我们这次课程设计的机会，通过不断学习和自己动手，我深刻的掌握了对输入表达式转换成逆波兰表达式和求值的原理，更对以前学过的C语言程序设计和数据结构做了一次详细的复习。六、参考文献1编译原理程序设计 陈火旺等 国防工业出版社 2005年2C语言程序设计教程 杨路明等 北京邮电大学出版社 2004年 3 数据结构（c语言版）严蔚敏等 清华大学出版社 2004年课程设计任务书及成绩评定课题名称：_表达式求值_完 成 者： 梁赛明、梁觉丰、周永升 1、设计的目的与要求： 将中缀表达式转换为逆波兰表达式并对逆波兰表达式的计算2、设计进度及完成情况日 期内 容6.8-6.10了解设计目的和需求分析6.11-6.13总体设计6.14-6.16详细设计6.17-6.19调试分析6.20-6.22测试结果6.23-6.25递交老师修改并最终定型打印送交3、成绩评定：设计成绩： （教师填写）指导老师： （签字） 二00 年 月