순서 스 택 구현 표현 식 값

/*
* 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;
}