expression.cpp

常用算法与数据结构原代码

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

#define RADIX 10
#define POW 1
#define MUL 2
#define DIV 3
#define ADD 4
#define SUB 5
#define LP  6
#define RP  7
#define END 8
#define EPS 1e-7

struct {
	char op;
	int code;
} opchTbl[]={{'^',1},{'*',2},{'/',3},{'+',4},{'-',5},{'(',6},
			{')',7},{'\n',8},{' ',-1}};

int osp[]={5,3,3,2,2,5,1,1},isp[]={4,3,3,2,2,0};
int c=' ';
   

typedef struct node {
	double data;
	node *link;
} LNODE;
LNODE *optop,*numtop;

void l_push(double x,LNODE *&toppt)
{
	LNODE *p=new LNODE;
	p->data=x;
	p->link=toppt;
	toppt=p;
}

int l_pop(double &x,LNODE *&toppt)
{
	LNODE *p=toppt;
	if (toppt==NULL)
		return 1;
	x=p->data;
	toppt=p->link;
	delete p;
	return 0;
}

void synError()
{
	double temp;
	cout<<"The expression is error!"<<endl;
	while (optop!=NULL)
		l_pop(temp,optop);
	while (numtop!=NULL)
		l_pop(temp,numtop);
	exit(0);
}

double eval(int tag,double left,double right)
{
	int n;
	double result;
	switch (tag)
	{
	case POW :if (right==0)
				  return 1;
		      for (n=1,result=left;n<right;n++)
				  result*=left;
			  return result;
	case ADD :return left+right;
	case SUB :return left-right;
	case MUL :return left*right;
	case DIV :if (fabs(right)<EPS)
			  {
				  cout<<"Error!"<<endl;
				  exit(1);
			  }
		      return left/right;
	}
}

int getToken(double &nump)
{
	double dradix,num;
	int i;
	while (c==' ' || c=='\t')
		c=getchar();
	if (c<'0' || c>'9')
	{
		for (i=0;opchTbl[i].code!=-1 && opchTbl[i].op!=c;i++)
			;
		if (opchTbl[i].code==-1)
			synError();
		if (c!='\n')
			c=getchar();
		return opchTbl[i].code;
	}
	num=0;
	while (c>='0' && c<='9')
	{
		num=RADIX*num+c-'0';
		c=getchar();
	}
	if (c=='.')
	{
		dradix=1.0/RADIX;
		c=getchar();
		while (c>='0' && c<='9')
		{
			num=num+(c-'0')*dradix;
			dradix/=RADIX;
			c=getchar();
		}
	}
	nump=num;
	return 0;
}

void main()
{
	double num,op,operand1,operand2,res;
	int type;
	char ans;
	do{
		cout<<"Please input the expression:"<<endl;
		optop=numtop=NULL;
		l_push(LP,optop);
		do{
			c=getchar();
		}
		while (c==' '||c=='\n'||c=='\t');
		while (1)
		{
			type=getToken(num);
			if (type==0)
				l_push(num,numtop);
			else
			{
				if (osp[type-1]>isp[(int)optop->data-1])
					l_push((double)type,optop);
				else
				{
					while (osp[type-1]<=isp[(int)optop->data-1] && optop->data<=5)
					{
						if (l_pop(op,optop))
							synError();
						if (l_pop(operand2,numtop))
							synError();
						if (l_pop(operand1,numtop))
							synError();
						res=eval((int)op,operand1,operand2);
						l_push(res,numtop);
					}
					if (type==END)
						break;
					if (type==RP)
					{
						do{
							if (l_pop(op,optop))
								synError();
						}
						while ((int)op!=LP);
					}
					else
						l_push((double)type,optop);
				}
			}
		}
		if (l_pop(operand1,numtop))
			synError();
		cout<<"The answer is :"<<operand1<<endl;
		while (optop!=NULL)
			l_pop(op,optop);
		while (numtop!=NULL)
			l_pop(res,numtop);
		cout<<"Continued or not?"<<endl;
		cin>>ans;
	}
	while (ans=='y' || ans=='Y');
}