逆波兰

学号：0740303104姓名：雷凤实验三逆波兰表达式的产生及计算一、实验目的非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。二、实验内容将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。三、逆波兰表达式的产生及计算实验设计思想及算法逆波兰式定义将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。产生逆波兰式的前提中缀算术表达式逆波兰式生成的设计思想及算法(1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。(2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。(3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。(4)如果不是数字，该字符则是运算符，此时需比较优先关系。做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。(5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。运用以上算法分析表达式(a+b*c)*d的过程如下：当前符号输入区符号栈输出区（a+b*c)*da+b*c)*d(+*c)*d(abc)*d(+a*)*d(+abc*d(+*ab)*d(+*abc)*d(+abc*)d(abc**abc*+d*abc*+*abc*+dabc*+d(1)构造一个栈，存放运算对象。(2)读入一个用逆波兰式表示的简单算术表达式。(3)自左至右扫描该简单算术表达式并判断该字符，如果该字符是运算对象，则将该字符入栈。若是运算符，如果此运算符是二目运算符，则将对栈顶部的两个运算对象进行该运算，将运算结果入栈，并且将执行该运算的两个运算对象从栈顶弹出。如果该字符是一目运算符，则对栈顶部的元素实施该运算，将该栈顶部的元素弹出，将运算结果入栈。(4)重复上述操作直至扫描完整个简单算术表达式的逆波兰式，确定所有字符都得到正确处理，我们便可以求出该简单算术表达式的值。逆波兰式计算的设计思想及算法四、实验要求1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。2、如果遇到错误的表达式，应输出错误提示信息。3、程序输入/输出实例：输入以#结束的中缀表达式(包括+-*/（）数字#)。例：(1)（a+b）(2)(a+b*c)(3)B+(-(A))*C输出逆波兰表达式的格式如下：(1)(a+b);→ab+)((2)(a+b*c)→abc*+)((3)B+(-A(A))*C→BA)(-)(C*+输入中缀表达式并计算结果：a*(b+c)+(-d)#；输出逆波兰式:abc+*d@+输入：a=3;b=1;c=2;d=5;计算结果为:4五、源程序代码//#includestdio.h#includeiostream.h#includestdlib.h#includemath.h#definemax100charex[max];/*存储后缀表达式*/voidtrans()/*将算术表达式转化为后缀表达式*/{charstr[max];/*存储原算术表达式*/charstack[max];/*作为栈使用*/charch;intsum,i,j,t,top=0;//cout*****************************************\n;cout*输入一个求值的表达式，以#结束。*\n;//cout******************************************\n;cout算数表达式：;i=0;/*获取用户输入的表达式*/do{i++;cinstr[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'/':while(stack[top]=='*'||stack[top]=='/'){ex[t]=stack[top];top--;t++;}top++;stack[top]=ch;break;case'':break;default:while(ch='0'&&ch='9')/*判定为数字*/{ex[t]=ch;t++;ch=str[i];i++;}i--;//数字串结束ex[t]='';t++;//让输出时有空格}ch=str[i];i++;}while(top!=0){ex[t]=stack[top];t++;top--;}ex[t]='#';//cout原来表达式：;//for(j=1;jsum;j++)//printf(%c,str[j]);//{coutstr[j];}//coutendl;//printf(\n\t后缀表达式：,ex);cout后缀表达式：;for(j=1;jt;j++){coutex[j];}coutendl;}voidcalculate(){/*计算后缀表达式的值*/floatstack[max],d;/*作为栈使用*/charch;intt=1,top=0;/*t为ex下标，top为stack下标*/ch=ex[t];t++;while(ch!='#'){switch(ch){case'+':stack[top-1]=stack[top-1]+stack[top];top--;break;case'-':stack[top-1]=stack[top-1]-stack[top];top--;break;case'*':stack[top-1]=stack[top-1]*stack[top];top--;break;case'/':if(stack[top]!=0){stack[top-1]=stack[top-1]/stack[top];}else{cout除零错误!endl;exit(0);/*异常退出*/}top--;break;default:d=0;while(ch='0'&&ch='9'){d=10*d+ch-'0';/*将数字字符转化为对应的数值*/ch=ex[t];t++;}top++;stack[top]=d;}ch=ex[t];t++;}cout计算结果:;coutstack[top]endl;}voidmain(){trans();calculate();}六、运行结果*输入一个求值的表达式，以#结束。*算数表达式：3-(6*4)+64-8/4#后缀表达式：364*-64+84/-计算结果:41Pressanykeytocontinue七、心得体会逆波兰的思想就是要把中缀表达式改写成后缀表达式，并计算出结果。在这中间也设置了一个先进后出的符号栈，根据相应符号的优先级控制运算符的出栈顺序，得出后缀表达式。思想不难，把程序的流程和栈的用法弄清楚，此程序就易写易读多了。