expressvalue.cpp

数据结构源程序

#include <stdio.h>

#define MAXSIZE 100

int InDigit(char);
int InOperator(char);
int Prior(char);

typedef struct SqStack
{
	char *elem;
	char *top;
}SqStack;

typedef char ElemType;
typedef int status;

status Init(SqStack& sq)
{
	sq.elem = NULL;
	sq.elem = new ElemType[MAXSIZE];
	sq.top = sq.elem;

	if(sq.elem) return 1;
	else return 0;
}

void Destroy(SqStack& sq)
{
	delete []sq.elem;
	sq.elem = NULL;
}

status Pop(SqStack& sq,ElemType& elem)
{
	if(sq.elem == sq.top)
	{
		printf("\n栈为空!\n");
		return 0;
	}
	elem = *(--sq.top);
	return 1;
}

status Push(SqStack& sq,ElemType elem)
{
	if(sq.top-sq.elem >= MAXSIZE)
	{
		printf("\n栈满!不能入栈!\n");
		return 0;
	}
	*sq.top++ = elem;
}

ElemType Top(SqStack& sq)
{
	if(sq.elem == sq.top)
	{
		printf("\n栈空!\n");
	}
	return *(sq.top-1);
}


void ToSuffix(char *exp,char *suffix)
{
	char *pexp = exp;
	char *psuffix = suffix;
	char elem;

	SqStack sq;
	
	if(!Init(sq))
		printf("初始化失败！");

	Push(sq,'#');

	while(*pexp!='#')
	{
		if(InDigit(*pexp))
			*psuffix++ = *pexp++;
		else if(*pexp == '(')
		{
			Push(sq,*pexp);
			pexp++;
		}
		else if(InOperator(*pexp))
		{
			while(Prior(*pexp) <= Prior(Top(sq)))
			{
				Pop(sq,elem);
				*psuffix++ = elem;
			}
			Push(sq,*pexp);
			pexp++;
		}
		else if(*pexp == ')')
		{
			while(Top(sq)!='(')
			{
				Pop(sq,elem);
				*psuffix++ = elem;
			}
			Pop(sq,elem);
            pexp++;
		} 
		else
			continue;
	}

	while(*pexp == '#' && Top(sq)!='#')
	{
		Pop(sq,elem);
		*psuffix++ = elem;
	}
    *psuffix = 0;
	
}

int InDigit(char ch)
{
	if(ch>='0' && ch<='9')
		return 1;
	else 
		return 0;
}

int InOperator(char ch)
{
	char opset[4]={'+','-','*','/'};
	
    for(int i=0;i<4;i++)
		if(ch == opset[i])
			return 1;
	return 0;
}

int Prior(char ch)
{
	if(ch == '*' || ch=='/')
		return 3;
	else if(ch == '+' || ch=='-')
		return 2;
	else if(ch == '#')
		return 0;
	else if(ch =='(' || ch==')')
		return 1;
}

int Calculate(int val1,int val2,char ch)
{
    if(ch == '+')
		return val1+val2;
	else if(ch == '-')
		return val1-val2;
	else if(ch == '*')
		return val1*val2;
	else if(ch == '/')
		return val1/val2;
}

int Value(char* suffix)
{
	SqStack sq;
    char elem1,elem2;
	int val1,val2,val3,digit;

	Init(sq);

	char *psuffix=suffix;

	while(*psuffix)
	{
		if(InDigit(*psuffix))
			Push(sq,*psuffix);
		else if(InOperator(*psuffix))
		{
			Pop(sq,elem1);
			Pop(sq,elem2);
			val1 = elem1 - '0';
			val2 = elem2 - '0';
			val3 = Calculate(val1,val2,*psuffix);
			Push(sq,val3+'0');
		}
		psuffix++;
	}
    char elem;
	Pop(sq,elem);
	Destroy(sq);

	return elem-'0';
}

main()
{
	char *suffix = new char[20];
	char *exp = new char[20];
     
	printf("\n输入表达式：");
	scanf("%s",exp);

	ToSuffix(exp,suffix);

	printf("\n%s\n",suffix);
	printf("value = %d\n",Value(suffix));


}