tank.cpp

排序算法比较 排序算法比较

#include <math.h>
#include <iostream>
#include <string.h>
#include <assert.h>
#include <sstream>
using namespace std;

const int stackIncreament=20;

/*##################################################*/
template <class T>
class Stack
{
	public:
		Stack(int sz=50);
		~Stack(){delete[]elements;}
		void Push(const T& x);
		bool Pop(T& x);
		bool getTop(T& x);
		bool IsEmpty()const {return(top==-1)?true:false;}
		bool IsFull()const {return(top==maxSize-1)?true:false;}
		int getSize()const{return top+1;}
		void MakeEmpty(){top=-1;}
		friend ostream& operator<<(ostream& os,Stack<T>& s);
	private:
		T* elements;
		int top;
		int maxSize;
		void overflowProcess();

};

template <class T>
Stack<T>::Stack(int sz):top(-1),maxSize(sz)
{
	elements=new T[maxSize];
	assert(elements!=NULL);
};

template<class T>
void Stack<T>::overflowProcess()
{
	T* newArray=new T[maxSize+stackIncreament];
	if(newArray=NULL)
	{
		cerr<<"动态分配失败!"<<endl;
		exit(1);
	}
	for(int i=0;i<=top;i++)
		newArray[i]=elements[i];
	maxSize=maxSize+stackIncreament;
	delete []elements;
	elements=newArray;
};

template <class T>
void Stack<T>::Push(const T& x)
{
	if(IsFull()==true)
		overflowProcess();
	elements[++top]=x;
};

template<class T>
bool Stack<T>::Pop(T& x)
{
	if(IsEmpty()==true)
		return false;
	x=elements[top--];
	return true;
};

template<class T>
bool Stack<T>::getTop(T& x)
{
	if(IsEmpty()==true)
		return false;
	x=elements[top];
	return true;
};

template <class T>
ostream& operator<<(ostream& os,Stack<T>& s)
{
	os<<"top="<<s.top<<endl;
	for(int i=0;i<=s.top;i++)
		os<<i<<":"<<s.elements[i]<<endl;
	return os;
};

/*##################################################*/
class Calculator{
public :
	Calculator(int sz):s(sz){}
	void Run(char*,int);
	void Clear();
private:
	Stack<double> s;
	char* ch;
	void AddOperand(double value);
	bool Get2Operands(double &left,double &right);
	void DoOperator(char op);
};

void Calculator ::DoOperator(char op){
	double left ,right;
	double value=0.0;
	int result;
	result=Get2Operands(left,right);
	if(result==true)
	{
		switch(op)
		{
		case 43:
			value=left+right;
			s.Push(value);
			break;
		case 45:
			value=left-right;
			s.Push(value);
			break;
		case 42:
			value=left*right;
			s.Push(value);
			break;
		case 47:
			if(right==0.0)
			{
				cerr<<"Divide by 0!"<<endl;
				Clear();
			}
			else
			{
				value=left/right;
				s.Push(value);
				break;
			}
		}
	}
	else
		Clear();
};

bool Calculator::Get2Operands(double& left,double& right)
{
	if(s.IsEmpty()==true)
	{
		cerr<<"缺少右操作数!"<<endl;
		return false;
	}
	s.Pop(right);
	if(s.IsEmpty()==true)
	{
		cerr<<"缺少左操作数!"<<endl;
		return false;
	}
	s.Pop(left);
	return true;
};

void Calculator::AddOperand(double value)
{
	s.Push(value);
};

void Calculator::Run(char e[],int size)
{
	char* ch;
	double newOperand;
	ch=strtok(e," ");
	for(int i=0;i<size;i++)
	{
		if(ch[0]==43||ch[0]==45||ch[0]==42||ch[0]==47)
		{
			DoOperator(ch[0]);
		}
		else
		{
			newOperand=atof(ch);
		    AddOperand(newOperand);
		}
		ch=strtok(NULL," ");
	}
	double key=0.0;
	s.Pop(key); 
	cout<<key<<endl;
};
void Calculator::Clear()
{
	s.MakeEmpty();
}

bool isdigit(char c)
{
	switch(c)
	{
	case'0':case'1':case'2':case'3':case'4':
	case'5':case'6':case'7':case'8':case'9':
		return true;
	}
	return false;
}

/*##################################################*/

int isp(char c)
{
	switch(c)
	{
	case'#':
		return 0;
	case'(':
		return 1;
	case'*': case'/':
		return 5;
	case'+': case'-':
		return 3;
	case')':
		return 6;
	default:
		return 0;
	}
}

int icp(char c)
{
	switch(c)
	{
	case'#':
		return 0;
	case'(':
		return 6;
	case'*': case'/':
		return 4;
	case'+': case'-':
		return 2;
	case')':
		return 1;
	default:
		return -1;		
	}
}

void postfix(char* e)
{
	char* str=new char[50];
	int num=0;
	int num2=0;
	Stack<char> s;
	char ch='#',ch1,op;
	s.Push(ch);
	ch=e[num++];
	while(s.IsEmpty()==false||ch!='#')
	{
		if(isdigit(ch)||ch=='.')
		{	
			str[num2++]=ch;
			cout<<ch;
			ch=e[num++];
		}
		else
		{
			cout<<" ";
			str[num2++]=' ';
			s.getTop(ch1);
			if(isp(ch1)<icp(ch))
			{				
				s.Push(ch);
				ch=e[num++];
			}
			else if(isp(ch1)>icp(ch))
			{	
				s.Pop(op);
				cout<<op;
				str[num2++]=op;				
			}
			else
			{
				s.Pop(op);
				if(op=='(')
				{
					num2--;
					ch=e[num++];
                }
				if(op==')')
					num2--;
				
			}
		}
	}
	str[num2++]='#';
	cout<<"\n\n"; 
	delete []e;
	e=new char[50];
	for(int i=0;i<50;i++)
	{	
		if(str[i]==' '&&str[i+1]==' ')
		{}
		else
		{
			e[i]=str[i];
			if(str[i]=='#')
			break;
		}
				
	}
}
/*##################################################*/
int main()
{	
	cout<<"请输入计算表达式,以＃结束"<<endl;
	char* s=new char[50];
	for(int i=0;i<50;i++)
	{
		cin>>s[i];
		if(s[i]=='#')
			break;
	}
    postfix(s);
	int size;
	for(int j=0;j<50;j++)
	{
		if(s[j]=='#')
		{
			size=j+1;
			break;
		}
	}
	char snew[30];
	for(int h=0;h<size;h++)
	{
		snew[h]=s[h];
		//cout<<snew[h];
	}
	int sz=0;
	for(int k=0;k<size;k++)
	{
		if(snew[k]==' ')
			sz++;
	}

	Calculator calc(50);
	calc.Run(snew,sz);
    delete []s;
	return 0;
}