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

1、学号1406410107成绩编译原理上机报告名称： 逆波兰式的产生及计算学院： 信息与控制工程学院专业： 计算机科学与技术班级： 计算机1401班姓名： 叶达成2016年 11月 4日一、上机目的通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。1、选择最有代表性的语法分析方法，如LL(1) 语法分析程序、算符优先分析程序和LR分析分析程序，并至少完成两个题目。2、选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。 实验前的准备按实验的目的和要求，编写语

2、法分析程序，同时考虑相应的数据结构。 调试调试例子应包括符合语法规则的算术表达式，以及分析程序能够判别的若干错例。 输出对于所输入的算术表达式，不论对错，都应有明确的信息告诉外界。 扩充有余力的同学，可适当扩大分析对象。譬如： 算术表达式中变量名可以是一般标识符，还可含一般常数、数组元素、函数调用等等。 除算术表达式外，还可扩充分析布尔、字符、位等不同类型的各种表达式。加强语法检查，尽量多和确切地指出各种错误。二、基本原理和上机步骤基本原理：将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。采用逆波兰式

3、可以很好的表示简单算术表达式，其优点在于易于计算机处理表达式。上机步骤：(1)构造一个栈，存放运算对象。(2)读入一个用逆波兰式表示的简单算术表达式。(3)自左至右扫描该简单算术表达式并判断该字符，如果该字符是运算对象，则将该字符入栈。若是运算符，如果此运算符是二目运算符，则将对栈顶部的两个运算对象进行该运算，将运算结果入栈，并且将执行该运算的两个运算对象从栈顶弹出。如果该字符是一目运算符，则对栈顶部的元素实施该运算，将该栈顶部的元素弹出，将运算结果入栈。(4)重复上述操作直至扫描完整个简单算术表达式的逆波兰式，确定所有字符都得到正确处理，我们便可以求出该简单算术表达式的值。三、上机结果程序清

4、单：#include<iostream>#include<stdio.h>#include<stdlib.h>#include<algorithm>#include<cctype>#include<cstring>using namespace std;char str50;/用于存放原来的表达式int top;/栈顶指针char stack50;/定义栈，用于计算逆波兰式char ex50;/存放后缀表达式double _stack50;/定义栈，用于计算逆波兰式子int flag50;/用于区分+、-号的含义，0表示运

5、算符，1表示正负号/生成逆波兰式void NiBolan() memset(flag,0,sizeof(flag); /flag初始值设为0 char ch=str0; int i=1,t=0; top=0; while(ch!='#') switch(ch) case '(': top+; stacktop=ch; break; case ')': while(stacktop!='(') ext=stacktop; top-; t+; top-; break; case '': while(stacktop=&

6、#39;') /设置运算符优先级为最高 ext=stacktop; top-; t+; top+; stacktop=ch; break; case '+': case '-':/当ch为+、-号是，若前面相邻字符不是')'或数字且后面相邻字符是数字时表示正负号 if(isdigit(stri) && !isdigit(stri-2) && stri-2!=')') flagt=1;/标记符号为正负号 ext+=ch; ch=stri+; while(ch>='0'&a

7、mp;&ch<='9')|(ch>='a'&&ch<='z')|ch='.'|ch='+') /判别小数点 ext=ch; t+; ch=stri; i+; i-; ext='&' t+; else while(top!=0&&stacktop!='(') ext=stacktop; top-; t+; top+; stacktop=ch; break; case '*': case '/

8、9;: while(stacktop='*'|stacktop='/'|stacktop='') /运算符优先级高于*和/ ext=stacktop; top-; t+; top+; stacktop=ch; break; case ' ': break; default: while(ch>='0'&&ch<='9')|(ch>='a'&&ch<='z')|ch='.')/判别小数点 ext=c

9、h; t+; ch=stri; i+; i-; ext='&' t+; ch=stri;i+; while(top!=0) if(stacktop!='(') ext=stacktop; t+; top-; else printf("error"); top-; exit(0); ext='#' ext+1='0' printf("逆波兰式为：%sn",ex);void Calculate() char ch=ex0; int t=0; top=-1; while(ch!='

10、#') if(ch='&') ch=ex+t; continue; switch(ch) case '+': if(flagt)/'+'表示正号 ch=ex+t; double d=0; while(ch>='0'&&ch<='9') d=10.0*d+double(ch-'0'); ch=ex+t; if(ch='.')/判断是否为小数 ch=ex+t; double k=1.0; while(ch>='0'&

11、;&ch<='9') d=d+double(ch-'0')/(10.0*k); k=k+1.0; ch=ex+t; top+; _stacktop=d; else _stacktop-1=_stacktop-1+_stacktop; top-; t+; break; case '-': if(flagt)/'-'表示负号 ch=ex+t; double d=0; while(ch>='0'&&ch<='9') d=10.0*d+double(ch-'

12、0'); ch=ex+t; if(ch='.') ch=ex+t; double k=1.0; while(ch>='0'&&ch<='9') d=d+double(ch-'0')/(10.0*k); k=k+1.0; ch=ex+t; top+; _stacktop=-d; else _stacktop-1=_stacktop-1-_stacktop; top-; t+; break; case '':/运算符为'' if(_stacktop=0) _stack

13、top-1=1; else int temp; temp=_stacktop-1; while(-_stacktop) _stacktop-1*=temp; top-; t+; break; case '*': _stacktop-1=_stacktop-1*_stacktop; top-; t+; break; case '/': if(_stacktop!=0) _stacktop-1=_stacktop-1/_stacktop; else printf("ntchu0error!n"); exit(0); top-; t+; break

14、; default: double d=0; while(ch>='0'&&ch<='9') d=10.0*d+double(ch-'0'); ch=ex+t; if(ch='.')/判断是否为小数 ch=ex+t; double k=1.0; while(ch>='0'&&ch<='9') d=d+double(ch-'0')/(10.0*k); k=k+1.0; ch=ex+t; top+; _stacktop=d; ch=ext; cout<<"计算结果："<<_stacktop<<endl;/printf("计算结果：%lfn",_stacktop);int main() printf("请输入中缀表达式："); scanf("%s",&str);/输入原表达式 printf("原表达式为：%sn",