算术表达式转换为用逆波兰式来表示的算术表达式

算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。1)实验内容：算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。备注：在表达式数字仅有一位2)、实验原理(1))逆波兰式定义将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。采用逆波兰式可以很好的表示简单算术表达式，其优点在于易于计算机处理表达式。(2))产生逆波兰式的前提通过翻译产生逆波兰式,逆波兰式放入num[]中S→E{}E→E1+T{num[t++]=’+’}E→T{}T→T1*F{num[t++]=’*’}T→F{}F→(E){}F→digit{num[t++]=digit.val}3)、实验过程(1)：利用语法分析过程构造逆波兰式(2)：逆波兰式求值(a)构造一个栈，存放运算对象。(b)读入一个用逆波兰式表示的简单算术表达式。(c)自左至右扫描该简单算术表达式并判断该字符，如果该字符是运算对象，则将该字符入栈。若是运算符，如果此运算符是二目运算符，则将对栈顶部的两个运算对象进行该运算，将运算结果入栈，并且将执行该运算的两个运算对象从栈顶弹出。如果该字符是一目运算符，则对栈顶部的元素实施该运算，将该栈顶部的元素弹出，将运算结果入栈。(d)重复上述操作直至扫描完整个简单算术表达式的逆波兰式，确定所有字符都得到正确处理，我们便可以求出该简单算术表达式的值.参考程序：#includestdio.h#includestring.hchar*action[12][6]={S5#,NULL,NULL,S4#,NULL,NULL,/*ACTION表*/NULL,S6#,NULL,NULL,NULL,acc,NULL,r2#,S7#,NULL,r2#,r2#,NULL,r4#,r4#,NULL,r4#,r4#,S5#,NULL,NULL,S4#,NULL,NULL,NULL,r6#,r6#,NULL,r6#,r6#,S5#,NULL,NULL,S4#,NULL,NULL,S5#,NULL,NULL,S4#,NULL,NULL,NULL,S6#,NULL,NULL,S11#,NULL,NULL,r1#,S7#,NULL,r1#,r1#,NULL,r3#,r3#,NULL,r3#,r3#,NULL,r5#,r5#,NULL,r5#,r5#};intgoto1[12][3]={1,2,3,/*GOTO表*/0,0,0,0,0,0,0,0,0,8,2,3,0,0,0,0,9,3,0,0,10,0,0,0,0,0,0,0,0,0,0,0,0};charvt[6]={'i','+','*','(',')','#'};/*存放终结符*/charvn[3]={'E','T','F'};/*存放非终结符*/char*LR[7]={S-E#,E-E+T#,E-T#,T-T*F#,T-F#,F-(E)#,F-i#};/*存放产生式*/inta[10];charb[10],c[10],d[10],c1;inttop1,top2,top3,top,m,n,t;intjudge(){intg,h,i,j,k,l,p,y,z,count;charx,copy[10],copy1[10];top1=0;top2=0;top=0;a[0]=0;y=a[0];b[0]='#';count=0;z=0;t=0;printf(步骤\t状态栈\t\t符号栈\t\t输入串\t\tACTION\tGOTO\n);do{y=z;/*y,z指向状态栈栈顶*/g=top;k=0;x=c[top];count++;printf(%d\t,count);m=0;while(m=top1){/*输出状态栈*/printf(%d,a[m]);m=m+1;}printf(\t\t);n=0;while(n=top2){/*输出符号栈*/printf(%c,b[n]);n=n+1;}printf(\t\t);while(g=top3){/*输出输入串*/printf(%c,c[g]);g=g+1;}printf(\t\t);if(x='0'&&x='9')j=0;else{j=1;while(j6&&x!=vt[j])j++;if(j=6){printf(error\n);return0;}}if(action[y][j]==NULL){printf(error\n);return0;}strcpy(copy,action[y][j]);if(copy[0]=='a')return1;if(copy[0]=='S'){/*处理移进*/z=copy[1]-'0';if(copy[2]!='#')z=z*10+copy[2]-'0';top1=top1+1;top2=top2+1;a[top1]=z;b[top2]=x;top=top+1;i=0;while(copy[i]!='#'){printf(%c,copy[i]);i++;}printf(\n);}if(copy[0]=='r'){/*处理归约*/i=0;while(copy[i]!='#'){printf(%c,copy[i]);i++;}h=copy[1]-'0';strcpy(copy1,LR[h]);while(copy1[0]!=vn[k])k++;l=strlen(LR[h])-4;top1=top1-l+1;top2=top2-l+1;y=a[top1-1];p=goto1[y][k];a[top1]=p;b[top2]=copy1[0];z=p;printf(\t);printf(%d\n,p);switch(h){case1:d[t++]='+';break;case2:break;case3:d[t++]='*';break;case4:break;case5:break;case6:d[t++]=c[top-1];}}}while(1);}intcompvalue(){/*计算后缀表达式的值*/intstack[10];/*作为栈使用*/ints=0,top=0;/*t为ex下标，top为stack下标*/while(d[s]!='#'){switch(d[s]){case'+':stack[top-2]=stack[top-2]+stack[top-1];top--;break;case'*':stack[top-2]=stack[top-2]*stack[top-1];top--;break;default:stack[top++]=d[s]-'0';}s++;}return(stack[top-1]);}voidmain(){inti;top3=0;printf(请输入表达式\n);do{scanf(%c,&c1);c[top3]=c1;top3=top3+1;}while(c1!='#');i=judge();if(i==1)printf(acc\n);d[t++]='#';for(i=0;it;i++)printf(%c,d[i]);printf(\n%d\n,compvalue());}