当前位置：文档之家 › 对逆波兰式计算的程序设计

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

  • 格式：doc
  • 大小：40.50 KB
  • 文档页数：10

数据结构作业报告逆波兰式的计算一题目内容逆波兰式也叫后缀表达式(将运算符写在操作数之后)如：我们平时写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);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return OK;}//将栈顶元素输出到元素e之中Status Pop(SqStack &S,SElemType e) {if(S.top==S.base)return ERROR;e=*--S.top;return OK;}//将元素e加入到栈之中程序最重要的操作函数如下（进行计算操作）：char CalVal_InverPoland(char Buffer[]){Stack Opnd;InitStack(Opnd);int i=0;char c;ElemType e1,e2;while(Buffer[i]!='#'){if(!IsOperator(Buffer[i])){Push(Opnd,Buffer[i]);}else{Pop(Opnd,e2);Pop(Opnd,e1);c=Cal(e1,Buffer[i],e2);Push(Opnd,c);}i++;}return c;}while循环中是对表达式各字符的判断和计算过程，如果是数字则加入栈中，是操作符则从栈中提取两数据进行计算，之后将计算结果加入到栈中，直至遇到表达式结束标志’#’则结束运算，栈中数字则为计算结果。

Status IsOpertor(char c){char *p="#+-*/";while(*p){if(*p==c)return TRUE;p++;}return FALSE;}//数字操作符判断函数char Cal(char c1,char op,char c2) {int x,x1,x2;char ch[10];ch[0]=c1;ch[1]='\0';x1=atoi(ch);ch[0]=c2;ch[1]='\0';x2=atoi(ch);switch(op){case '+':x=x1+x2;break;case '-':x=x1-x2;break;case '*':x=x1*x2;break;case '/':x=x1/x2;break;default:break;}itoa(x,ch,10);return ch[0];}//计算函数如计算‘1+6-4’，则逆波兰式式为‘16+4-’，输入‘16+4-#’，计算结果应为3，运行结果如下四源代码#include <iostream.h>#include <stdlib.h>#include <string.h>#include <malloc.h>#define SElemType char#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status;#define OVERFLOW -1#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef struct{SElemType *base;SElemType *top;int stacksize;}SqStack;Status InitStack(SqStack &S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));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*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType ));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return OK;}Status Pop(SqStack &S,SElemType &e) {if(S.top==S.base)return ERROR;e=*--S.top;return OK;}Status IsOperator(char c){char *p="#+-*/";while(*p){if(*p==c)return TRUE;p++;}return FALSE;}char Cal(char c1,char op,char c2){int x,x1,x2;char ch[10];ch[0]=c1;ch[1]='\0';x1=atoi(ch);ch[0]=c2;ch[1]='\0';x2=atoi(ch);switch(op){case '+':x=x1+x2;break;case '-':x=x1-x2;break;case '*':x=x1*x2;break;case '/':x=x1/x2;break;default:break;}itoa(x,ch,10);return ch[0];}char CalVal_InverPoland(char Buffer[]){SqStack Opnd;InitStack(Opnd);int i=0;char c;SElemType e1,e2;while(Buffer[i]!='#'){if(!IsOperator(Buffer[i])){Push(Opnd,Buffer[i]);}else{Pop(Opnd,e2);Pop(Opnd,e1);c=Cal(e1,Buffer[i],e2);Push(Opnd,c);}i++;}return c;}int main(){char a[30],c;cout<<"请输入逆波兰算术表达式字符序列：";cin>>a;c=CalVal_InverPoland(a);cout<<"计算结果是"<<c;return 0;}。

合集下载

Java实现《编译原理》中间代码生成-逆波兰式生成与计算-程序解析

Java实现《编译原理》中间代码生成-逆波兰式生成与计算-程序解析

Java实现《编译原理》中间代码⽣成-逆波兰式⽣成与计算-程序解析Java 实现《编译原理》中间代码⽣成 -逆波兰式⽣成与计算 - 程序解析编译原理学习笔记（⼀）逆波兰式是什么？逆波兰式（Reverse Polish notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）⼀般的表达式⼜称中缀表达式，这种表达式的⼆元运算符放在两个运算量之间。

⽽逆波兰表达式⼜称后缀表达式，这种表达式把运算符放在运算量后⾯。

⽐如如 a+b 的逆波兰式表⽰为 ab+注意：逆波兰式是⼀个⽆括号表达式；逆波兰式的运算符出现的顺序就是原表达式的运算顺序。

（⼆）逆波兰式编译原理有什么关系？逆波兰式，三元式，四元式等是编译原理 - 中间代码⽣成阶段的常见的中间代码形式。

（三）本篇任务通过设计，使⽤ Java 语⾔编写⼀个逆波兰式⽣成程序，测试效果：（四）Java 源代码package com.java997.analyzer.rpn;import java.util.HashMap;import java.util.Map;import java.util.Scanner;import java.util.Stack;/*** <p>* 逆波兰式** @author XiaoPengwei* @since 2019-06-19*/public class RpnMain {/*** 检查算术表达术括号是否匹配, 语法是否正确** @param s 算术表达术* @return boolean*/public boolean isMatch(String s) {//括号符号栈Stack<Character> charStack = new Stack<>();//将表达式的字符串转换成数组char[] charArray = s.toCharArray();//遍历数组for (char aChar : charArray) {if (aChar == '(') {charStack.push(aChar);} else if (aChar == ')') {//如果是 ) , 且栈为空则返回 falseif (charStack.isEmpty()) {return false;} else {//如果是 ) , 且栈不为空则返回 false//peek() 是返回栈顶的值, 不做其他操作if (charStack.peek() == '(') {//把栈顶的值删除charStack.pop();}}}}//⾛到这⾥, 栈为空则表达式正确return charStack.empty();}/*** 判断是否为操作符 + - * /** @param charAt* @return boolean*/public boolean isOperator(char charAt) {return charAt == '+' || charAt == '-' || charAt == '*' || charAt == '/'; }/*** 根据正确的表达式, 获取逆波兰式** @param input* @return ng.String*/public StringBuilder getRpn(String input) {//结果StringBuilder sb = new StringBuilder();sb.append("The RPN is: ");//运算符栈Stack<Character> opStack = new Stack();//运算符优先级Map<Character, Integer> opMap = new HashMap(5);opMap.put('(', 0);opMap.put('+', 1);opMap.put('-', 1);opMap.put('*', 2);opMap.put('/', 2);//处理字符串for (int i = 0; i < input.length(); i++) {//如果是'('直接压栈if (input.charAt(i) == '(') {opStack.push('(');} else if (new RpnMain().isOperator(input.charAt(i))) {//如果是运算符char curOp = input.charAt(i);//如果运算符栈是空，就直接压栈if (opStack.isEmpty()) {opStack.push(curOp);} else if (opMap.get(curOp) > opMap.get(opStack.peek())) {//运算符栈不为空，且当当前运算符的优先级⽐站内第⼀个运算符的优先级⾼的时候，压栈 opStack.push(curOp);} else {//栈不为空，且运算符的优先级⼩于等于栈顶元素for (int j = 0; j <= opStack.size(); j++) {//弹出栈内第⼀个元素char ch = opStack.pop();sb.append(ch);if (opStack.isEmpty()) {opStack.push(curOp);break;} else if (opMap.get(curOp) > opMap.get(opStack.peek())) {opStack.push(curOp);break;}}}} else if (input.charAt(i) == ')') {//如果是')'就把站内'('上的元素都弹出栈for (int j = 0; j < opStack.size(); j++) {char c = opStack.pop();if (c == '(') {break;} else {sb.append(c);}}} else if ('A'<=input.charAt(i)&&input.charAt(i)<='Z'){//如果是字母就直接添加sb.append(input.charAt(i));}else if ('a'<=input.charAt(i)&&input.charAt(i)<='z'){//如果是字母就直接添加sb.append(input.charAt(i));}else if (Character.isDigit(input.charAt(i))){//如果是数字sb.append(input.charAt(i));}else {return new StringBuilder("But the expression contains unrecognizable characters");}}//把栈内剩余的运算符都弹出站for (int i = 0; i <= opStack.size(); i++) {sb.append(opStack.pop());}return sb;}public static void main(String[] args) {RpnMain rpnMain = new RpnMain();Scanner sc = new Scanner(System.in);while (true) {System.out.println("==========================\nPlease input an expression:");String input = sc.nextLine();if ("q".equals(input)) {sc.close();return;} else {if (rpnMain.isMatch(input)) {System.out.println("The expression's brackets are matched");// 获取逆波兰式System.out.println(rpnMain.getRpn(input));} else {System.out.println("Error: The expression's brackets are not matched! Enter 'q' to exit");}}}}}测试：。

实验三 逆波兰表达式的产生及计算

实验三 逆波兰表达式的产生及计算

实验三逆波兰表达式的产生及计算一、实验目的非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。

二、实验内容将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。

三、逆波兰表达式的产生及计算实验设计思想及算法◆逆波兰式定义将运算对象写在前面，而把运算符号写在后面。

用这种表示法表示的表达式也称做后缀式。

逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。

◆产生逆波兰式的前提中缀算术表达式◆逆波兰式生成的设计思想及算法(1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。

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

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

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

做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。

如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。

倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。

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

运用以上算法分析表达式(a+b*c)*d的过程如下：当前符号输入区符号栈输出区（ a+b*c)*da +b*c)*d (+ *c)*d ( ab c)*d (+ a* )*d (+ abc *d (+* ab) *d (+* abc) *d (+ abc*) d ( abc** abc*+d * abc*+* abc*+dabc*+d(1)构造一个栈，存放运算对象。

(2)读入一个用逆波兰式表示的简单算术表达式。

逆波兰式（后缀表达式）的计算

逆波兰式（后缀表达式）的计算

逆波兰式（后缀表达式）的计算输⼊：后缀表达式（可带浮点数）输出：double型的计算结果代码：#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define ElemType double#define Stack_Init_Size 100#define Increase_Size 10#define MaxBuffer 10typedef struct sqStack{ElemType *top;ElemType *base;int initSize;}sqStack;typedef struct sqStack *LinkStack;//初始化void InitStack( sqStack *s ){s->base = (LinkStack)malloc(Stack_Init_Size * sizeof(ElemType));if(!s->base){printf("存储空间分配失败······\n");return;}s->top = s->base;s->initSize = Stack_Init_Size;}//进栈void Push(sqStack *s,ElemType e){if(s->top - s->base >= s->initSize - 1){s->base = (LinkStack)realloc(s->base,(s->initSize + Increase_Size) * sizeof(ElemType));//第⼀个s->base是增加后的存储空间块的地址，第⼆个是增加空间之前的存储空间块地址，后⾯是增加过的存储空间块的⼤⼩ if(!s->base){printf("增加存储空间失败······\n");return;}s->initSize = Increase_Size + Stack_Init_Size;}*(s->top) = e;(s->top)++;}//出栈void Pop(sqStack *s,ElemType *e){if(s->top == s->base){printf("栈已空，⽆法进⾏出栈操作······\n");return;}s->top--;*e = *s->top;}//求栈的长度int StackLen(sqStack s){return (s.top - s.base);}//逆波兰计算器：输⼊逆波兰式（后缀表达式）输出结果int main(){int i = 0,j,len;double m,n,t;char c;struct sqStack s;char str[MaxBuffer];InitStack(&s);printf("请输⼊您要计算的后缀表达式，按Enter键结束（两个不同的字符之间⽤空格隔开）：\n");scanf("%c",&c);while(c != '\n'){while( (c >= '0'&&c <= '9') || c == '.'){str[i] = c;i++;// str[i] = '\0';if(i >= 10){printf("\n输⼊的数字过⼤导致出错\n"); return -1;}scanf("%c",&c);if( c == ' '){t = atof(str);// printf("\nt is %f\n",t);Push(&s,t);i = 0;for(j = 0;j < MaxBuffer;j++){str[j] = '\0';}break;}}switch( c ){case '+':Pop(&s,&m);Pop(&s,&n);Push(&s,n+m);break;case '-':Pop(&s,&m);Pop(&s,&n);Push(&s,n-m);break;case '*':Pop(&s,&m);Pop(&s,&n);Push(&s,n*m);break;case '/':Pop(&s,&m);Pop(&s,&n);if( m == 0){printf("\n除数为0，出错\n");return -1;}else{Push(&s,n/m);break;}}scanf("%c",&c);}Pop(&s,&t);printf("\n最终的计算结果为：%f \n",t);return 0;}。

编译原理实验报告6逆波兰式的翻译和计算

编译原理实验报告6逆波兰式的翻译和计算

实验6 逆波兰式的翻译和计算一、实验目的通过实验加深对语法指导翻译原理的理解，掌握算符优先分析的方法，将语法分析所识别的表达式变换成中间代码的翻译方法。

二、实验内容设计一个表示能把普通表达式（中缀式）翻译成后缀式，并计算出结果的程序。

三、实验要求1、给出文法如下：G[E]E->T|E+T;T->F|T*F;F->i(E);对应的转化为逆波兰式的语义动作如下： E-> E (1)op E (2) {E.CODE:= E (1).CODE||E (2).CODE||op} E->(E (1)) { E.CODE := E (1).CODE}E->id { E.CODE := id}2、利用实验5中的算符优先分析算法，结合上面给出的语义动作实现逆波兰式的构造；3、利用栈，计算生成的逆波兰式，步骤如下：1） 中缀表达式，从文本文件读入，每一行存放一个表达式，为了降低难度，表达式采用常数表达式；2） 利用结合语法制导翻译的算符优先分析，构造逆波兰式；3） 利用栈计算出后缀式的结果，并输出；四、实验环境PC 微机DOS 操作系统或 Windows 操作系统Turbo C 程序集成环境或 Visual C++ 程序集成环境五、实验步骤1、了解语法制导翻译的方法，学习后缀式构造的语义动作；2、结合实验5的算符优先程序，设计程序构造后缀式；3、利用栈，编程实现后缀式的计算；4、测试程序运行效果：从文本文件中读表达式，在屏幕上输出，检查输出结果。

六、测试数据输入数据：编辑一个文本文文件expression.txt，在文件中输入如下内容：正确结果：（1）1+2;输出：1,2,+ 3（2）(1+2)*3;输出：1,2,+,3,* 9（3）(10+20)*30+(50+60*70)输出：10,20,+30,*50,60,70,*,+,+ 5150七、实验报告要求实验报告应包括以下几个部分：1、构造逆波兰式的语义动作；2、结合算符优先分析构造逆波兰式的算法和过程；3、语法制导翻译的运行方法；4、程序的测试结果和问题；5、实验总结。