calculator.cpp

实现多项式表达式的运算器利用栈实现表达式计算器的模板类；用表达式计算器类和多项式类实现多项式表达式的计算器

#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#include<conio.h>
#include"stack.hpp"
#include"namedpolynomial.hpp"


template<class Type>
class Calculator
{
public:
	Calculator(){}//Constructor
	void Run();   //多项式的执行函数
	void Clear(); //清空运算数栈s中的内容
private:
	void getOperand();//取得计算器要运算的多项式
	bool isOperator(char ch);//判断输入的字符是否为运算符
	bool isIdentifier(char ch);//判断输入的字符是否合法的标识符
	void postfix(char p[],char q[]);//将中序表达式转化为后续表达式
	int icp(char ch);//判断一个运算符的栈外优先数
	int isp(char ch);//判断一个运算符的栈内优先数
	void AddOperand(Type value);//运算数进栈
	bool Get2Operands(Type& left, Type& right);//从运算数栈中取两个运算数作运算
	void DoOperator(char op);//作运算
	
	Stack<Type> s;//暂存运算数的堆栈
	Type* operand;//用户输入的运算运算数数组，运算数堆栈将从这里取得符合要求的运算数进栈
	int operandscount;//计算某次计算中计算器总共有几个不同运算数
};

//////////////////////////////////////////////////////////////////////
template<class Type>
void Calculator<Type>::AddOperand(Type value)
{
	//运算数进栈
	s.Push(value);
}
//////////////////////////////////////////////////////////////////////
template<class Type>
bool Calculator<Type>::Get2Operands(Type& left,Type& right) 
{
	//从运算数栈中取两个运算数作运算
	if(s.IsEmpty())
	{
		cerr<<"Missing Operand!"<<endl;
		return false;
	}
	right = s.Pop();
	if(s.IsEmpty())
	{
		cerr<<"Missing Operand!"<<endl;
		return false;
	}
	left=s.Pop();
	return true;
}
//////////////////////////////////////////////////////////////////////
template<class Type>
void Calculator<Type>::DoOperator(char op)
{
	Type left, right;
	bool result;
	result=Get2Operands(left,right);
	if(result == true)
	switch(op)
	{
		case '+':  { s.Push(left+right);  break; }
		case '-':  { s.Push(left-right);  break; }
		case '*':  { s.Push(left*right);  break; }
		default:   
			{
				cerr<<"Error!This operation is not defined!"<<endl;
				Clear();
				exit(1);
			}
	}
	else
		Clear();
}
//////////////////////////////////////////////////////////////////////
template<class Type>
void Calculator<Type>::Clear()
{
	s.MakeEmpty();
}
//////////////////////////////////////////////////////////////////////
template<class Type>
int Calculator<Type>::icp(char ch)
{
	//输出运算符的栈外优先数
	switch (ch)
	{
	    case '=':  return 0;
        case '(':  return 8;
        case '^':  return 6;
        case '*':  
		case '/':  
		case '%': return 4;
        case '+':   
		case '-': return 2;
        case ')': return 1;
    }
	return -1;
}
//////////////////////////////////////////////////////////////////////
template<class Type>
int Calculator<Type>::isp(char ch)
{  
	//输出运算符的栈内优先数
    switch (ch)
	{
        case '=':  return 0;
        case '(':  return 1;
        case '^':  return 7;
        case '*':  
		case '/':  
		case '%':  return 5;
        case '+':  
		case '-':  return 3;
        case ')':  return 8;
    }
	return -1;
}
//////////////////////////////////////////////////////////////////////
template<class Type>
void Calculator<Type>::Run()
{
	//数组p存放转化后的后序表达式，q存放原来的中序表达式
	char p[100],q[100];
	getOperand();//先取得所作运算的运算对象
	
	//提示用户输入运算对象之间的运算表达式
	cout<<"请输入所要作的运算的表达式:"<<endl;
	
	//postfix函数将读入运算的中序表达式，并将它转化为相应的后序表达式
	//在转化后的后序表达式中，运算对象之间，运算对象与运算符之间用空格
	//分开，以便下面的while循环解析不同的多项式名，从而在operand数组中取得
	//所需要的运算多项式
	postfix(p,q);

	while( (p[0] != '=') && (p[0]!='\0'))//扫描后序多项式,'='为运算结束标志
	{
		int n=strlen(p);//求得后序多项式字符串的长度
		//如果串的首字符是'+' '-' '*'之一，则执行已经运算
		if( (p[0] == '+') || (p[0] == '-') || (p[0] == '*'))
		{
			DoOperator(p[0]);//执行运算
			//当前运算已完成，将后序表达式串中的内容前移，消去已做的运算符
			//即将字符串中后面n-1个字符(除去已上面已做的运算的运算符)复制到
			//字符串前面
			strncpy(p,p+1,n-1);
		}

		//如果串的首字符是标识符，在operand数组中搜索名字与当前后序
		//表达式的运算对象名字一致的多项式，并执行读取运算数入栈的工作
		else if( isIdentifier(p[0]) )
		{
			//字符数组记录当前后序表达式的运算对象的名字
			char* m=new char[100];
			
			//以下语句段将当前后序表达式的运算对象的名字复制到字符串m中
			m[0] = p[0];
			for(int i=1;p[i]!=' ';i++)
				m[i]=p[i];
			m[i]='\0';
			//用m串创建一个String对象
			String s=m;

            //在operand数组中搜索名字与当前后序表达式的运算对象名字
		    //一致的多项式，并执行读取运算数入栈的工作
			for(int j=0;j<operandscount;j++)
			{
				if( s==operand[j].getName() )
					AddOperand(operand[j]);
			}

			strncpy(p,p+i+1,n-i-1);//当前运算已完成，将后序表达式串中的内
			//容前移，移除已进栈的运算数即将字符串中后面n-i-1个字符(除去已
			//上面已进栈的运算数)复制到字符串前面
		}
		else
		{
			cerr<<"Error!Unknown charactor "<<p[0]<<"!The Calculator can't do it!"<<endl;
			exit(1);
		}
	}
	assert(!s.IsEmpty());//若栈底无数，错误！终止
	cout<<"结果多项式:"<<endl;
	cout<<q<<"="<< s.Pop().getPoly()<<endl;//输出结果（栈底元素）
}
//////////////////////////////////////////////////////////////////////
template<class Type>
void Calculator<Type>::postfix(char p[],char q[])
{
	//将中序表达式转化为后续表达式，转化后的后序表达式存于数组p中转化前
	//的中序表达式存放于q中，两个数组返回Run中继续执行计算器的运算
	
	Stack<char> s;//存放运算符的堆栈
	char ch,y;
	int i=0,j=0;//数组p和q的计数器
	s.MakeEmpty();
	s.Push('=');//先将等号进栈
	
	//输入中序表达式，以'='为结束标志
	while(cin>>ch,ch!='=')
	{
		q[j++]=ch;//记录中序表达式的内容进数组q
		//判断输入的字符，如果是合法的表示符类型，直接将它记入数组p中
		if(isIdentifier(ch))
		{
			p[i]=ch;
			i++;
		}
		//如果输入字符是')'
		else if(ch==')')
		{
			//首先判断数组p中的最后一个字符是否表示符，如果是则插入空格
			//以便将计算对象－多项式的名字与运算符分隔开
			if(isIdentifier(p[i-1]))
			{
				p[i]=' ';
				i++;
			}
			//连续从运算符栈中退出运算符，直至'('为止
			for(y=s.GetTop();y!='(';y=s.GetTop())
			{
				s.Pop();
				p[i]=y;
				i++;
			}
			s.Pop();//最后将'('也从栈中退出
		}
		
		//如果输入的字符是运算符
		else if(isOperator(ch))
		{
			//如果该运算符是'('，并且数组p中的最后一个字符是标识符
			//则在p数组中插入一个空格作为分隔
			if((ch!='(') && isIdentifier(p[i-1]))
			{
				p[i]=' ';
				i++;
			}

			//改运算符是其他类型，比较运算符栈的栈顶元素与当前输入的运算符
			//的优先数，如果栈顶运算符的isp大于当前输入字符的icp，则不断从
			//栈中退出运算符，直至栈顶运算符的isp>当前输入运算符的icp为止
			for(y=s.GetTop();isp(y)>icp(ch);y=s.GetTop())
			{
				s.Pop();
				p[i]=y;
				i++;
			}
			//最后当栈顶运算符的isp不再大于当前输入字符的icp，则将ch进栈
			s.Push(ch);
		}
		else //否则输入字符不合法，提示并中止程序
		{
			cerr<<"Error!未知字符 "<<ch<<" 被输入！运算器无法完成计算！"<<endl;
			exit(1);
		}
	}
	//判断数组p中的最后一个字符是否表示符，如果是则插入空格
	if(isIdentifier(p[i-1]))
	{
		p[i]=' ';
		i++;
	}
	//最后从运算符栈中连续退出运算符存入p数组中，以完成后序表达式的转换
	while(!s.IsEmpty())
	{
		y=s.Pop();
		p[i]=y;
		i++;
	}
	//为p和q数组加上字符串结束符
	q[j]='\0';
	p[i]='\0';
}
//////////////////////////////////////////////////////////////////////
template<class Type>
bool Calculator<Type>::isIdentifier(char ch)
{
	//判断输入的字符是否合法的标识符，合法的表示符由数字，字母和下划线组成
	if( ((ch>='a')&&(ch<='z')) || ((ch>='A')&&(ch<='Z')) || ((ch>='0')&&(ch<='9'))||(ch=='_'))
		return true;
	else 
		return false;
}
//////////////////////////////////////////////////////////////////////
template<class Type>
bool Calculator<Type>::isOperator(char ch)
{
	//判断输入的字符是否为运算符
	switch(ch)
	{
	case '+':
	case '-':
	case '*':
	case '(':
	case ')':return true;
	}
	return false;
}
//////////////////////////////////////////////////////////////////////
template<class Type>
void Calculator<Type>::getOperand()
{
	//取得计算器要运算的多项式
	cout<<"您总共需要输入多少个多项式作为计算对象?请输入:"<<endl;
	cin>>operandscount;
	operand=new namedPolynomial[operandscount];
	
	for(int i=1;i<=operandscount;i++)
	{
		cout<<"输入多项式"<<i<<":"<<endl;
		cin>>operand[i-1];
	}
	
}
//////////////////////////////////////////////////////////////////////
//主函数
void main()
{
	cout<<"本程序为多项式计算器。用于完成多项式的加，减，乘等多项式的复合运算。"<<endl;
	cout<<endl;
	cout<<endl;
	cout<<"程序即将开始。若要启动多项式计算器请按任意键。"<<endl;
	cout<<endl;
	cout<<endl;
	getch();

	char y='y';
	while(y=='y')
	{
		Calculator<namedPolynomial> a;
	    a.Run();
		cout<<endl;
		cout<<endl;
		cout<<"需要继续做其他多项式运算吗?y－继续，n－退出。请输入你的选择:"<<endl;
		cin>>y;
	}

	cout<<endl;
	cout<<endl;
	getch();
	cout<<"多项式计算器程序结束!感谢使用!"<<endl;
	cout<<endl;
	cout<<endl;
}