表达式树

版权声明:本文为博主原创文章,转载请注明博客地址: https://blog.csdn.net/zy010101/article/details/83027514

表达式树:表达式树的叶节点是操作数,其他节点是操作符。假设所有的运算符都是双目运算符,那么刚好形成一颗二叉树。我们可以通过递归计算左子树和右子树的值,从而得到整个表达式树的值。

这就是一颗表达式树,在这棵树中,只有叶节点是操作数,其他节点都是操作符。 我们先来遍历一下这棵树。前序遍历这棵树将会得到这样一个表达式:++a*bc*de;(这样的表达式,我们称之为前缀表达式,操作符位于操作数之前。)接着,我们来中序遍历这棵树,得到的表达式是这样的:a+b*c+d*e;(中缀表达式是我们最熟悉的表达式,但是有时候中序遍历产生的表达式是不符合预期的,一般我们可以通过递归产生一个带括号的左表达式,然后打印根,最后通过递归产生一个带括号的右表达式。后序遍历会得到的表达式是这样的:abc*+de*+;(后缀表达式计算起来是非常简单的:可以参考这篇博客)我们常用的遍历表达式树的方式是中序遍历和后序遍历。这样可以得到我们人喜欢使用的中缀表达式和计算机喜欢的后缀表达式。

构造一颗表达式树的算法:该算法描述的是将一颗后缀表达式转换成表达式树的方法。

我们每次读入一个符号,如果是操作数,我们建立一个单节点树(该节点是没有左右子树的),并将指向这棵树的指针入栈;如果读到的符号是操作符,那么从栈中弹出两个子树,分别作为该操作符的左右子树,将形成的这颗新树压入栈中。接着继续读取符号,重复上面的步骤,直到读取结束为止。这时候,栈中只剩一个元素,该元素就是这颗表达式树的根节点。

创建表达式树的代码实现如下,表达式的操作数是小写字母a~z,操作符可以是+,-,*,/,^,%等双目运算符。

PTree CreatExpTree()
{
	char data;
	PTree T;
	Pstack P = CreatStack();

	cout << "请输入后缀表达式:(换行输入ctrl+z结束输入)";
	while (cin >> data)
	{
		if ('a'<= data && 'z' >= data)
		{
			T = (PTree)malloc(sizeof(Tree));
			T->data = data;
			T->left = NULL;
			T->right = NULL;
			Push(P, T);
		}
		else
		{
			T = (PTree)malloc(sizeof(Tree));
			T->data = data;
			T->right = Pop(P);
			T->left = Pop(P);
			Push(P, T);
		}
	}
	return Pop(P);    //返回树的根节点
}

由于中序表达式有时是运算逻辑错误的,因此,在中序遍历的时候加上括号就行了。中序遍历代码实现如下:

void InorderTraversal(PTree T)
{
	//递归真好用
	if (T)
	{
		if (T->left)		//如果有左子树,说明不是叶节点,应该输出一个左括号
		{
			cout << '(';
		}
		InorderTraversal(T->left);
		cout << T->data;
		InorderTraversal(T->right);
		if (T->right)		//如果有右子树,说明不是叶节点,应该输出一个右括号
		{
			cout << ')';
		}
	}
}

这样就可以加上括号了,使得中序表达式的运算是正确的。

下面给出全部代码:

exptree.h文件

#ifndef EXPTREE
#define EXPTREE

#include<iostream>
using std::cout;
using std::cin;
using std::endl;

typedef struct ExpTree Tree;
typedef Tree * PTree;
typedef char ElementType;
struct ExpTree
{
	ElementType data;
	PTree left;
	PTree right;
};
PTree CreatExpTree();
void PostorderTraversal(PTree T);
void InorderTraversal(PTree T);

#endif // !EXPTREE

stack.h文件

#ifndef STACK
#define STACK

#include"exptree.h"
typedef struct StackNode stack;
typedef stack * Pstack;

struct StackNode
{
	PTree data;
	Pstack next;
};
Pstack CreatStack();
void Push(Pstack P,PTree T);
PTree Pop(Pstack P);

#endif // !STACK

main.cpp文件

#include "stack.h"

int main()
{
	PTree ET;
	ET = CreatExpTree();
	cout << "中序遍历结果(中缀表达式):";
	InorderTraversal(ET);
	cout << endl;
	cout << "后序遍历结果:";
	PostorderTraversal(ET);
	cout << endl;
	system("pause");
	return 0;
}

stack.cpp文件

#include "stack.h"

Pstack CreatStack()
{
	Pstack P = (Pstack)malloc(sizeof(stack));
	if (P)
	{
		P->next = NULL;
		return P;
	}
	else
	{
		return NULL;
	}
}

void Push(Pstack P, PTree T)
{
	Pstack temp = (Pstack)malloc(sizeof(stack));
	temp->data = T;
	temp->next = P->next;
	P->next = temp;
}

PTree Pop(Pstack P)
{
	Pstack temp;
	PTree T = (PTree)malloc(sizeof(Tree));
	temp = P->next;
	P->next = P->next->next;
	T->data = temp->data->data;
	T->left = temp->data->left;
	T->right = temp->data->right;
	free(temp);

	return T;
}

exptree.cpp文件

#include "exptree.h"
#include "stack.h"
PTree CreatExpTree()
{
	char data;
	PTree T;
	Pstack P = CreatStack();

	cout << "请输入后缀表达式:(换行输入ctrl+z结束输入)";
	while (cin >> data)
	{
		if ('a'<= data && 'z' >= data)
		{
			T = (PTree)malloc(sizeof(Tree));
			T->data = data;
			T->left = NULL;
			T->right = NULL;
			Push(P, T);
		}
		else
		{
			T = (PTree)malloc(sizeof(Tree));
			T->data = data;
			T->right = Pop(P);
			T->left = Pop(P);
			Push(P, T);
		}
	}
	return Pop(P);
}

void PostorderTraversal(PTree T)
{
	if (T)
	{
		PostorderTraversal(T->left);
		PostorderTraversal(T->right);
		cout << T->data;
	}
}

void InorderTraversal(PTree T)
{
	//递归真好用
	if (T)
	{
		if (T->left)		//如果有左子树,说明不是叶节点,应该输出一个左括号
		{
			cout << '(';
		}
		InorderTraversal(T->left);
		cout << T->data;
		InorderTraversal(T->right);
		if (T->right)		//如果有右子树,说明不是叶节点,应该输出一个右括号
		{
			cout << ')';
		}
	}
}

测试一个表达式吧,ab+cde+**;这样一个后缀表达式,我们来看看输出的结果。

可以看到输出的结果是正确的,没有什么问题。

表达式树主要用在编译器的设计领域,当然计算器的计算也是可以使用的。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C++之类(一)

    在C++之中,我们使用类来定义自己的数据类型。通过自定义数据类型,可以使我们的编程变得更加方便。或者说C++设计类的目的就是为了使我们可以像使用基本数据类型一样...

    zy010101
  • C++之运算符重载(二)

    https://blog.csdn.net/zy010101/article/details/105240318

    zy010101
  • C++之覆盖

    在继承中,C++允许子类的成员和父类同名。此时,子类的同名成员会覆盖父类的同名成员。如果想使用父类的同名成员,需要使用类名+作用域运算符。下面这段代码演示了如何...

    zy010101
  • Bug的严重程度、优先级如何定义

    http://blog.sina.com.cn/s/blog_4adc4b090102wucf.html

    夹胡碰
  • 安卓得到状态栏高度及各个控件高度

    用户4458175
  • Motion Selective Prediction for Video Frame Synthesis

    https://www.arxiv-vanity.com/papers/1812.10157/

    用户1908973
  • TensorFlow学习笔记--CIFAR-10 图像识别

    是用于普通物体识别的小型数据集,一共包含 10个类别 的 RGB彩色图片(包含:(飞机、汽车、鸟类、猫、鹿、狗、蛙、马、船、卡车)。图片大小均为 3232像素*...

    喵叔
  • c++银行家算法

    拾点阳光
  • Motion Selective Prediction for Video Frame Synthesis

    https://www.arxiv-vanity.com/papers/1812.10157/

    用户1908973
  • Segment Routing 在大规模数据中的应用(上)

    在写《BGP在大规模数据中心中的应用》里当时就有了讨论Segment Routing(SR)的想法,因为当时我还在参与MPLS+SR的白皮书测试,得到了不少真实...

    SDNLAB

扫码关注云+社区

领取腾讯云代金券