栈与队列

栈的应用举例

1.数制转换

//对于输入任意一个非负十进制整数,打印输出与其等值的八进制数
void conversion()
{
	InitStack(S);
	scanf("%d",N);
	while(N)
	{
		Push(S,N%8);
		N=N/8;
	}
	while(!StackEmpty(S))
	{
		Pop(S,e);
		printf("%d",e);
	}
} 

2.表达式求值

三个原则：

（1）先乘除后加减

（2）从左算到右

（3）先括号内后括号外

为实现算符优先算法，可以使用两个工作栈。一个称作OPTR，用以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。#为表达式起始符和结束符，作栈底元素。

OperandType EvaluteExpression()
//算术表达式求值的算符优先算法.
//设OPTR、OPND分别为运算符栈和运算数栈 
//OP为运算符集合 
{
	InitStack(OPTR); push(OPTR,'#');
	InitStack(OPND); 
	c=getchar();		
	while(c!='#'||GetTop(OPTR)!='#')
	{
		if(!In(c,OP))//判断不是运算符则进栈OPND 
		{
			Push(OPND,c);
			c=getchar;	
		}
		else
			switch(Precede(GetTop(OPTR),c))
			//precede,判断栈顶符号与输入符号优先级顺序 
			{
				case'<'://栈顶元素优先级低
					Push(OPTR,c);c=getchar();break;
				case'=':
				//脱括号并接收下一运算符（只有’（‘’）‘和’#‘’#‘比较时为’=‘） 
					Pop(OPTR,x);c=getchar();break;
				case'>'//退栈并将运算结果入栈
					Pop(OPTR,theta);
					Pop(OPND,b); Pop(OPND,a);
					Push(OPND,Operate(a,theta,b));//运算 a theta b（eg：1+2） 
					break; 	
			}	
	}
	return GetTop(OPND); 
}