sqstack.cpp

数据结构

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef struct{
	char *base;
	char *top;
	int stacksize;
}SqStack1;

typedef struct{
	double *base;
	double *top;
	int stacksize;
}SqStack2;

SqStack1 OPTR;
SqStack2 OPND;

double EvaluateExpression();
void CHAR_InitStack(SqStack1 &S);
void DOUBLE_InitStack(SqStack2 &S);
char CHAR_GetTop(SqStack1 S);
double DOUBLE_GetTop(SqStack2 S);
int CHAR_Push(SqStack1 &S , char e);
int DOUBLE_Push(SqStack2 &S , double e);
char CHAR_Pop(SqStack1 &S , char &e);
double DOUBLE_Pop(SqStack2 &S , double &e);
char Precede(char a,char b);
double Operate ( double d ,char e,double f);
int In(char c);


void main()
{
	double result;
	printf("*************************\n");
	printf("*      表达式计算       *\n");
	printf("*************************\n");
	printf("请输入一组表达式(以#号结束):\n");
	result = EvaluateExpression();
	printf("\n\n计算结果是(结果保留两位小数):%.2f\n\n\n",result);
}

void CHAR_InitStack(SqStack1 &S)
{
	S.base=(char *)malloc(STACK_INIT_SIZE * sizeof(char));
	if(!S.base)exit(OVERFLOW);
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
}

void DOUBLE_InitStack(SqStack2 &S)
{
	S.base=(double *)malloc(STACK_INIT_SIZE * sizeof(double));
	if(!S.base)exit(OVERFLOW);
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
}

char CHAR_GetTop(SqStack1 S)
{
	char e;
	if(S.top == S.base) return -1;
	e = *(S.top-1);
	return e;
}

double DOUBLE_GetTop(SqStack2 S)
{
	double e;
	if(S.top == S.base) return -1;
	e = *(S.top-1);
	return e;
}

int CHAR_Push(SqStack1 &S , char e)
{
	if(S.top - S.base >= S.stacksize)
	{
		S.base = (char *)realloc(S.base , (S.stacksize + STACKINCREMENT) * sizeof(char));
		if(!S.base) exit(OVERFLOW);
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*S.top++ = e;
	return 1;
}

int DOUBLE_Push(SqStack2 &S , double e)
{
	if(S.top - S.base >= S.stacksize)
	{
		S.base = (double *)realloc(S.base , (S.stacksize + STACKINCREMENT) * sizeof(double));
		if(!S.base) exit(OVERFLOW);
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*S.top++ = e;
	return 1;
}

char CHAR_Pop(SqStack1 &S , char &e)
{
	if(S.top == S.base)return -1;
	e = * --S.top;
	return e;
}

double DOUBLE_Pop(SqStack2 &S , double &e)
{
	if(S.top == S.base)return -1;
	e = * --S.top;
	return e;
}

int In(char c)  // 判断是否为运算符
{
	if ( c=='(' || c=='+' || c=='-' || c == '*' || c=='/' || c==')' || c=='#' || c=='^')
		return 1;
	else
		return 0;
}

char Precede(char a,char b) //判断优先级
{
    char op;
	switch(a)
	{
		case '#':
		    if (b=='#') 
				op='=';
			else op='<';
		    break;
		case '+':
			if (b=='*' || b=='/' || b=='('|| b=='^') 
				op='<';
			else op='>';
			break;
		case '-':
			if (b=='*' || b=='/' || b=='(' || b=='^')
				op='<';
			else op='>';
			break;
		case '*':
			if (b=='(' || b=='^')
				op='<';
			else op='>';
			break;
		case '/':
			if (b=='(' || b=='^')
				op='<';
			else op='>';
			break;
		case'^':
			if(b=='(')
				op='<';
			else op='>';
			break;
		case '(':
			if (b==')')
				op='=';
			else op='<';
			break;
		case ')':
			op='>';
			break;
    }
	return op;
}

double Operate( double d ,char e,double f) //计算
{
	double g;
	switch(e)
	{
		case '+':
			g=d+f;
			break;
		case '-':
			g=d-f;
			break;
		case '*':
			g=d*f;
			break;
		case '/':
			g=d/f;
			break;
		case '^':
			g=pow(d,f);
			break;
    }
	return g;
}

double EvaluateExpression()
{
	char c=0,theta,x;
	double a,b,number, n=0;
	CHAR_InitStack (OPTR);
	CHAR_Push (OPTR,'#');
	DOUBLE_InitStack (OPND);
	c = getchar();
	printf("\n转化成后缀表达式是:");
	while (c!='#'|| CHAR_GetTop(OPTR)!='#')
	{
		if(!In(c))
		{
			number=0;
			while(!In(c))
			{
				if(c=='.')
					break;
				number = number*10 +(c-48);
				c = getchar();
			}
			if(c=='.')
			{
				n=1;
				while(!In(c = getchar()))
				{
					number = number +(c-48)*(double)pow(0.1 , n);
					n++;
				}
			}
			DOUBLE_Push (OPND,number);
				printf("%.2f ",number);
		}
		else
		switch (Precede(CHAR_GetTop(OPTR),c))
		{
			case '<':
				CHAR_Push(OPTR , c);
				c=getchar();
				break;
			case '=':
				CHAR_Pop(OPTR , x);
				c=getchar();
				break;
			case '>':
				CHAR_Pop(OPTR , theta);
				printf("%c ",theta);
				DOUBLE_Pop(OPND , a);
				DOUBLE_Pop(OPND , b);
				DOUBLE_Push(OPND,Operate(b,theta,a));
				break;
		}
	}
	return (DOUBLE_GetTop(OPND));
}//int EvaluateExpression