逆波兰式的转化与求值 栈与队列 实验报告.doc

逆波兰式实验报告实验题目：逆波兰式的转化与求值实验目的：了解并运用栈与队列在程序中将非逆波兰式表示的算术表达式转 换为用逆波兰式表示，并计算用逆波兰式来表示的算术表达式的值验证刚学的 栈和队列的理论，巩固知识并加深理解实验内容：一、抽象数学模型：逆波兰式转化程序流程：逆波兰式求值程序流程:读入一个逆波兰算术达式 Ch-当前输入符号将该字符入栈根据运算符的特点从栈顶部 结束取出若干个对象进行该运 一—算，将运算结果入栈二、详细算法描述：逆波兰式计算：//先初始化一个栈S，并将左括号’（'压栈//从左至右对表达式进行扫描，依次存入字符串si中//若遇到数字则存入字符串s2中//若遇到右括号则将栈s中的元素弹出放入s2中直到遇到左括号’（‘，并将左括号 出栈//若遇到左括号则直接进栈//若遇到运算符则需比较其与栈顶元素优先级顺序，若大于则直接入栈，否则弹 出栈顶元素存入s2中直到运算符的优先级//低于栈顶元素并将其压栈//当遇到'#'时表明表达式以全部输入，此时将栈s中元素弹出并放入s2中，直至 遇到左括号'）’//将'# '放入s2作为表达式结束标志，表达式转换为逆波兰式（后缀表达式）后缀表达式求值算法描述//先初始化一个栈s//从左至右对s2进行扫描//若遇到数字字符则压入栈s//若遇到运算符则将栈s中元素依次弹出两个进行运算，将运算结果压栈//当遇到'#'时表达式结束，此时弹出栈顶元素即为表达式的值三、程序清单：（见附录）四、运行结果（截图）:运行结果分析：将运算对象写在前面，而把运算符号写在后面。

程序采用逆波兰 式可以很好的表示简单算术表达式，易于计算机处理表达式由 运行结果可知，可以正确地把算术表达式转化为后缀表达式且能 够正确计算出表达式的值五、调试分析和体会：（一） 、实验程序编写过程中运用了栈的相关知识，通过栈实现逆波兰式的转化和计算二） 、利用栈，巧妙地把表达式转化为后缀表达式从而大大简化翻译过程，同时在对后缀表达式进行计算时也方便了计算这是由于栈的先入后出性，与表达式数字与运算 符的先后关系相符，所以得到了很好的应用三） 、在判断优先级时，将定性判断转化为定量判断，易于计算机的识别计算缺陷：此算法中并不包括浮点型数据此算法只解决简单表达式求值问题，并不包括超越表达式的求值 此算法可以将中缀表达式转换为后缀表达式并求值，而没有转换成前缀表达式 此算法中表达式长度有限，不能超过N附录：#include#in clude#in clude#include#define STACKSIZE 100#define STACKINCREMENT 10#defi ne N 100typedef struct{int * top;int * base;int stacksize;}Sqstack;//构造—空栈void InitSt ack(Sqs tack * s){s->base=(i nt *)malloc(STACKSIZE*sizeof(i nt));if(!s->base)exi t(1);s->top=s->base;s->stacksize二STACKSIZE;}//将元素e压栈void Push(Sqs tack * s,int e){if(s->to p-s->base>=s->s tacksize){s->base=(int*)realloc(s->base,(STACKSIZE+STACKINCREMENT)*sizeof(i nt));if(!s->base)exi t(1);s->top=s->base+s->stacksize;s->stacksize二s->stacksize+STACKINCREMENT;}*s->top=e;s->top++;}//取出栈顶元素int Getto p(Sqs tack * s){int e;if(s->to p==s->base)exi t(1);e=*(s->to p-1);return( e);}〃删除栈顶元素并返回其值int Pop(Sqstack *s ){int e;if(s->to p==s->base)exi t(1);e=*(一s->to p);return( e);}//量化运算符的优先级int priori ty(int etop,int es1){int i; int a[2],b[2];a[0]=e top;a[1]=es1; for(i=0;i<2;i++) swi tch(a [i]){ case '(':b[i]=0;break;case ' +':case ' -':b[i]=1;break;case '*':case'/':b[i]=2;break;case '":b[i]=3;}if(b[0]-b[1]>=0)return 1;elsereturn 0;}//将中缀表达式转换为后缀表达式void TranslatExpression( char * s1){char s2[N];Sqs tack s; int i=0,j=0; int m;InitSt ack(&s); Push(&s,'('); while(s1[i]!二’#'){if(s1[i]>='0' &&s1[i]<='9'){ s2[j++]=s1[i]; if(s1[i+1]<'0'||s1[i+1]>'9') s2[j++]='';}elseswi tch(s1[i]){ case'(':Push(&s,s1[i]);break; case')':m=Ge ttop(&s); while(m!='('){m=Pop(&s);s2[j++]=m;m二Ge ttop(&s);}m=Pop(&s);break;default:m二Gettop(&s);while(priori ty( m,s1[i])){ m=Pop(&s);s2[j++]二m; m=Ge ttop(&s);}Push(&s,s1[i]);}i++；}m=Ge tt op(&s);while(m!='('){m=Pop(&s);s2[j++]=m; m=Ge ttop(&s);}s2[j]二pri nt f("逆波兰式为：\n"); for(i=0;s2[i]!='#';i++){s1[i]=s2[i];put char(s2[i]);}pri nt f("%c\n",'#');s1[i]二}//计算表达式的值int CalculatExpression(char * s1){int m,x,y,z,i=0; Sqs tack s;InitSt ack(&s);while(s1[i]!='#'){if(s1[i]>='0' &&s1[i]<='9'){m=0;while(s1[i] !=' '){ m=m*10+(s1[ i] 一'0'); i++;}Push(&s,m); i++;}else{y=Pop(&s); x=Pop(&s);swi tch(s1[i]){case '+':z=x+y;break;case '-':z=x-y;break;case ' *':z=x*y;break; case '/':z=x/y;break;defauIt:z=1;for(m=0;m