表达式树与前中后缀表达式

表达式树与前中后缀表达式计算机科学中,除了栈以外,二叉树也是处理表达式的常用工具,为了处理表达式而遵循相应规则构造的树被称为表达式树。表达式树算数表达式是分层的递归结构,一个运算符作用于相应的运算对象,其运算对象又可以是任意复杂的表达式。树的递归结构正好用来表示这种表达式。下面只讨论二元表达式。二元表达式可以很自然的联系到二叉树:以基本运算对象作为叶节点中的数据;以运算符作为非叶节点中的数据,其两棵子树是它的…

大家好,又见面了,我是你们的朋友全栈君。

计算机科学中,除了栈以外,二叉树也是处理表达式的常用工具,为了处理表达式而遵循相应规则构造的树被称为表达式树。

表达式树

算数表达式是分层的递归结构,一个运算符作用于相应的运算对象,其运算对象又可以是任意复杂的表达式。树的递归结构正好用来表示这种表达式。下面只讨论二元表达式。
二元表达式可以很自然的联系到二叉树:以基本运算对象作为叶节点中的数据;以运算符作为非叶节点中的数据,其两棵子树是它的运算对象,子树可以是基本运算对象,也可以是复杂表达式。如图是一个表达式树。
表达式树

前缀、中缀和后缀表达式

中缀表达式(中缀记法)
我们平时缩写的表达式,将运算符写在两个操作数中间的表达式,称作中缀表达式。在中缀表达式中,运算符有不同的优先级,圆括号用于改变运算顺序,这使得运算规则比较复杂,求值过程不能直接从左到右顺序进行,不利于计算机处理。

后缀表达式
将运算符写在两个操作数之后的表达式称作后缀表达式。后缀表达式中没有括号,并且运算符没有优先级。后缀表达式的求值过程能够严格按照从左到右的顺序进行,有利于计算机处理。

前缀表达式
前缀表达式是将运算符写在两个操作数之前的表达式。和后缀表达式一样,前缀表达式没有括号,运算符没有优先级,能严格按照从右到左的顺序计算。

另外,算式表达式和表达式树的关系如下:

  • 表达式树的先根遍历:前缀表达式
  • 表达式树的中根遍历:中缀表达式
  • 表达式树的后根遍历:后缀表达式

表达式的转换

利用表达式树

给定一个表达式的中缀形式:(4+1*(5-2))-6/3
首先将每个运算加上括号,区分优先级,得到(4+(1*(5-2)))-(6/3)
括号外的-优先级最低,作为根节点,(4+(1*(5-2)))作为左子树,(6/3)作为右子树;
递归的转换4+(1*(5-2)),+最为根节点,4是左子树,(1*(5-2))是右子树。*是右子树的根节点,1是左子树,(5-2)是右子树。最后计算(5-2),-是根节点,5是左子树,2是右子树。得到的表达式树如文章之初给出的图。

构造好表达式树之后,前缀表达式和中缀表达式可根据先根遍历和后根遍历得到。
前缀表达式:- + 4 * 1 – 5 2 / 6 3
后缀表达式:4 1 5 2 – * + 6 3 / –

利用栈

将中缀表达式转换为后缀表达式
step1:初始化一个栈和一个后缀表达式字符串
step2:从左到右依次对中缀表达式中的每个字符进行以下处理,直到表达式结束

  • 如果字符是‘(’,将其入栈
  • 如果字符是数字,添加到后缀表达式的字符串中
  • 如果字符是运算符,先将栈顶优先级不低于该运算符的运算符出栈,添加到后缀表达式中,再将该运算符入栈。注意,当‘(’在栈中时,优先级最低
  • 如果字符是‘)’,将栈顶元素出栈,添加到后缀表达式中,直到出栈的是‘(’
    step3:如果表达式结束,但栈中还有元素,将所有元素出栈,添加到后缀表达式中

例如给定一个表达式的中缀形式:(4+1*(5-2))-6/3,栈中元素和表达式的变化如下表所示:

扫描到的元素 后缀表达式 说明
( ( 将(入栈,表达式空
4 ( 4 将4加入表达式
+ ( + 4 将+入栈
1 ( + 4 1 将1加入表达式
* ( + * 4 1 将*入栈
( ( + * ( 4 1 将(入栈
5 ( + * ( 4 1 5 将5加入表达式
( + * ( – 4 1 5 将-入栈
2 ( + * ( – 4 1 5 2 将2 加入表达式
) ( + * 4 1 5 2 – -出栈,加入表达式
) 4 1 5 2 – * + *和+出栈,加入表达式,栈空
4 1 5 2 – * + -入栈
6 4 1 5 2 – * + 6 6加入表达式
/ -/ 4 1 5 2 – * + 6 /入栈
3 -/ 4 1 5 2 – * + 6 3 3加入表达式
4 1 5 2 – * + 6 3 / – 表达式扫描结束,将栈中元素加入表达式

最后得到后缀表达式为4 1 5 2 – * + 6 3 / –

将中缀表达式转换为前缀表达式
中缀表达式转换到前缀表达的方法和转换到后缀表达式过程一致,细节上有所变化
step1:初始化两个栈s1 和s2
step2:从右到左依次对中缀表达式中的每个字符进行以下处理,直到表达式结束

  • 如果字符是‘)’,将其入栈
  • 如果字符是数字,添加到s2中
  • 如果字符是运算符,先将栈顶优先级不低于该运算符的运算符出栈,添加到s2中,再将该运算符入栈。当‘)’在栈中是,优先级最低
  • 如果字符是‘(’,将栈顶元素出栈,添加到s2中,直到出栈的是‘)’
    step3:如果表达式结束,但栈中还有元素,将所有元素出栈,添加s2中
    step4:将栈s2中元素依次出栈,即得到前缀表达式

给定一个表达式的中缀形式:(4+1*(5-2))-6/3,其前缀形式为 – + 4 * 1 – 5 2 / 6 3

表达式的计算

中缀表达式的计算我们已经非常清楚,前缀和后缀表达式更适合计算机处理
后缀表达式的计算
后缀表达式没有括号,运算符的顺序即为实际运算顺序,在求值过程中,当遇到运算符时,只要取得前两个操作数就可以立即进行计算。当操作数出现时,不能立即求值,需要先保存等待运算符。对于等待中的操作数而言,后出现的先运算,所以需要一个栈辅助操作。
后缀表达式的运算过程如下:
step1:设置一个栈
step2:从左到右对后缀表达式中的字符进行以下处理:
– 如果字符是数字,现将其转化为数字,然后入栈
– 如果字符是运算符,出栈两个值进行计算。计算结果入栈
– 重复以上步骤,直到后缀表达式扫描结束,栈中最后一个元素就是表达式的结果。

给定后缀表达式4 1 5 2 – * + 6 3 / -,依次将4 1 5 2 入栈,当扫描到-时,2,5出栈,计算5-2=3;将3入栈,此时栈中元素为4 1 3。接着扫描到*,3 1出栈,计算1*3=3,3入栈,栈中元素为4 3,。扫描+,3 4出栈,计算4+3=7,7入栈。接着6 3 入栈,栈中该元素为7 6 3,扫描到/,3 6出栈,计算6/3=2,2入栈,栈中元素为7 2.扫描-,2 7 出栈,计算7-2=5,5入栈。表达式扫描完毕,栈中元素为5,表达式结果为5.
前缀表达式的计算
前缀表达式的计算扫描顺序从右到左,其他和后缀表达式的计算完全一致。


以上内容转载自二叉树的简单应用–表达式树,略加修改,给此文博主一个大大的赞,良心好文!!!本文以下内容为我对于这篇博文的一个补充。

表达式树代码实现

如何给一个表达式建立表达式树呢?方法有很多,这里只介绍一种:找到”最后计算”的运算符(它是整棵表达式树的根),然后递归处理(这也是前文介绍的方法)。下面是程序:

const int maxn = 1000;
int lch[maxn], rch[maxn]; char op[maxn];
int nc = 0;		//结点数
int build_tree(char* s, int x, int y)
{
	int i, cl = -1, c2 = -1, p = 0;
	int u;
	if(y-x == 1)		//仅一个字符,建立单独结点
	{
		u = ++nc;
		lch[u] = rch[u] = 0; op[u] = s[x];
		return u;
	}
	for(i = x; i < y; i++)
	{
		switch(s[i])
		{
			case '(': p++; break;
			case ')': p--; break;
			case '+': case '-': if(!p) c1 = i; break;
			case '*': case '/': if(!p) c2 = i; break;
		}
	}
	if(c1 < 0) c1 = c2;		//找不到括号外的加减号,就用乘除号
	if(c1 < 0) return build_tree(s, x+1, y-1);		//整个表达式被一对括号括起来
	u = ++nc;
	lch[u] = build_tree(s, x, c1);
	rch[u] = build_tree(s, c1+1, y);
	op[u] = s[c1];
	return u;
}

注意上述代码是如何寻找“最后一个运算符”的。代码里用了一个变量p,只有当p=0时才考虑这个运算符。为什么呢?因为括号里的运算符一定不是最后计算的,应当忽略。例如(a+b)*c中虽然有一个加号,但却是在括号里的,实际上比它优先级高的乘号才是最后计算的。由于加减和乘除号都是左结合的,最后一个运算符才是最后计算的,所以用两个变量c1和c2分别记录“最右”出现的加减号和乘除号。
再接下来的代码就不难理解了:如果括号外有加减号,它们肯定最后计算;但如果没有加减号,就需要考虑乘除号( if(c1<0) c1 = c2 );如果全都没有,说明整个表达式外面被一对括号括起来,把它去掉后递归调用。这样,就找到了最后计算的运算符s[c1],它的左子树是区间[x, c1],右子树是区间[c1+1, y]。
提示:建立表达式树的一种方法是每次找到最后的运算符,然后递归建树。“最后计算”的运算符是在括号外的、优先级最低的运算符。如果有多个,根据结合性来选择:左结合的(如加减乘除)选最右边;右结合的(如乘方)选最左边。根据规定,优先级相同的运算符的结合性总是相同。

后缀表达式计算代码实现

这个代码十分简单,只要将算法直译过来即是代码,博主比较懒,就将这个工作交给读者了,如果学校里后面有这个作业,博主会贴上代码。。


拓展:由浅入深表达式树(一)创建表达式树

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/150082.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号