表达式求值(c++).cpp

表达式求值的源代码,注释完全,适合初学者使用

#include<iostream>
using namespace std;
typedef struct queue
{//队列的元素节点
	int sign;//记录当前节点中存储数据的类型
	union item//节点中存储的数据
	{
		float num;
		char oper;
	}item;
	struct queue *next;
}queue;
class Queue 
{//队列类
private:
	queue *head,*rear;//队头,队尾
public:
	void print();//输出队中存储的表达式
	int m_i;//队的大小
	queue* gethead();//获得队头
	void EnQueue(float a);//float数据入队
	void EnQueue(char a);//char数据入队
	void EnQueue(queue a);//queue数据入队

	queue OutQueue();//出队
	Queue():head(NULL),rear(NULL),m_i(0){}//无赋值的构造函数
	Queue(int a)
	{//接受输入数据的构造函数
		char c;
		float number;
		head=rear=NULL;
		m_i=0;
		cout<<"请输入表达式,并以'#'号结束"<<endl;
		while(1){
			m_i++;
			cin>>c;
			if('0'<=c&&c<='9'){//对数字作出判断
				cin.putback(c);
				cin>>number;//接受数据
				EnQueue(number);
			}//if
			else if(c=='#') {EnQueue(c);break;}//结束
			else EnQueue(c);
		}//while
	}
};
template<class T>
class Stack
{//栈模板
private:
	T elem[50];//栈的存储空间
	int top;//栈首
public:
	Stack(){//对不同的T类型作出不同的初始化
		if(sizeof(T)==sizeof(char)) {top=0;elem[0]='#';}//若为字符栈,将'#'号压入
		else top=-1;
	}
	void twonum(float* ,float*);//获得数字栈栈顶的两个元素
	void pop();//弹栈
	void push(T a);//压栈
	T gettop();//获得栈首元素

};
Queue p;//存储后缀表达式的队列
Stack<float> num;//数字栈
Stack<char> oper;//运算符栈
Queue que(1);//存储中缀表达式的队列
/**********队列函数的实现部分************/
void Queue :: EnQueue(float a)
{
	if(!head)
		head=rear=new queue;
	else {
		rear->next=new queue;
		rear=rear->next;
	}
	rear->item.num=a;
	rear->sign=1;
	rear->next=NULL;
}
void Queue::EnQueue(char a)
{
	if(!head)
		head=rear=new queue;
	else {
		rear->next=new queue;
		rear=rear->next;
	}
	rear->item.oper=a;
	rear->sign=0;
	rear->next=NULL;
}
void Queue::EnQueue(queue a)
{
	if(!head)
		head=rear=new queue;
	else {
		rear->next=new queue;
		rear=rear->next;
	}
	if(a.sign){
		rear->item.num=a.item.num;
		rear->sign=1;
	}
	else {
		rear->item.oper=a.item.oper;
		rear->sign=0;
	}
	rear->next=NULL;
}
queue Queue::OutQueue()
{
	queue *p;

	if(!head) exit(0);
	p=head;
	head=head->next;
	return (*p);
}
queue* Queue::gethead()
{
	return head;	
}
void Queue::print()
{
	int i=0;
	for(i=0;i<m_i;i++){
		queue a=OutQueue();
		EnQueue(a);
		if(a.sign)
			cout<<a.item.num<<" ";
		else	cout<<a.item.oper<<" ";
	}
	cout<<endl;
}
/*********队列实现部分结束*************/

/********与中缀求值有关部分********/
bool Operator(char a,char b)
{//对运算符的优先次序作出判断
	int a_turn,b_turn;
	switch(a)//栈顶的运算符
	{
	 case '+':
	 case '-':a_turn=1;break;
	 case '*':
	 case '/':a_turn=2;break;
	 case '(':a_turn=0;break;
	 case '#':a_turn=-1;break;
	}
	switch(b)//当前的运算符
	{
	 case '+':
	 case '-':b_turn=1;break;
	 case '*':
	 case '/':b_turn=2;break;
	 case '(':b_turn=3;break;
	 case ')':b_turn=0;break;
	 case '#':b_turn=-2;break;
	}
	return a_turn>=b_turn;
}
void Dovalue(Stack<float> *num,Stack<char> *oper,char c)
{
	bool sign;
	float num1,num2;
	while(sign){
		sign=Operator(oper->gettop(),c);
		if(sign){
			if(oper->gettop()=='#') return;
			switch(oper->gettop())
			{
			case '+':num->twonum(&num1,&num2);num->push(num1+num2);break;//获得数据栈顶的两个数据,计算并压入栈
			case '-':num->twonum(&num1,&num2);num->push(num2-num1);break;
			case '*':num->twonum(&num1,&num2);num->push(num1*num2);break;
			case '/':num->twonum(&num1,&num2);
					 if(!num1) {
						 cout<<"除数为零,出错!"<<endl;//对除数为零作出处理
						 exit(0);
					 }
					 num->push(num2/num1);break;
			case '(':oper->pop();return;
			}
			p.EnQueue(oper->gettop());p.m_i++;//将栈顶运算符存入后缀表达式的队列中
			oper->pop();//弹出运算符栈栈顶元素
			
		}//if
		else oper->push(c);//当前运算符级别晓,压入运算符栈
	}//while
}
/*******中缀求值部分结束*********/

/**********8栈模板的实现部分*******/
template<class T>
void Stack<T>::pop()
{
	if(top==-1)
		return;
	else top--;
}

template<class T>
void Stack<T>::push(T a)
{
	elem[++top]=a;
	return;
}

template<class T>
T Stack<T> :: gettop()
{
	if(top==-1) return 0;
	else
		return elem[top];
}

template<class T>
void Stack<T>::twonum(float *num1,float *num2)
{
	*num1=gettop();
	pop();
	*num2=gettop();
	pop();
	return;
}
/*********栈模板实现部分结束*************/
void main()
{
	int i=0;
	do{//中缀表达式求值
		queue a;
		a=que.OutQueue();
		que.EnQueue(a);//保证求值结束后中缀表达式不变
		if(a.sign){
			p.EnQueue(a);p.m_i++;//将数据存入后缀表达式的队列中
			num.push(a.item.num);//将数据压入数据栈中
		}
		else Dovalue(&num,&oper,a.item.oper);//遇到运算符,进行计算
		i++;
	}while(i<que.m_i);
	cout<<"中缀求值为:"num.gettop()<<endl;
	cout<<"后序表达式为:"<<endl;
	p.print();//输出后缀表达式
	Stack<float> q;
	for(i=0;i<p.m_i;i++){//后缀求值
		queue a=p.OutQueue();
		
		if(a.sign){
			p.EnQueue(a);
			q.push(a.item.num);//数字压栈
		}
		else{
			float num1,num2;
			switch(a.item.oper)//遇到运算符,计算
			{
			case '+':q.twonum(&num1,&num2);q.push(num1+num2);break;
			case '-':q.twonum(&num1,&num2);q.push(num2-num1);break;
			case '*':q.twonum(&num1,&num2);q.push(num1*num2);break;
			case '/':q.twonum(&num1,&num2);q.push(num2/num1);break;
			}
		}
	}//for
	cout<<"后缀求值为:"<<q.gettop()<<endl;//输出后缀所求值
}