那个, 原创文章, 转载请注明出处噢...

最近在实现<<数据结构与算法>>课程的一些基础算法, 然后我这次做的是和"树"(Tree)有关的专题, 碰到一个个人觉得有点难以理解的问题, 那就是计算器问题. 题目是这么说的:

利用逆波兰表达式求一个四则混合元算的值。

具体要求:

  1. 定义二叉树的型BTREE和位置的型position。

  2. 实现二叉树的基本操作。

  3. 实现将一个四则混合运算转换成二叉树的函数:BTREE convert(char *express),其中参数express为四则混合运算表达式,返回值为生成的树。

  4. 实现计算四则混合运算的值的函数:double computer(BTREE bt),其中,参数bt为四则运算所对应的树,返回值为计算结果。提示:先求树的的波兰表达式,然后利用栈结构计算表达式的值。

在主函数中进行测试,求2+3*(5+8)/4-5的值。


当时看到这个题的时候, 我有点懵逼(毕竟我也确实很菜, 脑子转不动), 就上网查了一下, 网上看到的方法挺统一的, 大概就是用了两个栈, 一个栈用来存括号, 一个栈用来存算式里面的数字字符, 然后balabalabalabala叫你按照一个给你列得明明白白的规则来做, 就能通过那个栈做出波兰表达式或者逆波兰表达式.

至于其中的原理, 我看了一遍又一遍, 确实是有点不理解. 但是看着看着, 我确认了一点, 那就是这个栈是可以通过递归过程来实现的, 我画了几个图, 试着把原算式分割成一个又一个子问题, 发现上述教程里面栈的那些规则应该和我通过逻辑递归实现的效果是一模一样的, 所以我试着写了一个递归出来, 效果意外的很不错.

我先把原理说清楚吧:

原理

所以这个计算器的功能, 实际上是把原算式转换成二叉树, 再通过树构建前序表达式(波兰表达式)或者后序表达式(逆波兰表达式), 从而计算原算式的结果. 而为了建立这么一棵唯一的二叉树, 我们需要:

正向:

先去分析"原问题"(如图所示);

而要知道原问题, 我们就得知道"子问题1"得到的结果是什么;

而要知道"子问题1", 我们就需要知道"子问题2"的结果是什么;

而要知道"子问题2", 我们就需要知道"子问题3"的结果是什么;

而要知道"子问题3", 我们就需要知道"子问题4"的结果是什么;

而"子问题4"就是很简单的一个二叉树, 根节点为'+', 左孩子是'5', 右孩子是'8';

反向:

"子问题4"的结果得到了, 开始向上递归;

"子问题4"的结果向上返回到"子问题3", "子问题3"的结果就能知道了;

"子问题3"的结果向上返回到"子问题2", "子问题2"的结果就能知道了;

"子问题2"的结果向上返回到"子问题1", "子问题1"的结果就能知道了;

"子问题1"的结果向上返回到"原问题", "原问题"的结果就能知道了;

结果:

"原问题"的结果知道了, 那么这一整棵二叉树就建立完成了.


综上, 我们可以很轻松地发现, 建立二叉树的过程就是一个完美的递归过程, 而这个递归的逻辑顺序用递推的思路走一遍, 不出所料的话应该就是和用栈的那个方案建立二叉树的过程是完全一样的, 但是用递归来解的话思路相对来说会更清晰一些.

具体的实现细节我就通过贴代码和源码的方式来说吧, 看得懂的老板们自然看的很明白.

Calculator.h

#ifndef CALCULATOR_H
#define CALCULATOR_H
#include <iostream>
using namespace std;

class Calculator
{
private:
	struct celltype {
		char data;
		celltype* lchild, * rchild;
	};
	typedef celltype* binarytree;
	typedef celltype* treenode;
	binarytree btree;
	double result;

	int priority(char level);
	bool bracketMatch(char leftBracket, char rightBracket);
	bool isLeftBracket(char sth);
	bool isRightBracket(char sth);
	bool isOperator(char sth);
	bool isInteger(char sth);
	double sumResult(double left, char oprt, double right);

	string setPolandfx(treenode root);
	string setAntiPolandfx(treenode root);
	void inOrder(treenode root);

public:
	Calculator(char formula[], int len);

	treenode buildTree(char formula[], int st, int ed);
	double calculate();

	string setPolandfx();
	string setAntiPolandfx();
	void inOrder();
};

#endif

Calculator.cpp

#include "Calculator.h"
#include <stack>
using namespace std;

Calculator::Calculator(char formula[], int len) {
	btree = buildTree(formula, 0, len - 1);
}

Calculator::treenode Calculator::buildTree(char formula[], int st, int ed) {
	/*
	cout << "_____接受递归数据_____\n";
	cout << "测试st: " << st << endl;
	cout << "测试ed: " << ed << endl << endl << endl;
	*/
	//只有一个字符的情况, 直接返回叶节点
	treenode root = new celltype;
	if (st == ed) {
		root->data = formula[st];
		root->lchild = NULL;
		root->rchild = NULL;
		return root;
	}
	int left_st = -1, left_ed = -1, right_st = -1, right_ed = -1, min_priority = 100;
	stack<char> brackets;
	for (int i = st; i <= ed; i++) {
		if (isLeftBracket(formula[i])) brackets.push(formula[i]);
		if (!brackets.empty() && bracketMatch(brackets.top(), formula[i])) brackets.pop();
		if (brackets.empty() && min_priority > priority(formula[i])) {
			//cout << "触及赋值语句\n\n\n";
			min_priority = priority(formula[i]);
			root->data = formula[i];
			left_st = st;
			left_ed = i - 1;
			right_st = i + 1;
			right_ed = ed;
		}
	}
	//特殊情况: 括号保住整个表达式且其内部无括号, 则会导致上述index数据值全部为-1(未被修改过)
	//这种特殊情况发生时, 通过修正st和ed可以实质性解决问题, 但是需要多算一步, 总体上对复杂度没有影响
	if (left_st == -1 && left_ed == -1 && right_st == -1 && right_ed == -1 && bracketMatch(formula[st], formula[ed])) {
		st++;
		ed--;
		return buildTree(formula, st, ed);
	}
	else {
		/*
		cout << "_____开始递归到下一层_____\n";
		cout << "测试left_st: " << left_st << endl;
		cout << "测试left_ed: " << left_ed << endl;
		cout << "测试right_st: " << right_st << endl;
		cout << "测试right_ed: " << right_ed << endl << endl << endl;
		*/
		root->lchild = buildTree(formula, left_st, left_ed);
		root->rchild = buildTree(formula, right_st, right_ed);
	}
	return root;
}
double Calculator::calculate() {
	result = 0;
	string polandfx = setPolandfx(btree);
	int polandfx_len = polandfx.length();
	for (int i = 0; i < polandfx_len - 2; i++) {
		if (isOperator(polandfx[i]) && isInteger(polandfx[i + 1]) && isInteger(polandfx[i + 2])) {
			result = sumResult((polandfx[i + 1] - '0'), polandfx[i], (polandfx[i + 2] - '0'));
			//cout << "测试result状态: " << result << endl;
			polandfx[i] = 'x';
			for (int j = 1; j < (polandfx_len-i-2) ; j++) polandfx[i + j] = polandfx[i + j + 2];
			polandfx_len -= 2;
			i = 0;
			/*
			cout << "测试波兰表达式状态: ";
			for (int k = 0; k < polandfx_len; k++) cout << polandfx[k] << " ";
			cout << endl;
			cout << "波兰表达式长度: " << polandfx_len << endl;
			*/
		}
	}
	//最后只剩三位的时候会跳出循环, 此时只需要做最后一次计算即可
	result = sumResult((polandfx[1] - '0'), polandfx[0], (polandfx[2] - '0'));
	return result;
}
double Calculator::sumResult(double left, char oprt, double right) {
	//如果数字是'x'(72)的话, 要把值换成result值
	if (left == 72) left = result;
	if (right == 72) right = result;
	//cout << "检测算式: " << left << " " << oprt << " " << right << endl << endl << endl;
	switch (oprt)
	{
	case '+':
		return (left + right);
	case '-':
		return (left - right);
	case '*':
		return (left * right);
	case '/':
		return (left / right);
	default:
		return NULL;
	}
}

int Calculator::priority(char level) {
	switch (level) {
	default:
		return 1024;
	case '+':
		return 1;
	case '-':
		return 2;
	case '*':
		return 3;
	case '/':
		return 4;
	}
	return 0;
}
bool Calculator::bracketMatch(char leftBracket, char rightBracket) {
	if ('(' == leftBracket && ')' == rightBracket) return true;
	if ('[' == leftBracket && ']' == rightBracket) return true;
	if ('{' == leftBracket && '}' == rightBracket) return true;
	return false;
}
bool Calculator::isLeftBracket(char sth) {
	return ('(' == sth || '[' == sth || '{' == sth);
}
bool Calculator::isRightBracket(char sth) {
	return (')' == sth || ']' == sth || ']' == sth);
}
bool Calculator::isOperator(char sth) {
	return ('+' == sth || '-' == sth || '*' == sth || '/' == sth);
}
bool Calculator::isInteger(char sth) {
	int num = sth - '0';
	return (num >= 0 && num <= 9 || sth == 'x');
}

void Calculator::inOrder() {
	return inOrder(btree);
}
void Calculator::inOrder(treenode root) {
	if (root->lchild != NULL) inOrder(root->lchild);
	cout << root->data << " ";
	if (root->rchild != NULL) inOrder(root->rchild);
}
string Calculator::setPolandfx() {
	return setPolandfx(btree);
}
string Calculator::setPolandfx(treenode root) {
	string polandfx = "";
	polandfx += root->data;
	if (root->lchild != NULL) polandfx += setPolandfx(root->lchild);
	if (root->rchild != NULL) polandfx += setPolandfx(root->rchild);
	return polandfx;
}
string Calculator::setAntiPolandfx() {
	return setAntiPolandfx(btree);
}
string Calculator::setAntiPolandfx(treenode root) {
	string antiPolandfx = "";
	if (root->lchild != NULL) antiPolandfx += setAntiPolandfx(root->lchild);
	if (root->rchild != NULL) antiPolandfx += setAntiPolandfx(root->rchild);
	antiPolandfx += root->data;
	return antiPolandfx;
}

main.cpp

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

int main() {
	cout << "\n\n__________题目5__________\n";
	char formula[] = "2+3*(5+8)/4-5";
	cout << "原算式为: " << formula << endl;
	int formula_len = 13;
	Calculator calculator = Calculator(formula, formula_len);
	cout << "导入到类内后, 类内二叉树中序遍历测试: ";
	calculator.inOrder();
	cout << endl;
	cout << "所得波兰表达式: " << calculator.setPolandfx() << endl;
	cout << "所得逆波兰表达式: " << calculator.setAntiPolandfx() << endl;
	cout << "根据波兰表达式, 计算结果为: " << calculator.calculate() << endl;
}

一般来说在下的垃圾代码大家应该能一眼看明白的, 看明白了的老板请忽略接下来的补充内容.


关键代码段说明:

几个蜜汁函数:

/*
返回某个运算符的优先级. 我的设定目前只有 '+', '-', '*', '/' 四种运算符, 其中他们的优先级从左到右依次为'+': 1, '-': 2, '*': 3, '/': 4. 如果未来还想加入更多运算符并定义优先级, 可以直接在里面加.
*/
int priority(char level);



/*
用来匹配括号的函数. 当检测的两个字符分别为'('和')', 或者 '['和']', 或者 '{'和'}'时, 就会返回true. 当然, 你要有更多想要匹配的括号, 也可以加到这个函数里面去.
*/
bool bracketMatch(char leftBracket, char rightBracket);


/*
isInteger用来判断该字符是不是'0'-'9'的字符, 如果是就输出true
sumResult用来计算result的值

当然, isInteger那个'x'的部分和sumResult那个72 == left的部分你可能会有点懵逼, 我要解释一下. 那个72其实是'x'对应的ASCII码. 因为之后通过波兰表达式计算原式值的时候, 字符串内某些位置在计算时是需要发生改变的, 比如字符串读到"+58"的时候, 我们就应该知道我们需要把"+58"直接改写成'13'. 这就造成了一个问题, '13'这个字符在cout输出的时候并不是表示为'13'的, 而原来的字符串内"+58"的部分又必须要用'13'直接替代, 怎么办呢?

我想了一个办法, 我把超出'9'的用数字表示的字符用'x'表示, 而字符串一旦读取到'x', 就会默认它是一个"数字". 至于数字的值, 在我的类里面就是对应result的数值, 这样子原来的算式字符串就会按照算法越缩越短, 且result的值也逐渐能变化成最终答案了.
*/
bool isInteger(char sth);
double sumResult(double left, char oprt, double right);

那个递归函数:

/*
思路: 
1. 遍历整个算式, 找到优先级最低的且不在括号里面的那个运算符('+'或'-'), 通过这个运算符把树结点, 左子树, 右子树构建出来, 当然, 左子树或者右子树是通过递归求解"子问题"得到的

2. 如何确认遍历满足条件的时候, int游标所指位置在括号外部呢?
这就需要我们使用stack来存储括号了. 如果你学过符号匹配器的话, 你理解这个就会轻松很多.
当括号栈栈顶元素和读取的字符刚好能匹配(bracketMatch)的时候, 就pop栈顶元素.
只有当栈完全为空的时候, 才说明"游标所指即是括号外"

3. 有个特殊的括号问题, 那就是扫描字符串 (5 + 8) 和 (5) + (8) 的时候, 游标所指会一直在括号内, 这可怎么办呢? 通过测试buildTree这个函数我们可以知道, 当这种情况发生时, 即使for走完, left_st = -1, left_ed = -1, right_st = -1, right_ed = -1的值都没有被刷新过, 一直是之前赋予的初值-1.
所以说, 只要"上述的几个变量一直没有变值"这种情况发生, 说明字符串的情况是(5 + 8)而绝无可能是(5) + (8), 这个时候只需要修正st和ed的位置就能继续正常递归了
*/
Calculator::treenode Calculator::buildTree(char formula[], int st, int ed) {
	/*
	cout << "_____接受递归数据_____\n";
	cout << "测试st: " << st << endl;
	cout << "测试ed: " << ed << endl << endl << endl;
	*/
	//只有一个字符的情况, 直接返回叶节点
	treenode root = new celltype;
	if (st == ed) {
		root->data = formula[st];
		root->lchild = NULL;
		root->rchild = NULL;
		return root;
	}
	int left_st = -1, left_ed = -1, right_st = -1, right_ed = -1, min_priority = 100;
	stack<char> brackets;
	for (int i = st; i <= ed; i++) {
		if (isLeftBracket(formula[i])) brackets.push(formula[i]);
		if (!brackets.empty() && bracketMatch(brackets.top(), formula[i])) brackets.pop();
		if (brackets.empty() && min_priority > priority(formula[i])) {
			//cout << "触及赋值语句\n\n\n";
			min_priority = priority(formula[i]);
			root->data = formula[i];
			left_st = st;
			left_ed = i - 1;
			right_st = i + 1;
			right_ed = ed;
		}
	}
	//特殊情况: 括号保住整个表达式且其内部无括号, 则会导致上述index数据值全部为-1(未被修改过)
	//这种特殊情况发生时, 通过修正st和ed可以实质性解决问题, 但是需要多算一步, 总体上对复杂度没有影响
	if (left_st == -1 && left_ed == -1 && right_st == -1 && right_ed == -1 && bracketMatch(formula[st], formula[ed])) {
		st++;
		ed--;
		return buildTree(formula, st, ed);
	}
	else {
		/*
		cout << "_____开始递归到下一层_____\n";
		cout << "测试left_st: " << left_st << endl;
		cout << "测试left_ed: " << left_ed << endl;
		cout << "测试right_st: " << right_st << endl;
		cout << "测试right_ed: " << right_ed << endl << endl << endl;
		*/
		root->lchild = buildTree(formula, left_st, left_ed);
		root->rchild = buildTree(formula, right_st, right_ed);
	}
	return root;
}

树建完以后, 计算结果result的部分:

/*
当原算式转换成唯一的二叉树以后, 通过原二叉树的先序输出(波兰表达式)或者后续输出(逆波兰表达式)字符串, 是可以直接计算结果的.
方法: 
1. 对于波兰表达式, 使用遍历操作, 例如本题原式"2 + 3 * (5 + 8) / 4 - 5"的波兰表达式输出结果为: "+ 2 - * 3 / + 5 8 4 5". 我们只需要做一遍字符串扫描, 当扫描的游标读取到"+58"这三个连续字符时, 就直接把"+58"的结果更新为计算结果'13'(当然, 这里我们需要用'x'代替, 原因之前已经讲过了)
2. 这样做完以后, 之前的字符串就会变成: "2 - * 3 / x 4 5", 其中'x'代表result的值('13')
3. 重新扫描新的字符串. 当扫描到"/x5"时, 计算条件满足, 直接把"/x4"的结果更新为计算结果13 / 4 = 3.25
4. 这样做完以后, 之前的字符串就会变成: "2 - * 3 x 5", 其中'x'代表result的值('3.25')
5. 重新扫描新的字符串. 当扫描到"*3x"时, 计算条件满足, 直接把"*3x"的结果更新为计算结果3 * 3.25 = 9.75
6. 相信你做了1 ~ 5这几个步骤以后应该知道接下来的操作是什么了吧, 把2, 3, 4, 5步骤照葫芦画瓢就好了, 最终的result就是这么算出来的
*/
double Calculator::calculate() {
	result = 0;
	string polandfx = setPolandfx(btree);
	int polandfx_len = polandfx.length();
	for (int i = 0; i < polandfx_len - 2; i++) {
		if (isOperator(polandfx[i]) && isInteger(polandfx[i + 1]) && isInteger(polandfx[i + 2])) {
			result = sumResult((polandfx[i + 1] - '0'), polandfx[i], (polandfx[i + 2] - '0'));
			//cout << "测试result状态: " << result << endl;
			polandfx[i] = 'x';
			for (int j = 1; j < (polandfx_len-i-2) ; j++) polandfx[i + j] = polandfx[i + j + 2];
			polandfx_len -= 2;
			i = 0;
			/*
			cout << "测试波兰表达式状态: ";
			for (int k = 0; k < polandfx_len; k++) cout << polandfx[k] << " ";
			cout << endl;
			cout << "波兰表达式长度: " << polandfx_len << endl;
			*/
		}
	}
	//最后只剩三位的时候会跳出循环, 此时只需要做最后一次计算即可
	result = sumResult((polandfx[1] - '0'), polandfx[0], (polandfx[2] - '0'));
	return result;
}

从大体上来说, 这个方案其实很好想到, 在思路上是没有什么困难的, 除了实现的时候可能有些细节需要注意一下. 这个算法和传统算法唯一的不同之处就在于它在思路上面比使用栈的方式更具有逻辑性.

我后来查了一下, 刘汝佳老师的<<算法竞赛指南>>里面有相关内容, 所用方法也是递归, 我想的方法和书上的解法是大致相同的, 如果你看不懂我的算法, 看那本书上的详细讲解, 效果应该更好.

好了完.