数据结构课程设计之表达式建树

题目描述

一个表达式和一棵二叉树之间存在着自然的对应关系。请设计一个程序，实现基于二叉树表示的算术表达式的相关操作。

功能要求及说明

假设算术表达式内可以含有变量(a~z)， 常量(0~9)和二元运算符(+.-*./)。要求实现以下的操作:
1.以字符序列的形式输入语法正确的前缀表达式，并构造表达式二叉树；
2.用中缀表达式的形式输出表达式(在必要的地方添加()以正确反映运算的优先次序);
3.若表达式中含有变量，实现对表达式中的变量分别赋值;
4.对算术表达式求值(用后根遍历的次序)，对含有变量的表达式，先对变量赋值，再计算表达式的值;
5.采用模块化设计，分别以函数形式描述上述各功能。

测试数据

(1)不含变量的测例:分别输入0; -52; + - 9*/62-754;并输出0; 5-2; 9-6/2*(7-5)+4:计算结果0; 3; 7。
(2)对含有变量的表达式测例:分别输入 a ; + a * b3；并输出a; a+b * 3;分别给观赋不同的值(如a=2,b=3),计算并输出表达式的值(2; 11)。
(3)其它测例自选。

建树

这里主要讲一下建树的思路，由于输入的数据是前缀表达式，即每个运算符号后跟着它的两个操作数，如：
                  + - 9 * /62-754
其表示的运算为：
                  9-6/2 * (7-5)+4


观察前缀表达式：+ - 9 * /62-754,从后往前看，每个预算符后面跟的都是其两个操作数，即每个树根跟着两个左右孩子。建树过程如下：

从后往前遍历输入的前缀表达式字符，每遇到一个运算符就用它作为根节点和后面两个数据或节点作为其左右孩子。步骤如下：



依此类推，得到，不难发现其中序遍历结果即为：9-6/2 * (7-5)+4

源代码

#include <iostream>
#include <cstring>
#include <cmath>
#include<Windows.h>
using namespace std;

const int MAXSIZE = 100;//设置读取字符的最大长度

class Node //定义树类
{
public:
	Node* leftChild;	//左孩子
	Node* rightChild;	//右孩子
	char op;			//操作符“节点值”
	double value;		//“操作数”节点值
	//构造函数：初始化所有成员变量
	Node()
	{
		leftChild = NULL;
		rightChild = NULL;
		op = '#';
		value = 0;
	}
};

/*全局变量*/
char ops[MAXSIZE];//存放读入的操作符
char formula[MAXSIZE];//从键盘读入的“算式”
bool is_num[MAXSIZE];//判断每个字符是否为数字，是为true,不是为false
double num[MAXSIZE];//存放读入的数字

/**
* 反前序建树：叶子存数值，分支存运算符
*/
Node* rldBuild(bool *is_num, int len)
{
	Node *T = new Node;
	Node *rt[MAXSIZE];//暂存的指针数组
	for (int i = 0; i < len; i++) rt[i] = new Node;
	int *isSelectable = new int[MAXSIZE];//保存操作真值,0为操作符或者不可选，1为操作数，2为已经连接的节点
	for (int i = 0; i < len; i++) {
		if (is_num[i]) isSelectable[i] = 1;
		else isSelectable[i] = 0;
	}
	if (len == 1) rt[0]->value = num[0];
	for (int i = len - 1; i >= 0; i--) {
		if (isSelectable[i]==0) {  //如果为操作符，创建节点
			rt[i]->op = ops[i];			//存入操作符
			int isLinkTwo = 2;//判断是否已经连接左右节点，2为当前值为左，1为右
			for (int j = i+1; j < len; j++) {
				if (isSelectable[j] == 1) {//当前位置是数据
					if (isLinkTwo == 2) {
						rt[i]->leftChild = rt[j];//节点后面两个分别为左边孩子和右孩子
						rt[j]->value = num[j];
					}
					if (isLinkTwo == 1) {
						rt[i]->rightChild = rt[j];//节点后面两个分别为左边孩子和右孩子
						rt[j]->value = num[j];
					}
					isSelectable[j] = 0;//设置为不可选
					isLinkTwo--;
				}
				if (isSelectable[j] == 2) {
					if (isLinkTwo == 2) rt[i]->leftChild = rt[j];
					if (isLinkTwo == 1) rt[i]->rightChild = rt[j];
					isSelectable[j] = 0;//设置为不可选
					isLinkTwo--;
				}
				if (isLinkTwo == 0) j=len;
			}
			isSelectable[i] = 2;//当前位置置为节点
		}
	}
	T = rt[0];
	return T;
}
//中序遍历测试是否建好树
void ldr(Node* node)
{
	int isBracket=0;
	if (node == NULL) return;		//如果节点为空则返回
	if (node->op == '+' || node->op == '-') //如果是加减号则加上括号
	{
		cout << "(";
		isBracket++;
	}
	ldr(node->leftChild);			//遍历左节点
	if (node->op!='#')			//如果当前节点op不是#
		cout << node->op << " ";	//则输出操作符
	else cout << node->value << " ";//否则输出操作数
	ldr(node->rightChild);		//遍历右节点
	if (isBracket) {
		cout << ")";
		isBracket--;
	}
}
//先序遍历
void dlr(Node* node)
{
	if (node == NULL) return;		//如果节点为空则返回
	if (node->op != '#')			//如果当前节点op不是#
		cout << node->op << " ";	//则输出操作符
	else cout << node->value << " ";//否则输出操作数
	dlr(node->leftChild);			//遍历左节点
	dlr(node->rightChild);		//遍历右节点
}

/**
* 将表达式转换成字符和数值
* @param t 读入的字符串数
* @param len 读入的字符串数组的有效长度，不包含'\0'
*/
void change(char *t, int len)
{
	for (int i = 0; i < len; i++) {
		if (t[i] >= '0'&&t[i] <= '9') {
			num[i] = t[i] - '0';
			is_num[i] = 1;
		}
		else {
			ops[i] = t[i];
			is_num[i] = 0;
		}
	}
}

//计算表达式的值
double solve(Node* node)
{
	if (node->leftChild == NULL && node->rightChild == NULL)
	{
		return node->value;//如果左右孩子都为空，这返回根节点的值
	}
	double tmp1 = solve(node->leftChild);//左子树求值
	double tmp2 = solve(node->rightChild);//右子树求值
	if (node->op == '+')//分支运算符 + - * /
	{
		node->value = tmp1 + tmp2;//加
	}
	else if (node->op == '-')
	{
		node->value = tmp1 - tmp2;//减
	}
	else if (node->op == '*')
	{
		node->value = tmp1 * tmp2;//乘
	}
	else if (node->op == '/')
	{
		node->value = tmp1 / tmp2;//除
	}
	else cout << "识别到错误的运算符:"<<"\""<< node->op<<"\""<<endl;
	return node->value;
}
//输出表达式
void showFormula(int len){
	for(int i=0;i<len;i++)
	{
	if (is_num[i]) cout << num[i];
	else cout << ops[i];
	}
}
//将表达式中的变量替换为常数
void atoi(char *t, char *cs, int *vs, int len1, int len2) {
	for (int i = 0; i < len1; i++)
		if ((t[i] >= 'a'&&t[i] <= 'z') || (t[i] >= 'A'&&t[i] <= 'Z')) {
			for (int j = 0; j < len2; j++)
				if (t[i] == cs[j]) t[i] = '0' + vs[j];
		}
}
//不含变量的表达式
void opt1() {
	cout << "输入你要计算的表达式(PS：注意不要输入中文的括号)" << endl;
	cin >> formula;			//从键盘读入算数表达式
	int len = strlen(formula);	//获取字符长度
	change(formula, len);
	Node *root = rldBuild(is_num, len);
	if (root != NULL) {
		ldr(root);//遍历结果
		cout << "=" << solve(root) << endl;
	}
	else {
		cout << "建树失败,请检查输入的表达式!" << endl;
	}
	system("pause");
}
//含有变量的表达式
void opt2() {
	int numOfChar;//变量的个数
	cout << "输入变量的个数(变量名仅支持一个字母)：";
	cin >> numOfChar;
	char cs[MAXSIZE];//变量名数组
	int vs[MAXSIZE];//变量值数组
	for (int i = 0; i < numOfChar; i++) {
		cout << "输入第" << i << "个变量名："; cin >> cs[i];
		cout << "输入第" << i << "个变量值："; cin >> vs[i];
	}
	cout << "输入你要计算的表达式(PS：注意不要输入中文的括号)" << endl;
	cin >> formula;			//从键盘读入算数表达式
	int len = strlen(formula);	//获取字符长度
	atoi(formula, cs, vs, len, numOfChar);//为变量赋值
	change(formula, len);
	//showFormula();//输出表达式
	Node *root = rldBuild(is_num, len);
	if (root != NULL) {
		ldr(root);//中序号遍历输出表达式
		cout << "=" << solve(root) << endl;
	}
	else {
		cout << "建树失败,请检查输入的表达式!" << endl;
	}
	system("pause");
}
//菜单项
void menuList() {
	cout << "===计算表达式的值===" << endl;
	cout << " 1.不含变量的表达式" << endl;
	cout << " 2.含有变量的表达式" << endl;
	cout << "====================\n" << endl;
	cout << "输入选项：";
	int select;
	do {
		cin >> select;
		if (select != 1 && select != 2) cout << "输入错误,请重新输入！" << endl;
	} while (select!=1&&select!=2);
	if (select == 1) opt1();
	else opt2();
}

int main()
{
	menuList();
	system("cls");
	return 0;
}