数据结构考研分类复习真题 第三章 答案[8]

两栈共享一向量空间（一维数组）栈底设在数组的两端两栈顶相邻时为栈满设共享数组为S[MAX]则一个栈顶指针为另一个栈顶指针为MAX时栈为空

用C写的入栈操作push（ix）如下

const MAX=共享栈可能达到的最大容量

typedef struct node

{elemtype s[MAX]

int top[]

}anode

anode ds;

int push(int ielemtype x)

//ds为容量有MAX个类型为elemtype的元素的一维数组由两个栈共享其空间i的值为或x为类型为elemtype的元素本算法将x压入栈中如压栈成功返回否则返回

{if（dstop[]dstop[]==）{printf（栈满\n）return（）}

switch（i）

{case dss[++dstop[i]]=xbreak

case dss[dstop[i]]=x

return（）}//入栈成功

}

本程序段查找栈S中有无整数为k的元素如有则删除采用的办法使用另一个栈T在S栈元素退栈时若退栈元素不是整数k则压入T栈遇整数kk不入T栈然后将T栈元素全部退栈并依次压入栈S中实现了在S中删除整数k的目的若S中无整数k则在S退成空栈后再将T栈元素退栈并依次压入S栈直至T栈空这后一种情况下S栈内容操作前后不变

中缀表达式(+)*(/）的后缀表达式是 + / *

栈的变化过程图略（请参见题）表达式生成过程为

中缀表达式exp转为后缀表达式exp的规则如下

设操作符栈s初始为空栈后压入优先级最低的操作符#对中缀表达式从左向右扫描遇操作数直接写入exp若是操作符（记为w）分如下情况处理直至表达式exp扫描完毕

（）w为一般操作符（+*/等）要与栈顶操作符比较优先级若w优先级高于栈顶操作符则入栈否则栈顶运算符退栈到expw再与新栈顶操作符作上述比较处理直至w入栈

（）w为左括号（（）w入栈

（）w为右括号（））操作符栈退栈并进入exp直到碰到左括号为止左括号退栈（不能进入exp）右括号也丢掉达到exp中消除括号的目的

（）w为#表示中缀表达式exp结束操作符栈退栈到exp直至碰到#退栈整个操作结束

这里再介绍一种简单方法中缀表达式转为后缀表达式有三步首先将中缀表达式中所有的子表达式按计算规则用嵌套括号括起来接着顺序将每对括号中的运算符移到相应括号的后面最后删除所有括号

例如将中缀表达式(+)*(/）转为后缀表达式按如上步骤

执行完上面第一步后为(((+)*((/))))

执行完上面第二步后为((()+(()/))*)

执行完上面第三步后为 + / *

可用类似方法将中缀表达式转为前缀表达式

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []