逆波兰式
35百科网 2020-07-28 00:00:00
逆波兰式(reverse polish notation,rpn,或逆波兰记法),也叫后缀表达式(将运算符写在操作数之后)
逆波兰式定义
一个表达式e的后缀形式可以如下定义:
(1)如果e是一个变量或常量,则e的后缀式是e本身。
(2)如果e是e1 op e2形式的表达式,这里op是如何二元操作符,则e的后缀式为e1#39;e2#39; op,这里e1#39;和e2#39;分别为e1和e2的后缀式。
(3)如果e是(e1)形式的表达式,则e1的后缀式就是e的后缀式。
如:我们平时写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/-
逆波兰式作用
实现逆波兰式的算法,难度并不大,但为什么要将看似简单的中序表达式转换为复杂的逆波兰式?原因就在于这个简单是相对人类的思维结构来说的,对计算机而言中序表达式是非常复杂的结构。相对的,逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构,它执行先进后出的顺序。
逆波兰式算法实现
将一个普通的中序表达式转换为逆波兰表达式的一般算法是:
首先需要分配2个栈,一个作为临时存储运算符的栈s1(含一个结束符号),一个作为输入逆波兰式的栈s2(空栈),s1栈可先放入优先级最低的运算符#,注意,中缀式应以此最低优先级的运算符结束。可指定其他字符,不一定非#不可。从中缀式的左端开始取字符,逐序进行如下步骤:
(1)若取出的字符是操作数,则分析出完整的运算数,该操作数直接送入s2栈
(2)若取出的字符是运算符,则将该运算符与s1栈栈顶元素比较,如果该运算符优先级大于s1栈栈顶运算符优先级,则将该运算符进s1栈,否则,将s1栈的栈顶运算符弹出,送入s2栈中,直至s1栈栈顶运算符低于(不包括等于)该运算符优先级,最后将该运算符送入s1栈。
(3)若取出的字符是“(”,则直接送入s1栈顶。
(4)若取出的字符是“)”,则将距离s1栈栈顶最近的“(”之间的运算符,逐个出栈,依次送入s2栈,此时抛弃“(”。
(5)重复上面的1~4步,直至处理完所有的输入字符
(6)若取出的字符是“#”,则将s1栈内所有运算符(不包括“#”),逐个出栈,依次送入s2栈。
完成以上步骤,s2栈便为逆波兰式输出结果。不过s2应做一下逆序处理。便可以按照逆波兰式的计算方法计算了!
逆波兰式计算方法
新建一个表达式,如果当前字符为变量或者为数字,则压栈,如果是运算符,则将栈顶两个元素弹出作相应运算,结果再入栈,最后当表达式扫描完后,栈里的就是结果。
逆波兰式举例
下面以(a+b)*c为例子进行说明:
(a+b)*c的逆波兰式为ab+c*,假设计算机把ab+c*按从左到右的顺序压入栈中,并且按照遇到运算符就把栈顶两个元素出栈,执行运算,得到的结果再入栈的原则来进行处理,那么ab+c*的执行结果如下:
1)a入栈(0位置)
2)b入栈(1位置)
3)遇到运算符“+”,将a和b出栈,执行a+b的操作,得到结果d=a+b,再将d入栈(0位置)
4)c入栈(1位置)
5)遇到运算符“*”,将d和c出栈,执行d*c的操作,得到结果e,再将e入栈(0位置)
经过以上运算,计算机就可以得到(a+b)*c的运算结果e了。
逆波兰式除了可以实现上述类型的运算,它还可以派生出许多新的算法,数据结构,这就需要灵活运用了。逆波兰式只是一种序列体现形式。
逆波兰式算法图示
其中△代表一个标识,ω代表预算法,名字q代表变量(如int a,b等),
算法用到三个栈:a栈,b栈,in栈。
其中a栈用来存储逆波兰式,b用来存储△号和运算符,in栈为输入栈。
第一竖排为b栈中符号,第一横排为输入栈中符号。
pop(in)为输入栈栈顶元素出栈,pop(a,q)为q入a栈,next算法即为进行下一轮循环,其中ω1lt;ω2为算符优先级,如“+”和“-”lt;“*”和“/”。pop(b,b),push(b,b)中b为临时变量,用来存储出栈的元素。stop为算法结束。
算法开始时,现将△如b栈,输入栈以#号结尾。
输入流
b[s-1]
名字q
(
ω2
)
#
△
pop(in);
push(a,q)
next
pop(in);
push(b,△)
next
pop(in)
push(b,ω2)
next
pop(in)
pop(b,b)next
stop
ω1
pop(in)
push(a,q)
next
pop(in)
push(b,△)
next
若ω1lt;ω2,则
pop(in)
push(b,ω2)
next
若ω1≥ω2,则pop(in)
pop(b,b),
push(a,b)
pop(b,b)
push(a,b)
pop(b,b)
push(a,b)
逆波兰式程序实现
逆波兰式c/c++语言版
//#includelt;iostreamgt; #includelt;stdlib.hgt; #includelt;stdio.hgt; #includelt;stackgt; #includelt;math.hgt; #includelt;string.hgt; #definemax100 usingnamespacestd; charex[max];/*存储后缀表达式*/ voidtrans() {/*将算术表达式转化为后缀表达式*/ charstr[max];/*存储原算术表达式*/ charstack[max];/*作为栈使用*/ charch; intsum,i,j,t,top=0; printf(*****************************************\n); printf(*输入一个求值的表达式,以#结束。*\n); printf(******************************************\n); printf(算数表达式:); i=0;/*获取用户输入的表达式*/ do{ i++; //cingt;gt;str[i];/*此步我用的是c++c语言的话在后面之所以用这个有一点区别都*/ scanf(%c,amp;str[i]); }while(str[i]!=#39;##39;amp;amp;i!=max); sum=i; t=1;i=1; ch=str[i];i++; // while(ch!=#39;##39;) { switch(ch) { case#39;(#39;:/*判定为左括号*/ top++;stack[top]=ch; break; case#39;)#39;:/*判定为右括号*/ while(stack[top]!=#39;(#39;) { ex[t]=stack[top];top--;t++; } top--; break; case#39;+#39;:/*判定为加减号*/ case#39;-#39;: while(top!=0amp;amp;stack[top]!=#39;(#39;) { ex[t]=stack[top]; top--; t++; } top++; stack[top]=ch; break; case#39;*#39;:/*判定为乘除号*/ case#39;/#39;: while(stack[top]==#39;*#39;||stack[top]==#39;/#39;) { ex[t]=stack[top]; top--; t++; } top++; stack[top]=ch; break; case#39;#39;:break; default: while(chgt;=#39;0#39;amp;amp;chlt;=#39;9#39;) {/*判定为数字*/ ex[t]=ch;t++; ch=str[i];i++; } i--; ex[t]=#39;#39;;t++; } ch=str[i];i++; } while(top!=0) { ex[t]=stack[top]; t++;top--; } ex[t]=#39;#39;; printf(\n\t原来表达式:); for(j=1;jlt;sum;j++) printf(%c,str[j]); printf(\n\t逆波兰式:,ex); for(j=1;jlt;t;j++) printf(%c,ex[j]); } voidcompvalue() {/*计算后缀表达式的值*/ floatstack[max],d;/*作为栈使用*/ charch; intt=1,top=0;/*t为ex下标,top为stack下标*/ ch=ex[t];t++; while(ch!=#39;#39;) { switch(ch) { case#39;+#39;: stack[top-1]=stack[top-1]+stack[top]; top--; break; case#39;-#39;: stack[top-1]=stack[top-1]-stack[top]; top--; break; case#39;*#39;: stack[top-1]=stack[top-1]*stack[top]; top--; break; case#39;/#39;: if(stack[top]!=0)stack[top-1]=stack[top-1]/stack[top]; else { printf(\n\t除零错误!\n); exit(0);/*异常退出*/ } top--; break; default: d=0; while(chgt;=#39;0#39;amp;amp;chlt;=#39;9#39;) { d=10*d+ch-#39;0#39;;/*将数字字符转化为对应的数值*/ ch=ex[t];t++; } top++; stack[top]=d; } ch=ex[t]; t++; } printf(\n\t计算结果:%g\n,stack[top]); } intmain() { trans(); compvalue(); system(pause); return0; }
逆波兰式数据结构版
int precede(char op)
{ int x;
switch(op)
{
case #39;*#39;: x=2; break;
case #39;/#39;: x=2; break;
case #39;+#39;: x=1; break;
case #39;-#39;: x=1; break;
default : x=0;
}
return x;
}
char *rpexpression(char *e)
{/* 返回表达式e的逆波兰式 */
char *c;
c=(char*)malloc(sizeof(char)*20); //不能用char c[]
stack s1;
initstack(s1);
int i=0,j=0;
char ch;
push(s1,#39;@#39;);
ch=e[i++];
while(ch!= 0)
{
if(ch==#39;(#39;)
{
push(s1,ch);
ch=e[i++];
}
else if(ch==#39;)#39;)
{
while(top(s1)!=#39;(#39;)
{
pop(s1,c[j++]);
}
/* to[j++]=pop(amp;s1);*/
pop(s1,ch);
ch=e[i++];
}
else if(ch==#39;+#39;||ch==#39;-#39;||ch==#39;*#39;||ch==#39;/#39;)
{
char w;
w=top(s1);
while(precede(w)gt;=precede(ch))
{
pop(s1,c[j++]);
w=top(s1);
}
push(s1,ch);
ch=e[i++];
}
else
{
//while((chlt;=#39;z#39;amp;amp;chgt;=#39;a#39;)||(chlt;=#39;z#39; amp;amp; chgt;=#39;a#39;)){
c[j++]=ch;
ch=e[i++];
//}
//c[j++]=#39; #39;;
}
}
pop(s1,ch);
while(ch!=#39;@#39;)
{
c[j++]=ch;
pop(s1,ch);
}
//c[j++]=;
c[j++]=0;
return c;
}
还有一种方法,用2叉树.
逆波兰式二叉树法
将最终进行的运算符记为根节点,将两边的表达式分别记为左右子树,依次进行直到所有的运算符与数字或字母标在一棵二叉树上。然后对二叉树进行后序遍历即可。
35百科网 原文地址:https://www.555baike.com/9999/2186.html
标签:波兰
分享:
热门推荐