tree.cpp

表达式计算的代码 C C 表达式计算 字符串计算

// Tree.cpp: implementation of the Tree class.
//
//////////////////////////////////////////////////////////////////////

#include "Tree.h"
#include <iostream>
#include <stdlib.h>
#include<stdio.h>
#include <stack>
using namespace std;
//////////////////////////////////////////////////////////////////////
// 构造函数/析构构函数
//////////////////////////////////////////////////////////////////////
Tree::Tree()
{
  this->root =NULL;
}
Tree::~Tree()
{
}
//前序遍历
void Tree::preOrder(Node *localRoot)
{
	if(localRoot!=NULL)
	{
		cout<<localRoot->data<<"";//访问根节点
		preOrder(localRoot->leftChild);//遍历左子树
		preOrder(localRoot->rightChild);//遍历右子树
	}
}
//中序遍历
void Tree::inOrder(Node *localRoot)
{
     if(NULL!=localRoot)
	 {
		 inOrder(localRoot->leftChild);//遍历左子树
		 cout<<localRoot->data<<"";//访问根结点
		 inOrder(localRoot->rightChild );//遍历右子树
	 }
}
//后序遍历
void Tree::postOrder(Node *localRoot)
{
     if(NULL!=localRoot)
	 {
		 postOrder(localRoot->leftChild );//遍历左子树
		 postOrder(localRoot->rightChild );//遍历右子树
		 cout<<localRoot->data <<"";//访问根结点
	 }
}
//取结点值
double Tree::getValue(Node *node)
{
	//如果结点为数据直接返回
	if(node->kind==NUMBER)
	{
       return node->data ;
	}
	else
	{
		//否则kind一定是操作符类型,那么就开始计算
		double leftValue=this->getValue(node->leftChild);//取结点的左值
		double rightValue=this->getValue(node->rightChild);//取结点的右值
		switch(node->oper) 
		{
		case '+'://加法操作
			return leftValue+rightValue; 
		case '-'://减法操作
			return leftValue-rightValue;
		case '*'://乘法操作
			return leftValue*rightValue;
		case '/'://除法操作
			if(rightValue==0)
			{
			   cout<<"零不能为除数!"<<endl;
               return -1;  
			}
			else
			{
				return leftValue/rightValue;
			}
		default://错误处理
			return -1;
		}
	}
}
//最终结果
double Tree::getResult()
{
	return this->getValue(this->root);
}
//显示节点
void Tree::displayNode(Node *temp)
{
   if(temp->kind==NUMBER)
	   cout<<temp->data;//输出数据
   else
	   cout<<temp->oper ;//输出操作符
}
//显示树
void Tree::displayTree()
{
   stack<Node*> globalStack;//全局堆栈
   globalStack.empty();//清空
   globalStack.push(this->root);//将根节点放入
   int blanks=32;//空格数
   bool rowEmpty=false;//空行标识
   cout << ".........................................................." << endl;
   while(!rowEmpty)
   {
	   //本地堆栈,存放孩子节点信息.最后放入globalStack中
	   stack<Node *> localStack;
	   rowEmpty=true;
	   //先打印空格,如果是根节点,打印32个空格
	   for(int j=0; j<blanks; j++)
		  cout << ' ';
       //当全局堆栈不为空时
	   while(globalStack.size()!=0)
	   {
		  //取出全局堆栈中节点,放入temp中
		  Node *temp = globalStack.top();
		  globalStack.pop();
		  //当temp不为空时，打印节点信息,并把左右节点存入地方堆栈中
		  //注意,这里左右孩子有可能为NULL
		  if(NULL!=temp)
		  {
			  this->displayNode(temp);
			  localStack.push(temp->leftChild);//左孩子进栈
			  localStack.push(temp->rightChild);//右孩子进栈
			  //当左右节点至少有一个有数据时,rowEmpty就设为假
			  if(NULL!=temp->leftChild||NULL!=temp->rightChild)
			  {
                  rowEmpty=false;
			  }
		  }
		  else
		  {
			  //如果节点为假,即没有该孩子,则打印"--",并将左右孩子存为NULL
			  cout<<"--";
			  localStack.push(NULL);//空左孩子进栈
			  localStack.push(NULL);//空右孩子进栈
		  }
		  for(int j=0; j<blanks*2-2; j++)
              cout <<' ';
	   }
	   cout<<endl;
	   blanks /= 2;
       while(localStack.size()!=0)
	   {
          globalStack.push( localStack.top() );
	      localStack.pop();
	   }
   }
   cout << ".........................................................." << endl;
}