逆波兰式

   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

标签:波兰



分享:

  • 微信
  • QQ好友
  • QQ空间
  • 新浪微博


热门推荐

GlassFish

glassfish 是一款强健的商业兼容应用服务器,达到产品级质量,可免费用于开发、部署和重新分发。 ...

青藏铁路

青藏铁路东起青海西宁,南至西藏拉萨,全长1956千米,被誉为“天路”,是实施西部大开发战略的标志性工程, ...

水浒传(中国古典长篇小说,四大名著之一)

《水浒传》,是中国四大名著之一,全书描写北宋末年以宋江为首的108位好汉在梁山起义,以及聚义之后接受招安 ...

平遥古城(历史文化古城、世界文化遗产、5A风景区)

平遥古城位于山西省中部平遥县内,始建于西周宣王时期(公元前827年~公元前782年)。平遥古城是中国汉民 ...

李牧(战国时期赵国名将)

李牧(?-公元前229年),嬴姓,李氏,名牧,柏仁(今河北隆尧)人,战国时期的赵国军事家,与白起、王翦、 ...

唐古拉山脉

唐古拉山脉(tanggula mountains,t#39;ang-ku-la shan或tanggul ...

营业

营业,指营谋生计;职业;工作;商业、服务业、交通运输业等经营业务。语出《三国志·吴志·骆统传》:“百姓 ...

重阳节

重阳节,又称重九节、晒秋节、“踏秋”,汉族传统节日。庆祝重阳节一般会包括出游赏秋、登高远眺、观赏菊花、遍 ...

红楼梦(中国古典长篇小说四大名著之一)

《红楼梦》,中国古典四大名著之首,清代作家曹雪芹创作的章回体长篇小说[1] ,又名《石头记》《金玉缘》。 ...

女真族

同义词 女真一般指女真族 女真族,别称女贞与女直,源自3000多年前的肃慎,[1] 汉至晋时期称挹娄 ...

岫岩满族自治县

同义词 岫岩一般指岫岩满族自治县 岫岩满族自治县隶属于辽宁省鞍山市,位于辽东半岛的北部。[1] 东及 ...

中秋节

中秋节,又称月夕、秋节、仲秋节、八月节、八月会、追月节、玩月节、拜月节、女儿节或团圆节,是流行于中国众多 ...

四大名著(中国古典长篇小说四大名著)

中国古典长篇小说四大名著,简称四大名著,是指《红楼梦》、《三国演义》、《水浒传》、《西游记》这四部巨著。 ...

朱棣文

朱棣文(steven chu),1948年2月28日生于美国密苏里州圣路易斯,美国第12任能源部部长[1 ...

促销

促销(promotion)就是营销者向消费者传递有关本企业及产品的各种信息,说服或吸引消费者购买其产品, ...

CCNA

ccna认证标志着具备安装、配置、运行中型路由和交换网络,并进行故障排除的能力。获得ccna认证的专业人 ...

孙中山(中国近代伟大的资产阶级革命先行者)

孙中山(1866年—1925年),名文,字载之,号日新,又号逸仙,幼名帝象,化名中山樵,常以中山为名。[ ...

腊八节

同义词 腊八一般指腊八节 腊八节,俗称“腊八” ,即农历十二月初八,古人有祭祀祖先神灵、祈求丰收吉祥 ...

五一国际劳动节

同义词 劳动节一般指五一国际劳动节 国际劳动节又称“五一国际劳动节”、“国际示威游行日”(inter ...

嘉峪关关城

嘉峪关关城在嘉峪关市区西南6公里处,位于嘉峪关最狭窄的山谷中部,地势最高的嘉峪山上,城关两翼的城墙横穿沙 ...