데이터 구조 창고 의 응용 - 산술 표현 식 값 구하 기

실험 목적:
1. 창고 의 정의 와 실현 파악 하기;
2. 스 택 을 이용 하여 산술 표현 식 을 푸 는 방법 을 파악 한다.
실험 내용:
교재 의 알고리즘 3.4 를 보완 하고 스 택 을 이용 하여 산술 표현 식 의 값 을 구 하 는 알고리즘 을 수정 합 니 다.알고리즘 3.4 에서 호출 된 몇 가지 함수 에 대해 실현 과정 을 제시 해 야 합 니 다.
(1) 함수 인 (c): c 가 연산 자인 지 판단 하기;
(2) 함수 Precede (t1, t2): 연산 자 t1 과 t2 의 우선 순 위 를 판단 합 니 다.
(3) 함수 Operate (a, theta, b): a 와 b 를 이원 연산 theta.
프로그램 이 실 행 될 때 합 법 적 인 산술 표현 식 (중간 값 및 최종 결 과 는 0 ~ 9 사이 이 고 덧셈 과 괄호 포함) 을 입력 하면 해당 하 는 계산 결 과 를 출력 할 수 있 습 니 다.다음 그림:
 
   
#include
#include
#include
#include
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE 100
typedef int Status;
typedef char SElemType;
typedef struct
{
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack;
Status InitStack(SqStack &S)//    
{
	S.base=(SElemType*)malloc(sizeof(SElemType)*MAXSIZE);
	if(!S.base)
	exit(OVERFLOW);
	S.top=S.base;
	S.stacksize=MAXSIZE;
	return OK;
}
Status Push(SqStack &S,SElemType e)//   
{
	if(S.top-S.base==S.stacksize)
	return ERROR;//   
	*S.top++=e;//  e    ,     1; 
	return OK;
 } 
Status Pop(SqStack &S,SElemType &e)//   
{
	if(S.top==S.base)//   
	return ERROR;
	e=*--S.top;//      ,       e; 
	return OK;
}
SElemType GetTop(SqStack S)//      
{
	if(S.top!=S.base)//    
	return *(S.top-1);//        ,       
}
int In(SElemType e)//             
{
	if(e=='+'||e=='-'||e=='*'||e=='/'||e=='('||e==')'||e=='#')
	    return 1;//  
	else 
	    return 0; //   
}
SElemType Precede(SElemType a,SElemType b)//          
{
	SElemType f;
	if(a=='+'||a=='-')
	{
		if(b=='+'||b=='-'||b==')'||b=='#')
		    f='>';
		else if(b=='*'||b=='/'||b=='(')
		    f='';
		else if(b=='(')
		   f='';
	}
	else if(a=='#')
	{
		if(b=='+'||b=='-'||b=='*'||b=='/'||b=='(')
		   f='':
					Pop(OPTR,theta);
					Pop(OPND,b);
					Pop(OPND,a);
					Push(OPND,Operate(a,theta,b));
					break;
				case '=':
					Pop(OPTR,x);
				    ch=getchar();
					break;
			}
		} 
	}
	return GetTop(OPND)-'0';
}
int main()
{
	printf("        ,  #  
"); printf(" : %d
",EvaluateExpression()); return 0; }

좋은 웹페이지 즐겨찾기