c++实现表达式树

因为我不会模板，所以我写了两个stack，一个用来存表达式使其变为后缀，另一用来存Node节点使其变为一棵树，在写的过程中我一直在思考要不要写拷贝和移动构造，最后还是没有写。

1、下面是表达式中缀变后缀的栈的代码：

声明：

#pragma once
#include 

using namespace std;


class MyStack {
private:
	const int DEAFAULT_CAPACITY = 10;
	const int STACK_INCREMENT = 2;
	int* base;
	int* top;
	int stackSize;
	int maxCapacity = 0;
public:
	MyStack();
	MyStack(initializer_list list);  
	MyStack(MyStack& stack);
	MyStack(MyStack&& stack);
	~MyStack();
	int* begin();
	int* end();
	//入栈
	void push(int element);
	//退栈
	int pop();
	//得到栈顶元素
	int getTop();
	//清空
	void clear();
	//扩容操作
	void ensureCapacity(int newCapacity);
	int size();
};

定义：

#include 
#include "myStack.h"

using namespace std;

int* MyStack::begin() {
	return base;
}

int* MyStack::end() {
	return& base[stackSize];
}
MyStack::MyStack() {
	stackSize = 0;
	base = NULL;
	top = NULL;
}

MyStack::MyStack(initializer_list list)
	:base(new int[list.size()]), stackSize(list.size()), maxCapacity(list.size()) {
	copy(list.begin(), list.end(), base);
	top = &base[list.size() - 1];
}

MyStack::MyStack(MyStack& stack) {
	stackSize = stack.stackSize;
	maxCapacity = stack.maxCapacity;
	base = new int[maxCapacity];
	for (int i = 0; i < stackSize; i++) {
		base[i] = stack.base[i];
	}
	top = &base[stackSize];
}

MyStack::MyStack(MyStack&& stack) {
	this->base = stack.base;
	stack.base = NULL;
	this->top = stack.top;
	stack.top = NULL;
	this->stackSize = stack.stackSize;
	this->maxCapacity = stack.maxCapacity;
}


MyStack::~MyStack() {
	if (base != NULL) {
		delete[] base;
		base = NULL;
	}
	top = NULL;
}

//入栈
void MyStack::push(int element) {
	if (stackSize == 0) {
		ensureCapacity(DEAFAULT_CAPACITY);
	}
	if (maxCapacity == stackSize) {
		ensureCapacity(maxCapacity * STACK_INCREMENT + 1);
	}
	*top = element;
	top = &(base[++(stackSize)]);
}

//退栈
int MyStack::pop() {
	if (stackSize == 0) {
		return NULL;
	}
	top = &(base[--(stackSize)]);
	return *top;
}


//得到栈顶元素
int MyStack::getTop() {
	if (stackSize == 0) {
		return NULL;
	}
	return base[stackSize - 1];
}


//清空
void MyStack::clear() {
	top = &(base[(stackSize = 0)]);
}


//扩容操作
void MyStack::ensureCapacity(int newCapacity) {
	if (maxCapacity > newCapacity) {
		return;
	}
	if (newCapacity != DEAFAULT_CAPACITY) {
		int* old = base;
		base = new int[newCapacity];
		for (int i = 0; i < stackSize; i++) {
			base[i] = old[i];
		}
		delete[] old;
	}
	else {
		base = new int[newCapacity];
	}
	top = &(base[stackSize]);
	maxCapacity = newCapacity;
}

int MyStack::size() {
	return stackSize;
}

2、存Node节点，使其变为书的栈

在写这个栈的时候真是废了老大功夫，我想要建造一个数组来存放Node节点（类），但是我明白不能使用Node node 的方式来定义元素，我想了很久都不知道要怎么定义才好（其实还是c++中的可选择的方式太多，使得新手不知从何下手（比如指针，引用，和以定义基本数据类型变量的方式定义类变量））。突然我就想到了Java的存储方式。由于Java中只有引用，并且数组中保存的是保存在堆区对象的地址，所以我使用了保存指针的数组base和指向指针的指针（好吧，就像翁恺老师说的这有点绕口）top来表示数组和栈顶指针（栈顶指针总是指向头元素的下一个元素）。

其实我们的数据结构课是用jc语言描述的，但是我看的是java版的书，并且学习java的时候看过集合的底层，所以我采用了jdk8之后的底层数组自动扩容，和第一次push时创建底层数组的方式。

声明：

#pragma once
#include 
#include "Node.h"

using namespace std;


class ExpStack {
private:
	const int DEAFAULT_CAPACITY = 10;
	const int STACK_INCREMENT = 2;
	Node** base; // 一个数组数组里面全是指针
	Node** top = NULL; // top 表示指向的Node数组的地址  
	// *top表示指向的里面的值 **top 表示在堆区的一个Node
	int stackSize = 0;
	int maxCapacity = 10;
public:
	ExpStack();
	//ExpStack(initializer_list list);
	~ExpStack();
	//int* begin();
	//int* end();
	//入栈
	void push(Node* element);
	//退栈
	Node* pop();
	//得到栈顶元素
	Node* getTop();
	//清空
	void clear();
	//扩容操作
	void ensureCapacity(int newCapacity);
	int size();
};

定义：

#include "ExpStack.h"
#include 

using namespace std;

//int* ExpStack::begin() {
//	return base;
//}
//
//int* ExpStack::end() {
//	return&base[stackSize];
//}
ExpStack::ExpStack() {
	
}

//ExpStack::ExpStack(initializer_list list)
//	:base(new int[list.size()]), stackSize(list.size()), maxCapacity(list.size()) {
//	copy(list.begin(), list.end(), base);
//	top = &base[list.size() - 1];
//}

ExpStack::~ExpStack() {
	if (base != NULL) {
		for (int i = 0; i < stackSize; i++) {
			delete base[i];
			base[i] = NULL;
		}
		delete[] base;
		base = NULL;
	}
	top = NULL;
}

//入栈
void ExpStack::push(Node* element) {
	if (stackSize == 0) {
		ensureCapacity(DEAFAULT_CAPACITY);
	}
	if (maxCapacity == stackSize) {
		ensureCapacity(maxCapacity * STACK_INCREMENT + 1);
	}
	*top = element;
	top = &base[++(stackSize)];
}

//退栈
Node* ExpStack::pop() {
	if (stackSize == 0) {
		return NULL;
	}
	top = &base[--(stackSize)];
	Node* node = *top;
	//char ch = ((Node*)*top)->ch;
	*top = NULL;
	return node;
}



//得到栈顶元素
Node* ExpStack::getTop() {
	if (stackSize == 0) {
		return NULL;
	}
	return base[stackSize - 1];
}


//清空
void ExpStack::clear() {
	for (int i = 0; i < stackSize; i++) {
		delete base[i];
		base[i] = NULL;
	}
	top = &base[(stackSize = 0)];
}


//扩容操作
void ExpStack::ensureCapacity(int newCapacity) {
	if (maxCapacity > newCapacity) {
		return;
	}
	if (newCapacity != DEAFAULT_CAPACITY) {
		Node** old = base;
		base = new Node*[newCapacity];
		for (int i = 0; i < stackSize; i++) {
			base[i] = old[i];
			old[i] = NULL;
		}
		delete[] old;
	}
	else {
		base = new Node*[newCapacity];
	}
	top = &base[stackSize];
	maxCapacity = newCapacity;
}

int ExpStack::size() {
	return stackSize;
}

3、Node节点的声明和定义

声明：

我不会嵌套类，所以我把他单独拿出来了，不过说实话我还是对java的使用更加顺手。

#pragma once
#include 

using namespace std;

class Node {
public:
	char ch;
	Node* left;
	Node* right;
	Node();
	Node(char c = '', Node* l = NULL, Node* r = NULL);
	~Node() {}
};

定义：

其实完全没必要，但是我有强迫症，就多写了一个Node.cpp

#include "Node.h"
#include 

using namespace std;

Node::Node(char c, Node* l, Node* r)
	:ch(c), left(l), right(r) {}

4.表达式树ExpTree

声明：

#pragma once
#include 
#include "ExpStack.h"
#include "MyStack.h"
#include "Node.h"

using namespace std;

class ExpTree
{
private:
	ExpStack expStack;
	char* expression;
	int len;
	Node* root;

	char* infixTOsuffix(const char* exp);
	void print(Node* t, int h);
	void preTraverse(Node* t);
	void inTraverse(Node* t);
	void postTraverse(Node* t);
	void dostroy(Node* t);
public:
	ExpTree();
	ExpTree(const char* exp);
	~ExpTree();
	void creatTree(const char* exp);
	void print();
	void preTraverse();
	void inTraverse();
	void postTraverse();
};

定义：

#include 
#include "ExpTree.h"

using namespace std;

//private

char* ExpTree::infixTOsuffix(const char* exp) {
	MyStack myStack;
	int len = strlen(exp);
	char* ret = new char[len];
	int count = 0;
	for (int i = 0; exp[i] != '='; i++) {
		if (exp[i] == ' ')
			continue;
		else if (exp[i] >= '0' && exp[i] <= '9')
			ret[count++] = exp[i];
		else if ((exp[i] == '+' || exp[i] == '-')) {
			while (myStack.getTop() != NULL) {
				ret[count++] = myStack.pop();
			}
			myStack.push(exp[i]);
		}
		else if (myStack.getTop() != '/' && myStack.getTop() != '*')
			myStack.push(exp[i]);
		else if (myStack.getTop() == '/' && myStack.getTop() == '*'){
			//&& (exp[i] == '/' || exp[i] == '*')
			ret[count++] = myStack.pop();
			myStack.push(exp[i]);
		}
	}
	while (myStack.getTop() != NULL) {
		ret[count++] = myStack.pop();
	}
	ret[count] = '=';
	return ret;
}

void ExpTree::print(Node* t, int h) {
	if (t != NULL) {
		print(t->right, h + 1);
		for (int i = 0; i < h; i++) {
			cout << "     ";
		}
		cout << t->ch << endl;
		print(t->left, h + 1);
	}
}
void ExpTree::preTraverse(Node* node) {
	if (node == NULL)
		return;
	cout << node->ch << "  ";
	preTraverse(node->left);
	preTraverse(node->right);
}
void ExpTree::inTraverse(Node* node) {
	if (node == NULL)
		return;
	inTraverse(node->left);
	cout << node->ch << "  ";
	inTraverse(node->right);
}
void ExpTree::postTraverse(Node* node) {
	if (node == NULL)
		return;
	postTraverse(node->left);
	postTraverse(node->right);
	cout << node->ch << "  ";
}
void ExpTree::dostroy(Node* t) {
	if (t == NULL)
		return;
	dostroy(t->left);
	dostroy(t->right);
	delete t;
	t = NULL;
}

//public

ExpTree::ExpTree()
	:expression(NULL), len(0), root(NULL) {

}
ExpTree::ExpTree(const char* exp) {
	creatTree(exp);
}
ExpTree::~ExpTree() {
	dostroy(root);
}
//想要创建，那么expression必须是NULL
void ExpTree::creatTree(const char* exp) {
	dostroy(root);
	len = strlen(exp) + 1;//len 是字符串加结尾0的长度
	expression = new char[len];
	strcpy(expression, exp);
	char* suffix = infixTOsuffix(expression);
	for (int i = 0; suffix[i] != '='; i++) {
		if (suffix[i] >= '0' && suffix[i] <= '9')
			expStack.push(new Node(suffix[i]));
		else {
			Node* left = expStack.pop();
			Node* right = expStack.pop();
			Node* father = new Node(suffix[i]);
			father->left = left;
			father->right = right;
			expStack.push(father);
		}
	}
	delete[] suffix;
	root = expStack.pop();
}
void ExpTree::print() {
	print(root, 0);
}
void ExpTree::preTraverse() {
	preTraverse(root);
}
void ExpTree::inTraverse() {
	inTraverse(root);
}
void ExpTree::postTraverse() {
	postTraverse(root);
}

practice：

int main() {
	ExpTree tree("1+ 2*5 = ");
	tree.print();
	cout << endl;
	cout << endl;
	cout << endl;
	tree.creatTree("1 + 2 * 5 - 3 + 8 = ");
	tree.print();
	cout << endl;
	tree.postTraverse();
	cout << endl;
	tree.inTraverse();
	return 0;
}

输出：

可能会有bug，但是你知道我没有经过调试写完之后程序显示 (进程 6312)已退出，代码为 0。时我有多么激动吗！！！

c++实现表达式树

Java相关栏目本月热门文章