第三章 栈和队列
3.21
逆波兰式——后缀
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
达式
如ab+ ，ab*c/ ，abc+*
分别表示：a+b, a*b/c, a*(b+c)
对于逆波兰算法是通过出栈和入栈来实现表达式求值,也是将表达式有
中缀表达式变成后缀表达式来进行求解.下面是具体实现逆波兰算法的
过程:
a.建立两个栈：第一个位数字栈，第二个位算符栈！(将栈定义为char
类型)
b.对数字来说是无条件压入数字栈中.
c.而对符号来说，只有当前栈顶元素的优先值小于扫到的符号时（比
如"+"小于"*"），此符号才压入栈;否则大于等于的情况是将当前栈顶
元素弹出栈，与当前数字栈的前两个数字组成式子进行计算.计算结果
当作数号作为字压入数字栈作为栈顶元素（要舍弃已经弹出的两个数
字），而那个扫描到的符号则将代替那个弹出的符栈顶元素）。
d.最后说一下括号，原则是扫描到左括号时无条件压入符号栈，而扫
到右括号时，则弹出离栈顶最近的一个左括号以上的全部符号与数字
栈的数字做运算。
3.21
void NiBoLan(char *str,char *new)//把中缀表达式str转换成逆波兰式new
{
p=str;q=new; //为方便起见,设str的两端都加上了优先级最低的特殊符号
InitStack(s); //s为运算符栈
while(*p)
{
if(*p是字母)) *q++=*p; //字母直接输出
else
{
c=gettop(s);
if(*p优先级比c高) push(s,*p); //运算符只有优先级比栈顶元素高才入栈
else
{
while(gettop(s)// 运算符栈顶元素出栈，输出
{
pop(s,c);*(q++)=c;
}//while
push(s,*p); //运算符在栈内遵循越往栈顶优先级越高的原则
}//else
}//else
p++;
}//while
}//NiBoLan //参见编译原理教材
3.21
void NiBoLan(char *str,char *new)//把中缀表达式str转换成逆波兰式new
{
IinitStack(OPTR);
Push(OPTR,’#’);
c= getchar();
while(c!=‘#’||GetTop(OPTR)!=‘#’)
{
if(!=In(c,op))
{putchar(c);c= getchar();}//不是运算符则输出
else
{
switch(precede(GetTOP(OPTR,c))){
case ‘<’:Push(OPTR,c);c=getchar();break;
case ‘=’:Pop(OPTR,x);c=getchar();break ;//脱括号
case ‘>’:putchar(Pop(OPTR,theta));break;}
}
}
3.32
3.32 fn≤Max fn+1≥Max
参考答案
void GetFib_CyQueue(int k,int n)//求k阶斐波那契序列的前n+1项
{
InitCyQueue(Q); //其MAXSIZE设置为k
for(i=0;i
Max) return;
Q.base[m]=sum; //求第i项的值存入队列中并取代已无用的第一项
printf("%d",sum);
}
}//GetFib_CyQueue
浙公网安备 33021202002483