/***
*DynaSeqStack.cpp?-?動態順序棧，即棧的動態順序存儲實現
*
*
*題目：表達式求值
*
*班級：A1?北極
*
*姓名：邱繼穎
*
*學號：2008010829
*	
****/

#include?
#include?
#include?
#include?
#include?“DynaSeqStack.h“

const?int?STACK_INIT_SIZE?=?100;	//?初始分配的長度
const?int?STACKINCREMENT??=?10;		//?分配內存的增量

/*------------------------------------------------------------
操作目的：	初始化棧
初始條件：	無
操作結果：	構造一個空的棧
函數參數：
		SqStack?*S	待初始化的棧
返回值：
		bool		操作是否成功
------------------------------------------------------------*/
bool?InitStack（SqStack?*S）
{
	assert（S?!=?NULL）;
	S->base?=?（ElemType*）malloc（sizeof（ElemType）?*?STACK_INIT_SIZE）;
	
	if（S->base?==?NULL）	return?false;

	S->top?=?S->base;
	S->stacksize?=?STACK_INIT_SIZE;

	return?true;
}

/*------------------------------------------------------------
操作目的：	銷毀棧
初始條件：	棧S已存在
操作結果：	銷毀棧S
函數參數：
		SqStack?*S	待銷毀的棧
返回值：
		無
------------------------------------------------------------*/
void?DestroyStack（SqStack?*S）
{
	assert（S?!=?NULL）;

	free（S->base）;
	S->top?=?S->base?=?NULL;
}

/*------------------------------------------------------------
操作目的：	判斷棧是否為空
初始條件：	棧S已存在
操作結果：	若S為空棧，則返回true，否則返回false
函數參數：
		SqStack?S	待判斷的棧
返回值：
		bool		是否為空
------------------------------------------------------------*/
bool?StackEmpty（SqStack?S）
{
	assert（（S.base?!=?NULL）?&&?（S.top?!=?NULL））;
	return（S.base?==?S.top）;
}

/*------------------------------------------------------------
操作目的：	得到棧的長度
初始條件：	棧S已存在
操作結果：	返回S中數據元素的個數
函數參數：
		SqStack?S	棧S
返回值：
		int			數據元素的個數
------------------------------------------------------------*/
int?StackLength（SqStack?S）
{
	assert（（S.base?!=?NULL）?&&?（S.top?!=?NULL））;
	return（S.top-S.base）;
}

/*------------------------------------------------------------
操作目的：	得到棧頂元素
初始條件：	棧S已存在
操作結果：	用e返回棧頂元素
函數參數：
		SqStack?S	棧S
		ElemType?*e	棧頂元素的值
返回值：
		bool		操作是否成功
------------------------------------------------------------*/
bool?GetTop（SqStack?S?ElemType?*e）
{
	assert（（S.base?!=?NULL）?&&?（S.top?!=?NULL））;
	if（StackEmpty（S））	
		return?false;

	*e?=?*（S.top-1）;
	return?true;
}

/*------------------------------------------------------------
操作目的：	遍歷棧
初始條件：	棧S已存在
操作結果：	依次對S的每個元素調用函數fp
函數參數：
		SqStack?S		棧S
		void?（*fp）（）	訪問每個數據元素的函數指針
返回值：
		無
------------------------------------------------------------*/
void?StackTraverse（SqStack?S?void?（*fp）（ElemType））
{
	assert（（S.base?!=?NULL）?&&?（S.top?!=?NULL））;
	for（;?S.basese++）	
		（*fp）（*S.base）;
}

/*------------------------------------------------------------
操作目的：	壓棧——插入元素e為新的棧頂元素
初始條件：	棧S已存在
操作結果：	插入數據元素e作為新的棧頂
函數參數：
		SqStack?*S	棧S
		ElemType?e	待插入的數據元素
返回值：
		bool		操作是否成功
------------------------------------------------------------*/
bool?Push（SqStack?*S?ElemType?e）
{
	if（S?==?NULL）	return?false;
	assert（（S->base?!=?NULL）?&&?（S->top?!=?NULL））;

	//?validate?overflow
	if（StackLength（*S）?==?S->stacksize）
	{
		El