순서 스 택 구현 표현 식 값

5782 단어 데이터 구조
/*
* Created by Microsoft Visual Studio 2013
* @author: Teresa
* @date: 2017-10-07
* @description:      
*/

#include 
#include 
/*     */
#define TRUE 1	//  
#define OK 1
#define FALSE 0	//   
#define ERROR 0	//   
#define INFEASIBLE -1	//    
#define OVERFLOW -2 	//  

#define STACK_INIT_SIZE 100	//         
#define STACKINCREMENT 10	//        

typedef double OpndType;		//	           
typedef char OptrType;		//	           
typedef int Status;	//         


/*    */
typedef struct{
	OptrType *base;   //    ,      ,   null      
	OptrType *top; //    , top == base ,   ;
	int stackSize; //          ,      
}OptrStack;
//top-base          

/*    */
typedef struct{
	OpndType *base;
	OpndType *top;
	int stackSize;
}OpndStack;
	

/*      */
//      
Status InitOptrStack(OptrStack &S){
	S.base = (OptrType *)malloc(STACK_INIT_SIZE*sizeof(OptrType));
	if (!S.base)
		exit(ERROR);
	S.top = S.base;	//      
	S.stackSize = STACK_INIT_SIZE;
	return OK;
}
//  S     
Status OptrStackEmpty(OptrStack &S){
	if (S.top == S.base)
		return TRUE;
	else
		return FALSE;
}
//       e  S         OK   ERROR
Status GetOptrTop(OptrStack S, OptrType &e){
	if (S.top > S.base){
		e = *(S.top - 1);
		return OK;
	}
	else
		return ERROR;
}
//  e       
Status OptrPush(OptrStack &S, OptrType e){
	if (S.top - S.base == S.stackSize){
		//         
		S.base = (OptrType*)realloc(S.base, (S.stackSize + STACKINCREMENT)*sizeof(OptrType));
		if (!S.base)
			exit(ERROR);
		S.top = S.base + S.stackSize;	//      
		S.stackSize += STACKINCREMENT;	//    
	}
	*(S.top++) = e;
	return OK;
}
//         S       e        OK     ERROR
Status OptrPop(OptrStack &S, OptrType &e){
	if (S.top == S.base) return ERROR;
	e = *--S.top;
	return OK;
}

/*      */
//      
Status InitOpndStack(OpndStack &S){
	S.base = (OpndType *)malloc(STACK_INIT_SIZE*sizeof(OpndType));
	if (!S.base)
		exit(ERROR);
	S.top = S.base;	//      
	S.stackSize = STACK_INIT_SIZE;
	return OK;
}
//  S     
Status OpndStackEmpty(OpndStack &S){
	if (S.top == S.base)
		return TRUE;
	else
		return FALSE;
}
//       e  S         OK   ERROR
Status GetOpndTop(OpndStack S, OpndType &e){
	if (S.top > S.base){
		e = *(S.top - 1);
		return OK;
	}
	else
		return ERROR;
}
//  e       
Status OpndPush(OpndStack &S, OpndType e){
	if (S.top - S.base == S.stackSize){
		//         
		S.base = (OpndType*)realloc(S.base, (S.stackSize + STACKINCREMENT)*sizeof(OpndType));
		if (!S.base)
			exit(ERROR);
		S.top = S.base + S.stackSize;	//      
		S.stackSize += STACKINCREMENT;	//    
	}
	*(S.top++) = e;
	return OK;
}
//         S       e        OK     ERROR
Status OpndPop(OpndStack &S, OpndType &e){
	if (S.top == S.base) return ERROR;
	e = *--S.top;
	return OK;
}

//     
int Rank(OptrType e){
	switch (e){
	case '#':
		return 0; break;
	case '(':
		return 1; break;
	case '+':
	case '-':
		return 2; break;
	case '*':
	case '/':
		return 3; break;
	default:
		return INFEASIBLE; break;
	}
}

//    
OpndType Operate(OpndType a, OpndType b, OptrType op){
	OpndType c;
	switch (op){
	case '+':
		c = a + b;
		break;
	case '-':
		c = a - b;
		break;
	case '*':
		c = a*b;
		break;
	case '/':
		if (b == 0){
			printf("   0");
			return ERROR;
		}
		else
			c = a / b;
		break;
	default:
		printf("        ");
		break;
	}
	return c;
}
Status StackTraverse(OpndStack S){
	while (S.top > S.base){
		printf("%d ", *(S.base++));
	}
	printf("
"); return OK; } Status StackTraverse1(OptrStack S){ while (S.top > S.base){ printf("%c ", *(S.base++)); } printf("
"); return OK; } // void HandleStr(char str[]){ OptrStack optr; // OpndStack opnd; // OptrType op; InitOptrStack(optr); // InitOpndStack(opnd); // int i, j; OpndType f, a, b,result; char num[100]; OptrPush(optr, '#'); for (i = 0; str[i]; i++){ switch (str[i]){ case '+': case '-': /* , , ; , , , , , , 。*/ GetOptrTop(optr, op); if (op == '#' || op == '('){ OptrPush(optr, str[i]); } else{ OpndPop(opnd, a); OpndPop(opnd, b); OptrPop(optr, op); OpndPush(opnd, Operate(b, a, op)); OptrPush(optr, str[i]); } break; case '*': case '/': GetOptrTop(optr, op); if (Rank(str[i]) > Rank(op) || op == '('){ OptrPush(optr, str[i]); } else{ OpndPop(opnd, a); OpndPop(opnd, b); OptrPop(optr, op); OpndPush(opnd, Operate(b, a, op)); OptrPush(optr, str[i]); } break; case '(': OptrPush(optr,str[i]); break; case ')': GetOptrTop(optr, op); while (op != '('){ OpndPop(opnd, a); OpndPop(opnd, b); OptrPop(optr, op); OpndPush(opnd, Operate(b, a, op)); GetOptrTop(optr, op); } OptrPop(optr, op); break; default: j = 0; do{ num[j] = str[i]; i++; j++; } while (str[i] > '0' && str[i] < '9' || str[i] == '.'); num[j] = '\0'; i--; f = atof(num); OpndPush(opnd, f); break; } } GetOptrTop(optr, op); while (op != '#'){ OpndPop(opnd, a); OpndPop(opnd, b); OptrPop(optr, op); OpndPush(opnd, Operate(b, a, op)); GetOptrTop(optr, op); } GetOpndTop(opnd, result); printf(" %s=%g
", str, result); } int main(){ char str[100]; printf(" :
"); scanf("%s", str); HandleStr(str); return 0; }

좋은 웹페이지 즐겨찾기