分享
 
 
 

数据结构辅导---栈和队列(2)

王朝other·作者佚名  2008-06-01
窄屏简体版  字體: |||超大  

3. 把中缀表达式转换为后缀表达式的算法

设以’@’字符作为结束符的中缀算术表达式已经保存在s1字符串中,转换后得到的后缀算术表达式拟存于s2字符串中。由中缀表达式转换为后缀表达式的规则可知:转换前后,表达式中的数值项的次序不变,而运算符的次序发生了变化,由处在两个运算对象的中间变为处在两个运算对象的后面,同时去掉了所有的括号。为了使转换正确,必须设定一个运算符栈,并在栈底放入一个非凡算符,假定为’@’字符,让它具有最低的运算符优先级,假定为数值0,此栈用来保存扫描中缀表达式得到的暂不能放入后缀表达式中的运算符,待它的两个运算对象都放入到后缀表达式以后,再令其出栈并写入到后缀表达式中。

把中缀表达式转换为后缀表达式算法的基本思路是从头到尾地扫描中缀表达式中的每个字符,对于不同类型的字符按不情况进行处理。若碰到的是空格则认为是分隔符,不需要进行处理;若碰到的是数字或小数点,则直接写入到s2中,并在每个数值的最后写入一个空格;若碰到的是左括号,则应把它压入到运算符栈中,待以它开始的括号内的表达式转换完毕后再出栈;若碰到的是右括号,则表明括号内的中缀表达式已经扫描完毕,把从栈底直到保存着的对应左括号之间的运算符依次退栈并写入s2串中;若碰到的是运算符,当该运算符的优先级大于栈顶运算符的优先级(加减运算符的优先级设定为1,乘除运算符的优先级设定为2,在栈中保存的非凡运算符’@’和’(’的优先级设定为0)时,表明该运算符的后一个运算对象还没有被扫描并放入到s2串中,应把它暂存于运算符栈中,待它的后一个运算对象从s1串中读出并写入到s2串中后,再另其出栈并写入s2串中;若碰到的运算符的优先级小于等于栈顶运算符的优先级,这表明栈顶运算符的两个运算对象已经被保存到s2串中,应将栈顶运算符退栈并写入到s2串中,对于新的栈顶运算符仍继续进行比较和处理,直到被处理的运算符的优先级大于栈顶运算符的优先级为止,然后另该运算符进栈即可。

按照以上过程扫描到中缀表达式结束符’@’时,把栈中剩余的运算符依次退栈并写入到后缀表达式中,再向s2写入表达式结束符’@’和字符串结束符’\0’,整个转换过程就处理完毕,在s2中就得到了转换成的后缀表达式。

例如,设中缀算术表达式s1为:10+(18+9*3)/15-6@,使用的运算符栈用R表示,则转换过程如下:

(1)开始时存放后缀表达式的字符串s2为空,R中压入有’@’算符,它具有最低的优先级0:

@

(2)当扫描到s1中的左括号时,s2和R中的数据变化如下:

1 0

@ + (

(3)当扫描到s1中的数值3时,s2和R中的数据变化为:

1 0 1 8 9 3

@ + ( + *

(4)当扫描到s1中的右括号时,s2和R变为:

1 0 1 8 9 3 * +

@ +

(5)当扫描到s1中的数值15时,s2和R又变为:

1 0 1 8 9 3 * + 1 5

@ + /

(6)当扫描到s1中的’@’字符时,s2和R为:

1 0 1 8 9 3 * + 1 5 / + 6

@ -

1 0 1 8 9 3 * + 1 5 / + 6 - @ Ù

(7)当整个处理过程结束后,R栈为空,s2为:

将中缀算术表达式转换为后缀算术表达式的算法描述如下:

void Change(char* s1, char* s2)

// 将字符串s1中的中缀表达式转换为存于字符串s2中的后缀表达式

{

Stack R; // 定义用于暂存运算符的栈

InitStack(R); // 初始化栈

Push(R,'@'); // 给栈底放入'@'字符,它具有最低优先级0

int i,j;

i=0; // 用于指示扫描s1串中字符的位置,初值为0

j=0; // 用于指示s2串中待存字符的位置,初值为0

char ch=s1[i]; // ch保存s1串中扫描到的字符,初值为第一个字符

while(ch!='@')

{ // 顺序处理中缀表达式中的每个字符

if(ch==' ')

// 对于空格字符不做任何处理,顺序读取下一个字符

ch=s1[++i];

else if(ch=='(')

{ // 对于左括号,直接进栈

Push(R,ch);

ch=s1[++i];

}

else if(ch==')')

{ // 对于右括号,使括号内的仍停留在栈中的运算符依次

// 出栈并写入到s2中

while(Peek(R)!='(')

s2[j++]=Pop(R);

Pop(R); // 删除栈顶的左括号

ch=s1[++i];

}

else if(ch=='+'ch=='-'ch=='*'ch=='/')

{ // 对于四则运算符,使暂存在栈中的不低于ch优先级

// 的运算符依次出栈并写入到s2中

char w=Peek(R);

while(Precedence(w)>=Precedence(ch))

{ // Precedence(w)函数返回运算符形参的优先级

s2[j++]=w;

Pop(R); w=Peek(R);

&n

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有