数据结构——基于二叉树的表达式求值算法

VS数据结构实现编程

文章共1,933字 · 阅读需要大约7分钟

一键AI生成摘要，助你高效阅读

问答

FineFINE01

12153人浏览 · 2022-06-17 22:44:45

FineFINE01 · 2022-06-17 22:44:45 发布

一、实验项目要求

1.输入一个表达式（表达式中的数均小于10的正整数），利用二叉树来表示该表达式，创建表达式数，然后利用二叉树的遍历操作求表达式的值。

2.输入要求：多组数据，每组数据1行，为一个表达式，表达式以“=”结尾。当输入只有一个“=”时，输入结束。

3.输出要求：每组数据输出一行，为表达式的值。

4.输入样例：2*（2+5）=

1+2=

输出样例：

二、理论分析

第一,输入表达式,创建一个基于二叉链表表示的表达式树，里面包含树节点定义。定义了树的节点和节点指针。

第二，对表达式树进行后序遍历,得到表达式的值。

第三，针对算术表达式,都可用二叉树来表示。表达式对应的二叉树创建后,利用二叉树的遍历等操作,很容易实现表达式的求值运算。由于创建的表达式树需要准确的表达运算次序,因此在扫描表达式创建表达式树的过程中,当遇到运算符时不能直接创建结点,而应将其与前面的运算符进行优先级比较,根据比较的结果再进行处理。

第四，根据表达式树与表达式对应关系的递归定义,每两个操作数和一个运算符就可以建立一棵表达式二叉树,而该二叉树又可以作为另一个运算符结点的一棵子树。可以另外借助一个表达式树栈,来暂存已建立好的表达式树的根结点,以便其作为另一个运算符结点的子树而被引用。

三、实现方法

#include<iostream>
#include <cstdio>
using namespace std;

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0

#define STACK_INIT_SIZE 100   
#define STACKINCREMENT 10   
typedef int Status;
typedef char TElemType; 
typedef int ElemType;
typedef struct BiNode
{
	TElemType data;
	struct BiNode* lchild;
	struct BiNode* rchild;
}BiNode, * BiTree;
typedef BiTree SBElemType;

int  preorderTraverse(BiTree T) 
{
	if (T == NULL)
		return 0;
	else
	{
		cout<<T->data;
		preorderTraverse(T->lchild);
		preorderTraverse(T->rchild);
	}
}

int InorderTraverse(BiTree T) 
{
	if (T == NULL)
		return 0;
	else
	{
		InorderTraverse(T->lchild);
		cout<<T->data;
		InorderTraverse(T->rchild);
	}
}


int  PostorderTraverse(BiTree T) 
{
	if (T == NULL)
		return 0;
	else
	{
		PostorderTraverse(T->lchild);
		PostorderTraverse(T->rchild);
		cout<<T->data;
	}
}



typedef struct
{
	TElemType* base;
	TElemType* top;
	int stacksize;
}SqStack;


Status InitStack(SqStack* S)
{
	S->base = (TElemType*)malloc(STACK_INIT_SIZE * sizeof(TElemType));
	if (!S->base)
	{
		cout<<"内存分配失败!\n";
		exit(0);
	}

	S->top = S->base;
	S->stacksize = STACK_INIT_SIZE;
	return OK;
}

Status GetTop(SqStack* S, TElemType* e)
{
	if (S->top == S->base)
		return ERROR;

	*e = *(S->top - 1);
	return OK;
}

Status Push(SqStack* S, TElemType e)
{
	if (S->top - S->base >= STACK_INIT_SIZE)   
	{
		S->base = (TElemType*)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(TElemType));
		if (!S->base)
		{
			cout<<"内存分配失败!\n";
			exit(OVERFLOW);
		}

		S->top = S->base + S->stacksize;
		S->stacksize += STACKINCREMENT;
	}

	*S->top++ = e;

	return OK;
}

Status Pop(SqStack* S, TElemType* e)
{
	if (S->top == S->base)
		return ERROR;

	*e = *--S->top;

	return OK;
}






typedef struct {
	SBElemType* base; 	
	SBElemType* top; 	
	int stacksize; 	
} SqStack_BiTree;


void SqStack_BiTree_InitStack(SqStack_BiTree& S)
{
	if (!(S.base = (SBElemType*)malloc(STACK_INIT_SIZE
		* sizeof(SBElemType))))
		exit(0);    
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
}

void SqStack_BiTree_DestroyStack(SqStack_BiTree& S)
{
	free(S.base);
	S.base = NULL;
	S.top = NULL;
	S.stacksize = 0;
}

void SqStack_BiTree_Push(SqStack_BiTree& S, SBElemType e)
{
	if (S.top - S.base >= S.stacksize) 
{ 
		S.base = (SBElemType*)realloc(S.base, (S.stacksize
			+ STACKINCREMENT) * sizeof(SBElemType));
		if (!S.base)
			exit(OVERFLOW);           
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*(S.top)++ = e;
}

Status SqStack_BiTree_Pop(SqStack_BiTree& S, SBElemType& e)
{

	if (S.top == S.base)
	{
		return ERROR;
	}
	e = *--S.top;;

	return OK;
}

Status SqStack_BiTree_GetTop(SqStack_BiTree S, SBElemType& e)
{

	if (S.top > S.base) {
		e = *(S.top - 1);

		return OK;
	}
	else
	{
		return ERROR;
	}

}

char Precede(char t1, char t2)
{
	int i, j;
	char pre[7][7] = { 
			{'>','>','<','<','<','>','>'},
			{'>','>','<','<','<','>','>'},
			{'>','>','>','>','<','>','>'},
			{'>','>','>','>','<','>','>'},
			{'<','<','<','<','<','=','0'},
			{'>','>','>','>','0','>','>'},
			{'<','<','<','<','<','0','='} };
	switch (t1) {
	case '+': i = 0; break;
	case '-': i = 1; break;
	case '*': i = 2; break;
	case '/': i = 3; break;
	case '(': i = 4; break;
	case ')': i = 5; break;
	case '=': i = 6; break;
	}
	switch (t2) {
	case '+': j = 0; break;
	case '-': j = 1; break;
	case '*': j = 2; break;
	case '/': j = 3; break;
	case '(': j = 4; break;
	case ')': j = 5; break;
	case '=': j = 6; break;
	}
	return pre[i][j];
}
Status In(TElemType c)
{
	switch (c)
	{
	case '+':
	case '-':
	case '*':
	case '/':
	case '(':
	case ')':
	case '=':
		return TRUE;
	default:
		return FALSE;
	}

}

ElemType Operate(ElemType a, TElemType theta, ElemType b)
{
	TElemType c;
	switch (theta)
	{
	case '+':
		c = a + b;
		break;
	case '-':
		c = a - b;
		break;
	case '*':
		c = a * b;
		break;
	case '/':
		c = a / b;
		break;
	}
	return c;
}



void EvaluateExpression(BiTree& root, char* str)
{
	SqStack OPTR;
	InitStack(&OPTR);
	SqStack_BiTree EXPT;
	SqStack_BiTree_InitStack(EXPT);

	char ch, x, theta;
	BiTree a, b;
	int i = 0;

	Push(&OPTR, '=');  
	ch = str[i++];
	GetTop(&OPTR, &x);
	while (ch != '=' || x != '=')
	{
		if (In(ch))  
		{
			switch (Precede(x, ch))
			{
			case '<':  
				Push(&OPTR, ch);
				ch = str[i++];
				break;

			case '=': 
				Pop(&OPTR, &x); 
				ch = str[i++];
				break;
			case '>':
				Pop(&OPTR, &theta);
				BiTree TEMP;
				TEMP = (BiNode*)malloc(sizeof(BiNode));
				if (!TEMP)
					exit(-1);
				TEMP->data = theta;
				SqStack_BiTree_Pop(EXPT, b);
				SqStack_BiTree_Pop(EXPT, a);

				TEMP->lchild = a;
				TEMP->rchild = b;
				SqStack_BiTree_Push(EXPT, TEMP);


				root = TEMP;
				break;
			}
		}

		if (ch >= '0' && ch <= '9')
		{
			BiTree Temp;
			Temp = (BiNode*)malloc(sizeof(BiNode));
			if (!Temp)
				exit(-1);
			Temp->data = ch;
			Temp->lchild = NULL;
			Temp->rchild = NULL;
			SqStack_BiTree_Push(EXPT, Temp);

			ch = ch = str[i++];;
		}



		GetTop(&OPTR, &x);

	}

}

int	calculate_BiTree(BiTree& T)
{
	int lvalue;
	int rvalue;
	char theta;
	if (T == NULL)	return 0;
	if (T != NULL)
	{
		if (T->lchild == NULL && T->lchild == NULL)
			return T->data - '0';
		else
		{
			lvalue = calculate_BiTree(T->lchild);
			rvalue = calculate_BiTree(T->rchild);
			theta = T->data;

			return Operate(lvalue, theta, rvalue);
		}
	}
}


int main()
{
	BiTree T;
	char str[1000];
	int result[100] = { 0 };
	int number = 0;
	do
	{
	    cout << "输入表达式：";
        cin.getline(str,30);
		
		EvaluateExpression(T, str);
		result[number] = calculate_BiTree(T);
		number++;
	} while (strcmp(str, "=") != 0);


	for (int j = 0; j < number - 1; j++)
	{
		cout << endl;
		cout<<"表达式运算结果： " << result[j] << endl;
	}
}

三、实验结果分析

1.本实验遇到的问题与解决的方法

通过这次实验我学到了对二叉树的遍历和二叉树的创建等等，而且当遇到运算符时不能直接创建结点,而应将其与前面的运算符进行优先级比。

2.对设计及调试过程的心得体会

从这次实验，我知道了要学好数据结构必须得亲自动手去编写算法，经过本次实验我才发现自己是多么的单纯，在编写过程中还是出了许多问题。以后一定要加强动手编写，不能因为困难而放弃学习。

GitCode 开源社区

旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。

更多推荐

【目标检测】目标检测的一些常用神经网络模型及方法

我的阶段性总结????文章目录1.概述1.2 目标检测的任务1.3 目标检测的分类2.R-CNN系列2.1 [R-CNN（Region with CNN features）](https://arxiv.org/pdf/1311.2524.pdf)2.2 [Fast R-CNN](https://www.cv-foundation.org/openaccess/content_iccv_2015/