逆波兰式

淮阴工学院

编译原理课程设计报告

选题名称:逆波兰式的生成

系（院）:计算机工程学院

专业:计算机科学与技术信息安全方向班级:信息1071

姓名:王猛学号:1071303122 指导教师:高丽

学年学期:2009 ~ 2010 学年第 2 学期2010年 6 月12 日

设计任务书

指导教师（签章）：

年月日

摘要：

编译原理是计算机科学与技术专业最重要的一门专业基础课程，内容庞大，涉及面广，知识点多。由于该课程教、学难度都非常大，往往费了大量时间而达不到预期教学效果俗语说：学习的最好方法是实践。本课程设计正是基于此，力求为学生提供一个理论联系实际的机会，通过布置一定难度的课题，要求学生独立完成。我们这次课程设计的主要任务是编程实现对输入合法的中缀表达式进行词法分析、语法分析，构造相应的逆波兰式，计算后缀表达式的值输出结果。逆波兰式也叫后缀表达式，即将运算符写在操作数之后。通过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索前言知识的习惯，树立团队协作精神。同时，课程设计可以充分弥补课堂教学及普通实验中知识深度与广度有限的缺陷，更好地帮助学生从全局角度把握课程体系。

关键字：逆波兰式；语法分析；中缀表达式

目录

1 课题综述 (1)

1.1 课题来源 (1)

1.2 课题意义 (1)

1.3 预期目标 (1)

1.4 面对的问题 (1)

1.5 需解决的关键技术 (1)

2 系统分析 (2)

2.1 基础知识 (2)

2.2 解决问题的基本思路 (3)

2.3 总体方案 (3)

3 系统设计 (4)

3.1 算法实现 (4)

3.2 流程图 (5)

4 代码编写 (6)

5 程序调试 (10)

6 运行与测试 (10)

总结 (11)

致谢 (12)

参考文献 (13)

1 课题综述

1.1 课题来源

在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，所以，这种表示法也称为中缀表示。对中缀表达式的计值，并非按运算符出现的自然顺序来执行其中的各个运算，而是根据算符间的优先关系来确定运算的次序，此外，还应顾及括号规则。因此，要从中缀表达式直接产生目标代码一般比较麻烦。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。

1.2 课题意义

对于实现逆波兰式算法，难度并不大，但为什么要将看似简单的中缀表达式转换为逆波兰式，原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中缀表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。

1.3 预期目标

编写程序，实现逆波兰式的生成和计算。首先对输入的表达式进行词法分析，然后进行语法分析，最后进行逆波兰式的输出和计算。过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索知识的习惯。

1.4 面对的问题

如何通过递归下降方法分析表达式，并且输出词法分析、语法分析过程及结果。如何实现把中缀表达式转换成后缀表达式，并计算表达式的结果。

1.5 需解决的关键技术

本次课程设计中的关键是：通过递归下降方法分析表达式，主要有词法分析和语法分析，输出分析结果，判断表达式是否合法。如何确定操作符的优先顺序，确定数据的进栈及出栈顺序，根据后缀表达式计算表达式的结果。以及如何编写、调试、修改代码。还要了解一个题目有许多种解决方法。锻炼我们的思维能力。

2 系统分析

2.1 基础知识

2.1.1 词法分析基本原理

词法分析程序完成的是编译第一阶段的工作。词法分析的作用是把符流的程序变为单词序列，输出在一个中间文件上，这个文件作为语法分析程序的输入而继续编译过程。

2.1.2 递归下降的原理

由于时间和技术的限制，语法分析采用递归下降的方法。递归下降法是语法分析中最易懂的一种方法。它的主要原理是，对每个非终极符按其产生式结构构造相应语法分析子程序，其中终极符产生匹配命令，而非终极符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。

2.1.3 递归下降分析的文法要求

递归下降法要满足的条件：假设A的全部产生式为A→α1|α2|……|αn ，则必须满足如下条件才能保证可以唯一的选择合适的产生式

predict(A→αi)∩predict(A→αj)=Φ，当i≠j。

2.1.4 后缀表达式基础知识

有的编译程序直接生成目标代码，有的编译程序采用中间代码。中间代码，也称中间语言，是复杂性介于源程序代码和机器语言的一种表示形式。一般快速编译程序直接生成目标代码，没有中间代码翻译成目标代码的额外开销。但是为了使编译程序在结构上更为简单明确，常采用中间代码，这样可以将与机器相关的某些实现细节置于代码生成阶段进行处理，并且可以在中间代码一级进行优化工作使得代码优化比较容易实现。编译程序所使用的中间代码有多种形式。我们采用的是逆波兰记号的形式。

逆波兰记号是最简单的一种中间代码表示形式，早在编译程序出现之前，它就用于表示算术表达式，是波兰逻辑学家卢卡西维奇发明的。

这种表示法将运算对象写在前面，把运算符写在后面，叫后缀表达式。后缀表示法表示表达式，其最大优点是易于计算机处理表达式。利用一个栈，自左向右扫描算术表达式。每碰到运算对象，就把它推进栈，碰到运算符，若该运算符

是二目的，则对栈顶部的两个运算对象实施运算，并将运算结果代替运算对象而进栈。若是一目运算符，则对栈顶元素执行该运算，并以运算结果代替元素进栈。最后的结果留在栈顶。

2.2 解决问题的基本思路

根据课程设计的要求，程序应具有如下功能：对输入的表达式进行分析并输出逆波兰式。由于对算数表达式的分析过程比较简单，这里采用递归下降的分析方法。首先对输入的表达式进行词法分析，分析的结果作为语法分析的输入。然后进行语法分析，语法分析采用递归下降的分析方法。最后输出生成的逆波兰式并进行运算。

2.3 总体方案

启动VC++，新建源程序并进行编程，程序的功能模块图如图2-1所示。

图2-1 程序功能模块图

3 系统设计

3.1 算法实现

将一个普通的中序表达式转换为逆波兰表达式的一般算法是：

1 首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。

2 读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。

3 从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。

4 如果不是数字，该字符则是运算符，此时需比较优先关系。

做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将栈顶的运算符从栈中弹出，直到栈顶运算符的优先级低于当前运算符，将该字符入栈。

5 重复上述操作1-2直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。

转换的基本思路：

1 在表达式字符串的末尾加一个代表结束的辅助符，比如“#”。

2 从头开始扫描表达式，并判断当前的每一个字符。

3 取当前的一个字符，如果当前字符是代表数字，则进逆波兰式的栈，如果是运算符，则转入4，如果是“#”，则结束。

4 比较当前运算符与临时栈中的栈顶运算符，如果栈顶运算符比当前运算符优先级高，则弹出一个运算符放进逆波兰式栈中，并继续4。否则把当前运算符进临时栈，转入2。

图3-1 程序流程图

4 代码编写

在这次课程设计过程中，我主要负责的是语法分析模块，在词法分析的基础上将词法分析的结果作为语法分析的输入，语法分析采用递归下降的分析方法，部分代码如下。

int E1()

{

int f,t;

printf("%d\tE-->TG\t",total);total++;

flag=1;

input();

input1();

f=T();

if (f==0) return(0);

t=G();

if (t==0) return(0);

else return(1);

}

int E()

{

int f,t;

printf("%d\tE-->TG\t",total);total++;

e[0]='E';e[1]='=';e[2]='>';e[3]='T';e[4]='G';e[5]='#';

output();

flag=1;

input();

input1();

f=T();

if (f==0) return(0);

t=G();

if (t==0) return(0);

else return(1);

}

int T()

{

int f,t;

printf("%d\tT-->FS\t",total);total++;

e[0]='T';e[1]='=';e[2]='>';e[3]='F';e[4]='S';e[5]='#';

output();

flag=1;

input();

input1();

f=F();

if (f==0) return(0);

t=S();

if (t==0) return(0);

else return(1);

}

int G()

{

int f;

if(ch=='+') {

b[i1]=ch;

printf("%d\tG-->+TG\t",total);total++;

e[0]='G';e[1]='=';e[2]='>';e[3]='+';e[4]='T';e[5]='G';e[6]='#';

output();

flag=0;

input();input1();

ch=a1[++i1];

f=T();

if (f==0) return(0);

G();

return(1);

}

printf("%d\tG-->^\t",total);total++;

e[0]='G';e[1]='=';e[2]='>';e[3]='^';e[4]='#';

output();

flag=1;

input();input1();

return(1);

}

int S()

{

int f,t;

if(ch=='*') {

b[i1]=ch;printf("%d\tS-->*FS\t",total);total++;

e[0]='S';e[1]='=';e[2]='>';e[3]='*';e[4]='F';e[5]='S';e[6]='#';

output();

flag=0;

input();input1();

ch=a1[++i1];

f=F();

if (f==0) return(0);

if (t==0) return(0);

else return(1);}

printf("%d\tS-->^\t",total);total++;

e[0]='S';e[1]='=';e[2]='>';e[3]='^';e[4]='#';

output();

flag=1;

a1[i1]=ch;

input();input1();

return(1);

}

int F()

{

int f;

if(ch=='(') {

b[i1]=ch;printf("%d\tF-->(E)\t",total);total++;

e[0]='F';e[1]='=';e[2]='>';e[3]='(';e[4]='E';e[5]=')';e[6]='#';

output();

flag=0;

input();input1();

ch=a1[++i1];

f=E();

if (f==0) return(0);

if(ch==')') {

b[i1]=ch;printf("%d\tF-->(E)\t",total);total++;

flag=0;input();input1();

ch=a1[++i1];

}

else {

printf("error\n");

return(0);

}

}

else if(ch=='i') {

b[i1]=ch;printf("%d\tF-->i\t",total);total++;

e[0]='F';e[1]='=';e[2]='>';e[3]='i';e[4]='#';

output();

flag=0;input();input1();

ch=a1[++i1];

}

else {printf("error\n");return(0);}

}

void yufa() /*递归分析*/

{

int f,p,j=0;

char x;

d[0]='E';

d[1]='=';

d[2]='>';

d[3]='T';

d[4]='G';

d[5]='#';

j=strlen(a1);

a1[j]='#';

n1=j;

ch=b[0]=a1[0];

cout<

printf("步骤\t文法\t分析串\t\t分析字符\t剩余串\n");

f=E1();

if (f==0) return;

if (ch=='#')

{

printf("accept\n");

p=0;

x=d[p];

while(x!='#') {

printf("%c",x);p=p+1;x=d[p]; /*输出推导式*/

}

}else {

printf("error\n");

getchar();

return;

}

printf("\n");

getchar();

}

5 程序调试

程序中调用了许多函数，编写代码时会出现调用的错误，使在程序运行时无法正确判断以致程序运行出错。在创建函数时会出现错误而无法得知，致使在程序运行时出错，需要很细心的去编写代码。编程的时候一定要细心，对出现的错误要认真调整，反复修改，使函数前后相对应。

6 运行与测试

运行界面如下：

图5-1 运行结果

总结

在经过了一个星期的软件实习后，我获益匪浅。编译原理课程设计是我们将所学理论知识形成系统的一个锻炼的好机会，也是学校和老师检验我们学习成果的一个方法。经过一周的设计，实现逆波兰式的生成。其功能能够分析算术表达式，显示词法分析和语法分析的结果，并显示算术表达式的后缀形式，计算后缀表达式的值，显示结果。

这次的课程设计已经结束了，通过编程实现了预期的目标，管如此，VC++不断地探索和研究，在程序实现的过程中出现过许多没有想到的功能，原本设计的思路和方法，到真正的程序中运行的时候就达不到预想的效果。因此，我感觉编程序实际操作是非常重要的，不亲自实践就不会发现问题，我们只有不断的发现问题，不断的解决问题，才能使一个程序尽可能的完善。由于经验不足，时间有限，虽然在一周的时间里顺利的完成了系统的分析、设计和调试的工作，但是仍然有许多不足之处，我会在将来的软件设计过程中引以为戒。在做课程设计期间，有目的的去学习一些将要用到的东西，仔细的考虑工作流程的规律和步骤，充分的利用手中的开发工具，使自己的开发在代码上实现少而精确，能够尽量简单的进行操作。

当我即将完成这个设计的时候我终于认清楚了以前老师经常提起的一个问题，那就是：一个软件开发的过程中编码不是重要的，重要的是对分析系统以及系统模型的建立。有了一个好的系统模型之后，我们再将其划分成几个模块，那样做起来就会容易得多。通过这个课程设计让我有了深刻的了解，增长了自己的动手能力，而且我认识到团队合作也十分重要。通过这次课程设计不仅锻炼了我学习能力，在团队合作上也有很大提高。

致谢

在这次的课程设计中，让我深深地体现到编程不是一件简单的事情，它需要设计者具有全面的专业知识、缜密的思维、严谨的工作态度以及较高的分析问题、解决问题的能力，而我在很多方面还有欠缺。首先我要感谢淮阴工学院、计算机工程系提供的实践机会，实验室人员提供的实验环境，以及指导老师的悉心教导。因为课程设计不仅是学校和老师对我学习成果的一个统筹检测的方法，也是我将所学理论知识形成系统的一个锻炼的好机会。经过一个星期的时间，我不仅对操作环境有了更新的了解，更是掌握了程序设计的基本步骤，同时也对Visual C++有了更深的了解和掌握。

其次我要感谢同学们的帮助，以及其他提供过帮助的所有人。在课程设计的过程中，我查阅了大量的资料，也上网搜索了许多资料。但还是有不会做的地方，于是我去请教同学，他们都很热情的讲给我听并且还帮我上机调试，我真的很感谢他们。

最后，我要向给予我悉心指导和帮助的各位老师表示衷心的感谢和诚挚的敬意。因为在本次课程设计中，我从几位老师身上学到了很多东西，他们认真负责的工作态度，严谨的治学精神和深厚的理论水平都使我收益匪浅。他们无论在理论上还是在实践中，都给与我很大的帮助，使我得到不少的提高。这对于我以后的工作和学习都有一种巨大的帮助，感谢他们耐心的辅导。同时也感谢其他老师对我技术上的指导，由于经验不足，时间有限，虽然在近一个星期时间里顺利的完成了程序的调研、分析、设计和调试的工作，但是仍然有许多不足之处，我会在将来的软件设计过程中引以为戒。

参考文献

1高丽.编译原理课程设计指导书.淮阴工学院计算机工程系，2008

2 殷人昆，陶永雷等.面向对象方法与C++.清华大学出版社，1999

3 Bjarne Stroustrup. C++程序设计语言(特别版).高等教育出版社，2006 4於春景.实用C++调试指南.华中理工大学出版社，2006

5于永彦，于长辉.程序设计指导书，2006

6黄迪明.C++程序设计基础.电子工业出版社，2003

附录：代码

#include "dos.h"

#include "stdio.h"

#include "string.h"

#include "stdlib.h"

#include "iostream.h"

#define LEFTP 4

#define RIGHP 5

#define STARTEND 6

#define NO 32767

#define STACKSIZE 20

char a1[50] ,b[50],d[500],e[10]; char ch;

int n1,i1=0,flag=1,n=5;

int total=0;/*步骤计数器*

int E();

int E1();

int T();

int G();/*E’*/

int S();/*T’*/

int F();

void input()

{

int j=0;

for (;j<=i1-flag;j++)

printf("%c",b[j]);

/*输出分析串*/

printf("\t\t");

printf("%c\t\t",ch);

/*输出分析字符*/

}

void input1()

{

int j;

for (j=i1+1-flag;j

printf("%c",a1[j]);

/*输出剩余字符*/

printf("\n");

}

void

output(){

/*推导式计算*/

int m,k,j,q;

int i=0;

m=0;k=0;q=0;

i=n;

d[n]='=';d[n+1]='>';d[n+2]='#';n=n+2;i=n;

i=i-2;

while(d[i]!='>'&&i!=0){i=i-1;}

i=i+1;

while(d[i]!=e[0]){i=i+1;}

q=i;

m=q;k=q;

while(d[m]!='>'){m=m-1;}

m=m+1;

while(m!=q)

{d[n]=d[m];m=m+1;n=n+1;}

d[n]='#';

for(j=3;e[j]!='#';j++){

d[n]=e[j];

n=n+1;

}

k=k+1;

while(d[k]!='=') {

d[n]=d[k];n=n+1;k=k+1;

}

d[n]='#';

}

int E1()

{

int f,t;

printf("%d\tE-->TG\t",total);total++;

flag=1;

input();

input1();

f=T();

if (f==0) return(0);

t=G();

if (t==0) return(0);

else return(1);

}

int E()

{

int f,t;

printf("%d\tE-->TG\t",total);total++;

e[0]='E';e[1]='=';e[2]='>';e[3]='T';e[4]='G';e[5] ='#';

output();

flag=1;

input();

input1();

f=T();

if (f==0) return(0);

t=G();

if (t==0) return(0);

else return(1);

}

int T()

{

int f,t;

printf("%d\tT-->FS\t",total);total++;

e[0]='T';e[1]='=';e[2]='>';e[3]='F';e[4]='S';e[5] ='#';

output();

flag=1;

input();

input1();

f=F();

if (f==0) return(0);

t=S();

if (t==0) return(0);

else return(1);

}

int G()

{

int f;

if(ch=='+') {

b[i1]=ch;

printf("%d\tG-->+TG\t",total);total++;

e[0]='G';e[1]='=';e[2]='>';e[3]='+';e[4]='T';e[5] ='G';e[6]='#';

output();

flag=0;

input();input1();

ch=a1[++i1];

f=T();

if (f==0) return(0);

G();

return(1);

}

printf("%d\tG-->^\t",total);total++;

e[0]='G';e[1]='=';e[2]='>';e[3]='^';e[4]='#';

output();

flag=1;

input();input1();

return(1);

}

int S()

{

int f,t;

if(ch=='*') {

b[i1]=ch;printf("%d\tS-->*FS\t",total);total++ ;

e[0]='S';e[1]='=';e[2]='>';e[3]='*';e[4]='F';e[5] ='S';e[6]='#';

output();

flag=0;

input();input1();

ch=a1[++i1];

f=F();

if (f==0) return(0);

t=S();

if (t==0) return(0);

else return(1);}

printf("%d\tS-->^\t",total);total++;

e[0]='S';e[1]='=';e[2]='>';e[3]='^';e[4]='#';

output();

flag=1;

a1[i1]=ch;

input();input1();

return(1);

}

int F()

{

int f;

if(ch=='(') {

b[i1]=ch;printf("%d\tF-->(E)\t",total);total++;

e[0]='F';e[1]='=';e[2]='>';e[3]='(';e[4]='E';e[5] =')';e[6]='#';

output();

flag=0;

input();input1();

ch=a1[++i1];

f=E();

if (f==0) return(0);

if(ch==')') {

b[i1]=ch;printf("%d\tF-->(E)\t",total);total++;

flag=0;input();input1();

ch=a1[++i1];

}

else {

printf("error\n");

return(0);

}

}

else if(ch=='i') {

b[i1]=ch;printf("%d\tF-->i\t",total);total++;

e[0]='F';e[1]='=';e[2]='>';e[3]='i';e[4]='#';

output();

flag=0;input();input1();

ch=a1[++i1];

}

else {printf("error\n");return(0);}

return(1);

}

void InputExpression(char str[])

{ int len;

printf("******************************* **********\n");

printf("*逆波兰式的生成*\n");

printf("******************************************\n");

printf("请输入一个算术表达式:");

scanf("%s",str);

len=strlen(str);

str[len]='#';

str[len+1]='\0';

}

bool IsNumber(char ch)

{

if(((ch>='0')&&(ch<='9'))||ch=='.')

return true;

else

return false;

}

void cifa(char str[])

{

cout<

int i=0,j=0;

while(str[i]!='#')

{

if(IsNumber(str[i]))

{

cout<<"数字"<<' ';

while(IsNumber(str[i])){cout<

a1[j++]='i';cout<

}

else if(str[i]=='('||str[i]==')')

{

cout<<"括号"<<' '<

a1[j++]=str[i];

i++;

}

else if(str[i]=='*'||str[i]=='/')

{

cout<<"乘除"<<' '<

a1[j++]='*';

i++;

}

else if(str[i]=='+'||str[i]=='-')

语法制导把表达式翻译成逆波兰式

实验报告成绩：指导教师审核（签名）：年月日 预习报告□实验报告□ 语法制导把表达式翻译成逆波兰式 (一)实验目的 进一步掌握语法制导翻译的概念，理解中间语言，设计出错处理程序方法，掌握把表达式翻译成中间语言的算法。 (二)实验内容 1．从左到右扫描中缀表达式，经语法分析找出中缀表达式出现的错误并给出错误的具体位置和类型。一个运算符栈存放暂时不能出现的运算符，逆波兰区存放逆波兰表达式。 2．测试所编程序，给出正确和错误的结果。 (三)实验要求 1．学生课前要认真阅读实验指导，理解实验内容与相关理论知识的关系，并完成预习报告 2．用C语言或其它高级语言编写程序 3．写出实验报告

实验报告成绩：指导教师审核（签名）：年月日 预习报告□实验报告□ 语法制导把表达式翻译成逆波兰式 (一)实验目的 通过上机实习加深对语法指导翻译原理的理解，掌握运算符优先权的算法，将语法分析所识别的表达式变换成中间代码的翻译方法。 (二)实验内容 同预习报告 (三)实验要求 1.学生课前要认真阅读实验指导，理解实验内容与相关理论知识的关系，并完成预习报告 2．用C语言或其它高级语言编写程序 3．写出实验报告 (四)实验设计思路 1）表达式生成逆波兰式的算法 1、初始化△送到运算符栈。 2、扫描左括号“（”，把△送到运算符栈。 3、扫描到变量，把它送到逆波兰区。 4、扫描到运算符 ( 1)栈内运算符比较 a.栈内运算符>=栈外运算符，把栈内运算符送到逆波兰区。 b.栈内运算符<栈外运算符，把栈外运算符入栈。 ( 2 ) 栈内是△把运算符入栈。 5、扫描右括号“)”。 ( 1 )栈内是运算符，把栈内运算符送到逆波兰区。 ( 2 )栈内是△则△退栈，读入下一个字符。 6、扫描到#（结束符） ( 1 )栈内是运算符，把栈内运算符送到逆波兰区。 ( 2 )栈内是△结束，否则继续分析。

(编译原理)逆波兰式算法的源代码

一.实验目的 1．深入理解算符优先分析法 2．掌握FirstVt和LastVt集合的求法有算符优先关系表的求法 3．掌握利用算符优先分析法完成中缀表达式到逆波兰式的转化 二.实验内容及要求 将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。 程序输入/输出示例： 输出的格式如下： (1) (2)输入一以#结束的中缀表达式(包括+—*/（）数字#) (3) (4)逆波兰式 备注：(1)在生成的逆波兰式中如果两个数相连则用&分隔，如28和68，中间用&分隔； 注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、数字，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）； 3.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照； 三.实验过程 1、逆波兰式定义 将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。采用逆波兰式可以很好的表示简单算术表达式，其优点在于易于计算机处理表达式。 2、产生逆波兰式的前提 中缀算术表达式 3、逆波兰式生成的实验设计思想及算法

(1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。 (2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。 (3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。 (4)如果不是数字，该字符则是运算符，此时需比较优先关系。 做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算

编译原理-逆波兰式的产生及计算

编译原理上机报告 名称：逆波兰式的产生及计算 学院：信息与控制工程学院 专业：计算机科学与技术 班级：计算机1401班 姓名：叶达成 2016年11月4日

一、上机目的 通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。 1、选择最有代表性的语法分析方法，如LL(1) 语法分析程序、算符优先分析程序和LR分析分析程序，并至少完成两个题目。 2、选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。 ⑴实验前的准备 按实验的目的和要求，编写语法分析程序，同时考虑相应的数据结构。 ⑵调试 调试例子应包括符合语法规则的算术表达式，以及分析程序能够判别的若干错例。 ⑶输出 对于所输入的算术表达式，不论对错，都应有明确的信息告诉外界。 ⑷扩充 有余力的同学，可适当扩大分析对象。譬如： ①算术表达式中变量名可以是一般标识符，还可含一般常数、数组元素、函数调用等等。 ②除算术表达式外，还可扩充分析布尔、字符、位等不同类型的各种表达式。③加强语法检查，尽量多和确切地指出各种错误。 二、基本原理和上机步骤 基本原理： 将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。采用逆波兰式可以很好的表示简单算术表达式，其优点在于易于计算机处理表达式。 上机步骤： (1)构造一个栈，存放运算对象。 (2)读入一个用逆波兰式表示的简单算术表达式。 (3)自左至右扫描该简单算术表达式并判断该字符，如果该字符是运算对象，则将该字符入栈。若是运算符，如果此运算符是二目运算符，则将对栈顶部的两个运算对象进行该运算，将运算结果入栈，并且将执行该运算的两个运算对象从栈顶弹出。如果该字符是一目运算符，则对栈顶部的元素实施该运算，将该栈顶部的元素弹出，将运算结果入栈。 (4)重复上述操作直至扫描完整个简单算术表达式的逆波兰式，确定所有字符都得到正确处理，我们便可以求出该简单算术表达式的值。 三、上机结果 程序清单： #include #include #include #include #include #include using namespace std;

编译原理-实验报告4-逆波兰

计算机硬件实验室实验报告 姓名学号班级成绩 设备名称及软件环境逆波兰 一、实验目的： 将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。 二、实验要求： 输出的格式如下： (1)逆波兰式的生成及计算程序，编制人：姓名，学号，班级 (2)输入一以#结束的中缀表达式(包括+—*/（）数字#)：在此位置输入符 号串如(28+68)*2# (3)逆波兰式为：28&68+2* (4)逆波兰式28&68+2*计算结果为192 备注：(1)在生成的逆波兰式中如果两个数相连则用&分隔，如28和68，中间用&分隔； (2)在此位置输入符号串为用户自行输入的符号串。 注意： 1.表达式中允许使用运算符（+-*/）、分割符（括号）、数字，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）； 三、实验过程： （一）准备： 1.阅读课本有关章节， 2.考虑好设计方案； 3.设计出模块结构、测试数据，初步编制好程序。 （1）定义部分：定义常量、变量、数据结构。 （2）初始化：设立算符优先分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）； （3）控制部分：从键盘输入一个表达式符号串； （4）利用算符优先分析算法进行表达式处理：根据算符优先分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。 （5）对生成的逆波兰式进行计算。 （二）上课上机： 将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。 四、实验结果 （1）写出程序流程图 （2）给出运行结果

程序： #include #include #include #define max 100 char ex[max]; /*存储后缀表达式*/ void trans(){ /*将算术表达式转化为后缀表达式*/ char str[max]; /*存储原算术表达式*/ char stack[max]; /*作为栈使用*/ char ch; int sum,i,j,t,top=0; // printf("*****************************************\n"); printf("逆波兰式的生成及计算程序，编制人：武普泉，20号，1020562班\n"); printf("输入一以#结束的中缀表达式(包括+ - * /（）数字# )："); // printf("******************************************\n"); // printf("算数表达式："); i=0; /*获取用户输入的表达式*/ do{ i++; scanf("%c",&str[i]); }while(str[i]!='#' && i!=max); sum=i; t=1;i=1; ch=str[i];i++; while(ch!='#'){ switch(ch){ case '(': /*判定为左括号*/ top++;stack[top]=ch; break; case ')': /*判定为右括号*/ while(stack[top]!='('){ ex[t]=stack[top];top--;t++; } top--; break; case '+': /*判定为加减号*/ case '-': while(top!=0&&stack[top]!='('){ ex[t]=stack[top];top--;t++; } top++;stack[top]=ch; break; case '*': /*判定为乘除号*/ case '/':

中缀表达式转逆波兰式并求值

中缀表达式转逆波兰式并求值 // 标题: 栈的应用——中缀表达式转逆波兰式 // 时间: 2015年4月14日// 所有者: Vae #include #include #include #include #include #define STACK_INIT_SIZE 100 #define STACKCREATE 10 #define OK 1 #define ERROR 0 typedef struct double_stack { int *num; int *index; }DOUBLESTACK; typedef struct SqStack { DOUBLESTACK top; DOUBLESTACK base; int stacksize; }SqStack; // 函数名: InitStack // 形参类型: SqStack * // 函数功能构造一个栈void InitStack(SqStack *S) { S->base.index = (int *)malloc(sizeof(int)*STACK_INIT_SIZE);

S->base.num = (int *)malloc(sizeof(int)*STACK_INIT_SIZE); if (!(S->base.num && S->base.index)) { printf("构造栈失败!\n"); exit(-1); } S->top.num = S->base.num; S->top.index = S->base.index; S->stacksize = STACK_INIT_SIZE; return ; } // 函数名: Push // 形参类型: SqStack *, int, int // 函数功能插入e为新的栈顶元素int Push(SqStack *S, int m, int n) { if ((S->top.num - S->base.num) >= S->stacksize) { S->base.index = (int *)realloc(S- >base.index,sizeof(int)*(STACK_INIT_SIZE+STACKCREATE)); S->base.num = (int *)realloc(S- >base.num,sizeof(int)*(STACK_INIT_SIZE+STACKCREATE)); if (!(S->base.num || S->base.index))

编译原理波兰式和四元式

实验三波兰式和四元式及计算 课程编译原理实验名称波兰式和四元式第页班级11计本学号姓名 实验日期：2013年月日报告退发(订正、重做) 一、实验目的： 将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。 二、实验说明 1、逆波兰式定义 将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。采用逆波兰式可以很好的表示简单算术表达式，其优点在于易于计算机处理表达式。 2、产生逆波兰式的前提 中缀算术表达式 3、逆波兰式生成的实验设计思想及算法

(1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。 (2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。 (3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。 (4)如果不是数字，该字符则是运算符，此时需比较优先关系。 做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。 (5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得 到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。 3、逆波兰式计算的实验设计思想及算法 (1)构造一个栈，存放运算对象。 (2)读入一个用逆波兰式表示的简单算术表达式。 (3)自左至右扫描该简单算术表达式并判断该字符，如果该字符是运算对 象，则将该字符入栈。若是运算符，如果此运算符是二目运算符，则将对栈顶部的两个运算对象进行该运算，将运算结果入栈，并且将执行该运算的两个运算对象从栈顶弹出。如果该字符是一目运算符，则对栈顶部的元素实施该运算，将该栈顶部的元素弹出，将运算结果入栈。 (4)重复上述操作直至扫描完整个简单算术表达式的逆波兰式，确定所有 字符都得到正确处理，我们便可以求出该简单算术表达式的值。

编译原理实验 中间代码生成

实验四中间代码生成 一．实验目的： 掌握中间代码的四种形式（逆波兰式、语法树、三元式、四元式）。 二．实验内容： 1、逆波兰式定义:将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表 达式也称做后缀式。 2、抽象（语法）树：运算对象作为叶子结点，运算符作为内部结点。 3、三元式：形式序号：（op,arg1,arg2） 4、四元式：形式（op,arg1,arg2,result） 三、以逆波兰式为例的实验设计思想及算法 (1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。 (2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。 (3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。 (4)如果不是数字，该字符则是运算符，此时需比较优先关系。 做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。 (5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。 四、程序代码： //这是一个由中缀式生成后缀式的程序 #include<> #include<> #include<> #include<> #define maxbuffer 64 void main() { char display_out(char out_ch[maxbuffer], char ch[32]); //int caculate_array(char out_ch[32]); static int i=0; static int j=0; char ch[maxbuffer],s[maxbuffer],out[maxbuffer]; cout<<"请输入中缀表达式: ";

逆波兰式

塔里木大学信息工程学院 论文 编译原理课程设计 课目：编译原理 学生姓名：\ 学号： 学生姓名 学号： 所属学院：信息工程学院 班级：

设计任务书 指导教师（签章）： 年月日

摘要： 编译原理是计算机科学与技术专业最重要的一门专业基础课程，内容庞大，涉及面广，知识点多。编译原理旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。它是计算机科学与技术专业最重要的一门专业基础课程，内容庞大，涉及面广，知识点多。由于该课程教、学难度都非常大，往往费了大量时间而达不到预期教学效果俗语说：学习的最好方法是实践。本课程设计正是基于此，力求为学生提供一个理论联系实际的机会，通过布置一定难度的课题，要求学生独立完成。我们这次课程设计的主要任务是编程实现对输入合法的中缀表达式进行词法分析、语法分析，构造相应的逆波兰式，计算后缀表达式的值输出结果。比如中缀表达式：C*(E+F)，其后缀表达式为：CEF+*。逆波兰式也叫后缀表达式，即将运算符写在操作数之后。通过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索前言知识的习惯，树立团队协作精神。同时，课程设计可以充分弥补课堂教学及普通实验中知识深度与广度有限的缺陷，更好地帮助学生从全局角度把握课程体系。 关键字：逆波兰式；语法分析；中缀表达式

1 课设综述 1.1 课设来源 在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，所以，这种表示法也称为中缀表示。对中缀表达式的计值，并非按运算符出现的自然顺序来执行其中的各个运算，而是根据算符间的优先关系来确定运算的次序，此外，还应顾及括号规则。因此，要从中缀表达式直接产生目标代码一般比较麻烦。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。 1.2 设计意义 对于实现逆波兰式算法，难度并不大，但为什么要将看似简单的中缀表达式转换为逆波兰式，原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中缀表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。在逆波兰式中，不存在运算符的优先级问题，也不存在任何括号，计算的顺序完全按照运算符出现的先后次序进行。比中缀表达式的求值要简单得多。1.3 设计目标 编写程序，实现逆波兰式的生成和计算。首先对输入的表达式进行词法分析，然后进行语法分析，最后进行逆波兰式的输出和计算。过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索知识的习惯。 1.4 遇到的问题 如何通过递归下降方法分析表达式，并且输出词法分析、语法分析过程及结果。如何实现把中缀表达式转换成后缀表达式，并计算表达式的结果。 1.5 需解决的关键技术 本次课程设计中的关键是：通过递归下降方法分析表达式，主要有词法分析和语法分析，输出分析结果，判断表达式是否合法。如何确定操作符的优先顺序，确定数据的进栈及出栈顺序，根据后缀表达式计算表达式的结果。以及如何编写、调试、修改代码。还要了解一个题目有许多种解决方法。锻炼我们的思维能力。

编译原理-逆波兰式的产生及计算

学号07 成绩 编译原理上机报告 名称：逆波兰式的产生及计算 学院：信息与控制工程学院 专业：计算机科学与技术 班级：计算机1401班 姓名：叶达成 2016年11月4日

一、上机目的 通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。 1、选择最有代表性的语法分析方法，如LL(1) 语法分析程序、算符优先分析程序和LR分析分析程序，并至少完成两个题目。 2、选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。 ⑴实验前的准备 按实验的目的和要求，编写语法分析程序，同时考虑相应的数据结构。 ⑵调试 调试例子应包括符合语法规则的算术表达式，以及分析程序能够判别的若干错例。 ⑶输出 对于所输入的算术表达式，不论对错，都应有明确的信息告诉外界。 ⑷扩充 有余力的同学，可适当扩大分析对象。譬如： ①算术表达式中变量名可以是一般标识符，还可含一般常数、数组元素、函数调用等等。 ②除算术表达式外，还可扩充分析布尔、字符、位等不同类型的各种表达式。③加强语法检查，尽量多和确切地指出各种错误。 二、基本原理和上机步骤 基本原理： 将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。采用逆波兰式可以很好的表示简单算术表达式，其优点在于易于计算机处理表达式。 上机步骤： (1)构造一个栈，存放运算对象。 (2)读入一个用逆波兰式表示的简单算术表达式。 (3)自左至右扫描该简单算术表达式并判断该字符，如果该字符是运算对象，则将该字符入栈。若是运算符，如果此运算符是二目运算符，则将对栈顶部的两个运算对象进行该运算，将运算结果入栈，并且将执行该运算的两个运算对象从栈顶弹出。如果该字符是一目运算符，则对栈顶部的元素实施该运算，将该栈顶部的元素弹出，将运算结果入栈。 (4)重复上述操作直至扫描完整个简单算术表达式的逆波兰式，确定所有字符都得到正确处理，我们便可以求出该简单算术表达式的值。 三、上机结果 程序清单： #include #include<> #include<> #include #include #include using namespace std;

对逆波兰式计算的程序设计

数据结构作业报告逆波兰式的计算

一题目内容 逆波兰式也叫后缀表达式(将运算符写在操作数之后) 如：我们平时写a+b，这是中缀表达式，写成后缀表达式就是：ab+ (a+b)*c-(a+b)/e的后缀表达式为： (a+b)*c-(a+b)/e →((a+b)*c)((a+b)/e)- →((a+b)c*)((a+b)e/)- →(ab+c*)(ab+e/)- →ab+c*ab+e/- 计算给出的逆波兰式（假设条件：逆波兰表达式由单字母变量和双目四则运算符构成，以’#‘作为结束标志）。 二题目分析 逆波兰式即后缀表达式，运算符置于两个操作数之后。运算实应从前往后依次读出两个运算数，与这两个运算数之后的运算符进行计算，然后再从前往后提取两个操作数，再从之后提取对应的运算符，直到计算完毕。这与栈的功能相一致，建立一个栈结构，将表达式的各个字符依次读取，若是数字则放入栈中，，若是操作符则从栈中提取两个数字进行运算，将运算结果加入到栈中，直至运算完毕。

三程序描述 首先定义相关数值，建立栈结构的数据类型 typedef struct{ SElemType *base; SElemType *top; int stacksize; }SqStack; 之后是各个对栈的操作函数 Status InitStack(SqStack &S){ S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElem Type)); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; }//建立空栈 Status Push(SqStack &S,SElemType e){ if(S.top-S.base>=S.stacksize){ S.base=(SElemType*)malloc(S.base,(S.stacksize+STACKINCREME NT)*sizeof(SElemTYpe)); if(!S.base)exit(OVERFLOW);

逆波兰式求值

一、需求分析 1．从键盘中输入一个后缀表达式，该表达式包括加减乘除等操作符，以及正整数做诶操作数等。 2．需要利用堆栈来实现。 3．在Visual C++6.0界面操作。 问题描述： 读入一个后缀表达式，利用堆栈来计算该表达式的值，同时要校验后缀表达式是否正确。 测试数据用例 （1）输入：2 3 * 1 - # 输出：5 （2）输入：2 3 * 1 - * # 输出：表达式有误 （3）输入： 2 0 / 4 * # 输出：表达式有误 二、概要设计 抽象数据类型 为实现上述程序的功能，则以字符型数据存储用户的输入。若为数值，则用自定义函数将其转化为整形数据；若为操作符，则仍为字符型数据，以便计算出的结果。 算法的基本思想 根据题目要求，采用堆栈来实现。该算法的基本思想是运用自定义函数求解逆波兰表达式求值问题问题。 程序的流程 程序由三个模块组成： （1）输入模块：完成表达式的输入，存入栈S中。 （2）计算模块：利用自定义函数，计算逆波兰表达式的值。 （3）输出模块：屏幕上显示出最终计算结果。 三、详细设计

物理数据类型 程序中要求输入的表达式为任意的，但必须以#标志表达式输入的结束，只有正确的逆波兰表达式才能显示出最终计算结果。 算法的具体步骤 算法的具体步骤为： 建立一个名为s的栈。 将表达式的值一个个压入栈S中。在循环中，需要分类讨论：如果表达式中的值为“#”，则将#前的元素弹出栈中；如果表达式中的值为空格，那么继续压入，如果表达式中的值为0至9的字符，则要通过一个自定义的转换函数将其转换为int型数值；如果连续几个0至9的字符中间无空格隔开，则在计算中应将其还原为多位数；若表达式中的值为运算符，则要将栈S中所压入数值弹出栈，进行相应的计算后，再将结果压入栈中（值得注意的是，运算符是不入栈的）；除此之外的情况都归类为输入的表达式错误。 相应的入栈出栈及数值计算部分都由自定义函数来完成。 输入和输出的格式 输入 在字符界面上输入一个后缀表达式，其中两相邻操作数之间利用空格隔开。以“#”表示结束。 输出 如果该后缀表达式正确，那么在字符界面上输出其结果，计算结果小数点后面保留两位有效数字，如果不正确，请在字符界面上输出表达式错误提示。 四、调试分析 略。（已在老师面前调试） 五、测试结果

编译原理逆波兰式算法的源代码

(编译原理)逆波兰式算法的源代码

————————————————————————————————作者：————————————————————————————————日期：

一.实验目的 1．深入理解算符优先分析法 2．掌握FirstVt和LastVt集合的求法有算符优先关系表的求法 3．掌握利用算符优先分析法完成中缀表达式到逆波兰式的转化 二.实验内容及要求 将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。 程序输入/输出示例： 输出的格式如下： (1)逆波兰式的生成及计算程序，编制人：姓名，学号，班级 (2)输入一以#结束的中缀表达式(包括+—*/（）数字#)：在此位置输入符号串如(28+68)*2# (3)逆波兰式为：28&68+2* (4)逆波兰式28&68+2*计算结果为192 备注：(1)在生成的逆波兰式中如果两个数相连则用&分隔，如28和68，中间用&分隔；(2)在此位置输入符号串为用户自行输入的符号串。 注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、数字，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）； 3.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以 分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照； 三.实验过程 1、逆波兰式定义 将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。采用逆波兰式可以很好的表示简单算术表达式，其优点在于易于计算机处理表达式。 2、产生逆波兰式的前提 中缀算术表达式 3、逆波兰式生成的实验设计思想及算法

编译原理(逆波兰表达式)C语言版

中国计量学院 《编译原理设计》 课程论文 题目：中缀表达式的逆波兰表示 学生姓名： 学号： 学生专业： 班级： 二级学院：

一、摘要 编译原理是计算机科学与技术专业最重要的一门专业基础课程，内容庞大，涉及面广，知识点多。由于该课程教、学难度都非常大，往往费了大量时间而达不到预期教学效果俗语说：学习的最好方法是实践。本课程设计正是基于此，力求为学生提供一个理论联系实际的机会，通过布置一定难度的课题，要求学生独立完成。我们这次课程设计的主要任务是编程实现对输入合法的中缀表达式进行词法分析、语法分析，构造相应的逆波兰式，计算后缀表达式的值输出结果。逆波兰式也叫后缀表达式，即将运算符写在操作数之后。通过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索前言知识的习惯，树立团队协作精神。同时，课程设计可以充分弥补课堂教学及普通实验中知识深度与广度有限的缺陷，更好地帮助学生从全局角度把握课程体系。 关键字：逆波兰式；语法分析；中缀表达式 二、实验综述 在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，所以，这种表示法也称为中缀表示。对中缀表达式的计值，并非按运算符出现的自然顺序来执行其中的各个运算，而是根据算符间的优先关系来确定运算的次序，此外，还应顾及括号规则。因此，要从中缀表达式直接产生目标代码一般比较麻烦。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。 三、实验意义 对于实现逆波兰式算法，难度并不大，但为什么要将看似简单的中缀表达式转换为逆波兰式，原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中缀表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行 四、系统分析 词法分析基本原理：词法分析程序完成的是编译第一阶段的工作。词法分析的作用是把符流的程序变为单词序列，输出在一个中间文件上，这个文件作为语法分析程序的输入而继续编译过程。 递归下降的原理由于时间和技术的限制，语法分析采用递归下降的方法。递归下降法是语法分析中最易懂的一种方法。它的主要原理是，对每个非终极符按其产生式结构构造相应语法分析子程序，其中终极符产生匹配命令，而非终极符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。 五、算法实现 将一个普通的中序表达式转换为逆波兰表达式的一般算法是：

将中缀表达式转换为后缀表达式-C++程序

5 将中缀表达式转换为后缀表达式 【问题描述】表达式转换。输入的中缀表达式为字符串，转换得到的后缀表达式存入字符数组中并输出。 例如：a*(x+y)/(b-x) 转换后得：a x y + * b x - / 【数据结构】 ●定义一个暂时存放运算符的转换工作栈opst。 ●中缀表达式字符串char *infix; ●后缀表达式字符串char *postfix; 【算法提示】转换规则：把运算符移到它的两个操作数后面，删除掉所有的括号。 从头到尾扫描中缀表达式，对不同类型的字符按不同情况处理： ●数字或小数点，直接写入字符串postfix，并在每个数值后面写入一个空格； ●左括号，进栈，直到遇见相配的右括号，才出栈； ●右括号，表明已扫描过括号内的中缀表达式，把从栈顶直到对应左括号之间的运算 符依次退栈，并把结果推入栈内； ●对于运算符，分两种情况处理： ◆该运算符的优先级大于栈顶符号的优先级，则入栈； ◆若该运算符的优先级小于栈顶优先级，则先弹出栈顶运算符、写入postfix串；继续将该 运算符与栈顶运算符比较，直到能把它推入栈内为止（即优先级大于栈顶运算符）。 说明：自行设计运算符优先级的表示。 【主要代码】 #include #include #include #include const int stackIncreament=0; class opst { public: opst(int sz=50) { maxSize=sz; top=-1; elements=new char[maxSize]; assert(elements!=NULL); } ~opst(){delete[]elements;} bool IsEmpty(){return (top==-1)?true:false;} bool IsFull(){return (top==maxSize-1)?true:false;} void Push( char &x); bool Pop(char &x); bool getTop(char &x); int getSize()const{return top+1;} void MakeEmpty(){top=-1;} void input(); void Convert(); friend ostream& operator<<(ostream &os,opst &s); private: char *elements; int top; int maxSize; void overflowProcess(); }; void opst::overflowProcess()//溢出处理{ char *newArray=new char[maxSize+stackIncreament]; for(int i=0;i<=top;i++) newArray[i]=elements[i]; maxSize=maxSize+stackIncreament; delete [] elements; elements=newArray; } void opst::Push(char &x) {

Java计算器实现(逆波兰式)

package hfw.util; import java.util.ArrayDeque; import java.util.Deque; /** * *逆波兰式 *总结，java版的Eval：逆波兰和动态编译，推荐用动态编译，因为逆波兰式不认识"- 4"，只认识"-4" *@author zyh */ public class RNP { /** * 运算数 */ private static Deque operationNum = new ArrayDeque(); /** * 运算符 */ private static Deque operator = new ArrayDeque(); /** * 将表达式转换为逆波兰式 * @param expression * @return */ private static void str2Rnp(String expression){ operationNum.clear(); operator.clear(); int index = 0; for(int i=0;i

逆波兰式

一、题目 ◆3.21③假设表达式由单字母变量和双目四则运 算算符构成。试写一个算法，将一个通常书写形式 且书写正确的表达式转换为逆波兰式。 实现下列函数： char *RPExpression(char *e); /* 返回表达式e的逆波兰式 */ Stack是一个已实现的栈。 可使用的相关类型和函数： typedef char SElemType; // 栈Stack的元素类型 Status InitStack(Stack &s); Status Push(Stack &s, SElemType e); Status Pop(Stack &s, SElemType &e); Status StackEmpty(Stack s); SElemType Top(Stack s); ------------------------------------------------------------------------------------------------- 二、思路

拿到题目，要做的第一件事情，就是搞懂题目究竟要我们做什么，很显然，题目中的关键字是“逆波兰式”，那么首先我们要搞懂这个概念。 所谓的逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。（摘自维基） 举个简单的例子，平常我们写的数学表达式a+b，就是一种中缀表达式，写成后缀表达式就是ab+。再举一个复杂的例子，中缀表达式(a+b)*c-(a+b)/e的逆波兰式是ab+c*ab+e/-。 在弄清楚概念以及题目的要求之后，接下来就要编写算法了。那么将一个表达式转换为逆波兰式的算法思想是什么呢？ (1)首先，需要分配2个栈，栈s1用于临时存储运算符（含一个结束符号），此运算符在栈内遵循越往栈顶优先级越高的原则；栈 s2用于输入逆波兰式，为方便起见，栈s1需先放入一个优先级最低的运算符，在这里假定为'#'； (2)从中缀式的左端开始逐个读取字符x，逐序进行如下步骤： 1.若x是操作数，则分析出完整的运算数（在这里为方便，用字母代替数字），将x直接压入栈s2；

中间代码生成具体实验过程含代码

实验三中间代码生成 学号：1152185；姓名：马小军 实验目的 1.了解并掌握中间代码的生成过程和作用 2.了解并掌握四元式 3.体会属性文法在中间代码生成过程中的作用 。 实验环境 Windows7操作系统vs2010编程环境 实验内容 从文件中读入表达式，输出其四元式的结果序列 本程序只能生成赋值语句及算数表达式中间代码的四元式不能生成逻辑表达式及其他复杂语句中间代码的四元式 实验原理 三、以逆波兰式为例的实验设计思想及算法 (1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。 (2)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符数字，则分析到该数字串的结束并将该数字存入数组。 (3)如果不是数字，该字符则是运算符，此时需比较优先关系。 做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。 (4)重复上述操作(2)-(3)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为四元式。 下面给出算法流程图

实验步骤 打开并运行软件 根据提示输入要分析的源程序（文件目录下有写好的文件源文件1.txt输入即可） 运行输出结果 例如将以下源文件放入test.txt 运行结果 a:=b*c+b*d 思考 同样的思路对算法进行适当改动就可以生成其它形式的中间代码 【其他部分】 设计原理和算法思想参考 《程序设计语言编译原理》第三版国防工业出版社作者陈火旺等

逆波兰式分析实验报告

实验报告 姓名：孙岩 学号：1408080211 班级：惠普开发142 学校：青岛科技大学Mail: 632928843@https://www.wendangku.net/doc/af9119380.html, 电话：178******** 教师：宮生文

实验报告： 实验名称：逆波兰式分析 实验目的和要求 将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。 实验内容和步骤： 一、实验内容 对于这个实验，总共用了三个函数，即主函数、算术表达式转换为后缀表达式函数、根据后缀表达式求取表达式的计算值。 主要完成的功能是接收一个包含加减乘除以及括号的算数表达式，进而将其转换为后缀表达式，从而通过此后缀表达式求出该算数表达式的值。 二、实验步骤 1、基于实验的内容，构造程序所需的模块 2、根据已建构的模块，写出各个模块的相应程序代码 3、在主函数中调用模块来完成所要得到的效果 在本程序中，首先定义了数组常量ex[max]，用于存储后缀表达式，操作对象在前，运算符在后；其次，是trans()函数，它的作用是将算数表达式转换为后缀表达式；其次是compvalue()函数，它的作用是根据后缀表达式求取对应算数表达式的算数值；最后是主函数模块，主要是通过对以上几个模块的调用。 实验代码如下： #include #include #include #define max 100 char ex[max]; /*存储后缀表达式*/ void trans(){ /*将算术表达式转化为后缀表达式*/ char str[max]; /*存储原算术表达式*/ char stack[max]; /*作为栈使用*/ char ch; int sum,i,j,t,top=0; printf("*****************************************\n"); printf("*输入一个求值的表达式，以#结束。*\n"); printf("******************************************\n"); printf("算数表达式："); i=0; /*获取用户输入的表达式*/ do{ i++; scanf("%c",&str[i]); }while(str[i]!='#' && i!=max);