二叉树应用——计算表达式

由于时间比较匆忙，只实现了计算单个数字的，计算有十位或者更高位的还没去实现，之前用栈做的就可以，这里用二叉树做的，一开始把数据定为char类型，所以后来也就没去改它，就先实现了只有个位数的情况下的表达式的计算，更高位的表达式的计算，就是将数据的类型定位string类型，然后在数字组装和压栈的时候改些东西就好，这次由于重点是通过输入一个表达式，并建立起相对应的表达树，所以那里不想去深究。下面是代码，运算符号的优先级的判断，是用了栈的的结构特点，下一篇日记会贴出，只有栈和数组实现的表达式的计算，那个可以计算高位。

文件“tree.h”

#include<iostream>
#include<string>
#include<ctype.h>
using namespace std;

template<class T>
class My_stack;

template<class T>
class Node		//结点类
{
private:
	T data;
	Node<T> *next;
public:
	Node()
	{
		next=NULL;
	}
	Node(T d)
	{
		data=d;
		next=NULL;
	}
	friend My_stack<T>;
};

template<class T>
class My_stack
{
private:
	Node<T> *head;
public:
	My_stack()
	{
		head=new Node<T>();
	}
	
	~My_stack()
	{
		clean();
		delete head;
	}

	bool empty() const
	{
		return (head->next==0);
	}

	int size() const
	{
		int length=0;
		Node<T> *p=head->next;
		while(p)
		{
			length++;
			p=p->next;
		}
		return length;
	}

	void push(T d)	//入栈
	{
		Node<T> *p=new Node<T>(d);
		p->next=head->next;
		head->next=p;
	}

	T top()	//返回栈顶元素
	{
		if(empty())
		{
			cout<<"stack is empty."<<endl;
			exit(1);
		}
		Node<T> *p=head->next;
		T temp=p->data;
		return temp;
	}

	void pop()	//弹出栈顶元素
	{
		Node<T> *p=head->next;
		head->next=p->next;
		delete p;
	}

	void clean()	//清除整个栈
	{
		Node<T> *p=head->next;
		while(p)
		{
			head->next=p->next;
			delete p;
			head->next=p;
		}
	}
};

class BinTree;

class BinNode 
{
private:
	char data;
	BinNode *lchild;
	BinNode *rchild;
	friend BinTree;
};

class BinTree
{
private:
	BinNode *root;
	int pos;
	char str[255];
public:
	BinTree()
	{
		root=0;
		pos=0;
		str[0]='\0';
	}

	BinNode *Get_Root()
	{
		return root;
	}

	char *Get_str()
	{
		str[pos]='\0';
		return str;
	}

	void Create_Expression_Tree(BinNode *&r)	//建表达树
	{
		My_stack<char> digit;//暂存数字
		My_stack<char> opetor;//暂存操作符
		My_stack<BinNode *> node;//暂存结点
		
		char str[255];
		cout<<"输入表达式：";
		cin>>str;
		int i=0;
		char a,b;
		BinNode *p1,*p2,*p3;

		while(str[i]!='\0')
		{
			if(isdigit(str[i]))
			{
				digit.push(str[i]);
			}
			else
			{
				switch(str[i])
				{
				case '(': opetor.push(str[i]); break;
				case '*':
				case '/':
					if( !opetor.empty() && ( opetor.top()=='*' || opetor.top()=='/' ) )
					{
						p1=new BinNode;
						if(!opetor.empty())
						{
							p1->data=opetor.top();
							opetor.pop();
						}
						else
							cout<<"operator stack is empty"<<endl;
						if(!digit.empty()) //当数字栈中还有数字时
						{
							a=digit.top();
							digit.pop();
							p2=new BinNode;
							p2->data=a;
							p2->lchild=p2->rchild=0;
							if(!digit.empty())
							{
								b=digit.top();
								digit.pop();
								p3=new BinNode;
								p3->data=b;
								p3->lchild=p3->rchild=0;
								p1->lchild=p3;
								p1->rchild=p2;
							}
							else
							{
								if(!node.empty())
								{
									p3=new BinNode;
									p3=node.top();
									node.pop();
								}
								p1->lchild=p3;
								p1->rchild=p2;
							}
							node.push(p1);
						}
						else//当数字栈为空时，运算符号是作为两个式子运算结果的运算
						{
							p2=node.top();
							node.pop();
							p3=node.top();
							node.pop();
							p1->lchild=p3;
							p1->rchild=p2;
							node.push(p1);
						}
						opetor.push(str[i]);
					}
					else
						opetor.push(str[i]);
					break;
				case '+':
				case '-':
					while( (!opetor.empty()) && (opetor.top()!='(') )//加减的运算优先级最低，在他之前的所以运算符号都要出栈
					{
						p1=new BinNode;
						p1->data=opetor.top();
						opetor.pop();
						if(!digit.empty())
						{
							a=digit.top();
							digit.pop();
							p2=new BinNode;
							p2->data=a;
							p2->lchild=p2->rchild=0;
							if( !digit.empty() )
							{
								b=digit.top();
								digit.pop();
								p3=new BinNode;
								p3->data=b;
								p3->lchild=p3->rchild=0;
								p1->lchild=p3;
								p1->rchild=p2;
							}
							else
							{
								if(!node.empty())
								{
									p3=new BinNode;
									p3=node.top();
									node.pop();
								}
								p1->lchild=p3;
								p1->rchild=p2;
							}
							node.push(p1);
						}
						else
						{
							p2=node.top();
							node.pop();
							p3=node.top();
							node.pop();
							p1->lchild=p3;
							p1->rchild=p2;
							node.push(p1);
						}
					}
					opetor.push(str[i]);
					break;
				case ')':
					while( !opetor.empty() && opetor.top()!='(' )
					{
						p1=new BinNode;
						p1->data=opetor.top();
						opetor.pop();
						if(!digit.empty())
						{
							a=digit.top();
							digit.pop();
							p2=new BinNode;
							p2->data=a;
							p2->lchild=p2->rchild=0;
							if(!digit.empty())
							{
								b=digit.top();
								digit.pop();
								p3=new BinNode;
								p3->data=b;
								p3->lchild=p3->rchild=0;
								p1->lchild=p3;
								p1->rchild=p2;
							}
							else
							{
								if(!node.empty())
								{
									p3=new BinNode;
									p3=node.top();
									node.pop();
								}
								p1->lchild=p3;
								p1->rchild=p2;
							}
							node.push(p1);
						}
					}
					if(!opetor.empty())
						opetor.pop();
				}
			}
			i++;
		}
		while(!opetor.empty()) //表达式扫描完以后，将剩下的运算符号栈的元素，一一取出作为双亲结点进行继续建树
		{
			p1=new BinNode;
			p1->data=opetor.top();
			opetor.pop();
			if(!digit.empty())
			{
				a=digit.top();
				digit.pop();
				p2=new BinNode;
				p2->data=a;
				p2->lchild=p2->rchild=0;
				if(!digit.empty())
				{
					b=digit.top();
					digit.pop();
					p3=new BinNode;
					p3->data=b;
					p3->lchild=p3->rchild=0;
					p1->lchild=p3;
					p1->rchild=p2;
					node.push(p1);
				}
				else
				{
					if(!node.empty())
					{
						p3=new BinNode;
						p3=node.top();
						node.pop();
					}
					p1->lchild=p3;
					p1->rchild=p2;
					node.push(p1);
				}
			}
			else
			{			
				p2=new BinNode;
				p3=new BinNode;
				p2=node.top();
				node.pop();
				p3=node.top();
				node.pop();
				p1->lchild=p3;
				p1->rchild=p2;
				r=p1;
			}	
		}
		if(node.size()==1)//运算符号栈为空后，如果node栈只剩下一个元素，那么它就是根节点
		{
			r=node.top();
			node.pop();
		}
		root=r;
		cout<<"建树完成"<<endl;
	}

	void PostOrder_Traverse(BinNode *p)  //将中缀表达式转为后缀表达式
	{
		if(p)
		{
			PostOrder_Traverse(p->lchild);
			PostOrder_Traverse(p->rchild);
			str[pos]=p->data;
			pos++;
		}
	}
	
	void Count(char *str)
	{
		My_stack<int> s;//暂存中间结果
		cout<<"__计算表达式__"<<endl;
		int i=0,a,b;
		while(str[i]!='\0')
		{
			if(isdigit(str[i]))
			{
				int q=str[i]-'0';
				s.push(q);
			}
			else
			{
				switch(str[i])
				{
				case '+':
					if(!s.empty())
					{
						a=s.top();
						s.pop();
						b=s.top();
						s.pop();
						a=a+b;
						s.push(a);
					}
					break;
				case '-':
					if(!s.empty())
					{
						a=s.top();
						s.pop();
						b=s.top();
						s.pop();
						a=b-a;
						s.push(a);
					}
					break;
				case '*':
					if(!s.empty())
					{
						a=s.top();
						s.pop();
						b=s.top();
						s.pop();
						a=a*b;
						s.push(a);
					}
					break;
				case '/':
					if(!s.empty())
					{
						a=s.top();
						s.pop();
						b=s.top();
						s.pop();
						a=b/a;
						s.push(a);
					}
				}//end_switch
			}//end_else
			i++;
		}//end_while
		a=s.top();
		s.pop();
		cout<<"计算结果为："<<a<<endl;
	}

};

测试函数"main.cpp"

#include"tree.h"

int main()
{
	BinNode *root;
	BinTree tree;

	root=tree.Get_Root();
	tree.Create_Expression_Tree(root);

	char *str;
	tree.PostOrder_Traverse(root);

	str=tree.Get_str();
	int i=0;
	while(str[i]!='\0')
	{
		cout<<str[i]<<' ';
		i++;
	}
	cout<<endl;
	
	tree.Count(str);

	return 0;
}

输入 6+5*9-7/(3+4)

生成的二叉树如下所示：

输出结果：

输入表达式：6+5*9-7/(3+4)
建树完成
5 9 * 6 + 3 4 + 7 / -
__计算表达式__
计算结果为：50
Press any key to continue

最近也领悟到，当你调试一段比较长的代码时，如果你静下心来，你会发现，你为了跟踪某一段代码，可以想出很多很奇怪又很简单的方法，当错误都清理完后，那种成就感也是不言而喻的