数据结构中的表达式树

2025年03月17日 | 阅读 9 分钟

表达式树是一种用于表示各种表达式的树。树数据结构用于表示表达式语句。在这种树中，内部节点总是表示运算符。

叶节点总是表示操作数。
操作总是对这些操作数执行。
树的深度中存在的运算符总是具有最高优先级。
与深度中存在的运算符相比，树中深度不深的运算符总是具有最低优先级。
操作数将始终存在于树的深度中；因此，它在所有运算符中被认为是**最高优先级**。
简而言之，我们可以将其概括为：与树顶部存在的其他运算符相比，树的深度中存在的值具有最高优先级。
这些表达式树的主要用途是**评估、分析**和**修改**各种表达式。
它还用于查找表达式中每个运算符的结合性。
例如，+ 运算符是左结合的，/ 是右结合的。
通过使用表达式树，结合性的困境已经得到解决。
这些表达式树是通过使用上下文无关文法形成的。
我们在上下文无关文法中为每个文法产生式关联了一个规则。
这些规则也称为语义规则，通过使用这些语义规则，我们可以轻松地构建表达式树。
它是编译器设计的主要部分之一，属于语义分析阶段。
在此语义分析中，我们将使用语法导向翻译，并以输出的形式生成带注释的分析树。
带注释的分析树不过是与类型属性和每个产生式规则关联的简单分析。
使用表达式树的主要目的是使复杂的表达式能够使用这些表达式树轻松地进行评估。
它是不可变的，一旦我们创建了表达式树，我们就不能再更改或修改它。
要进行更多修改，需要完全构建新的表达式树。
它还用于解决后缀、前缀和中缀表达式评估。

表达式树在以数据形式表示**语言级**代码方面起着非常重要的作用，这些数据主要存储在树状结构中。它还用于**lambda**表达式的内存表示。使用树数据结构，我们可以更透明、更明确地表达 lambda 表达式。它最初是为了将代码段转换为数据段，以便可以轻松地评估表达式而创建的。

表达式树是二叉树，其中每个外部或叶节点对应于操作数，每个内部或父节点对应于运算符，例如，表达式 7 + ((1+8)*3) 的表达式树将是

设 S 为表达式树

如果 S 不为空，则

如果 S.value 是一个操作数，则

返回 S.value

x = solve(S.left)

y = solve(S.right)

返回 calculate(x, y, S.value)

在上面的例子中，表达式树使用了上下文无关文法。

在此文法中，我们有一些与某些产生式规则关联的产生式，这些产生式规则主要被称为**语义规则**。我们可以使用这些语义规则定义从相应的产生式规则产生的结果。这里我们使用了值参数，它将计算结果并将其返回给文法的起始符号。S.left 将计算节点的左子节点，类似地，可以使用 S.right 参数计算节点的右子节点。

表达式树的用途

使用表达式树的主要目的是使复杂的表达式能够使用这些表达式树轻松地进行评估。
它还用于查找表达式中每个运算符的结合性。
它还用于解决后缀、前缀和中缀表达式评估。

表达式树的实现

要实现表达式树并编写其程序，我们需要使用堆栈数据结构。

我们知道堆栈基于后进先出 LIFO 原则，最近推入堆栈的数据元素在需要时会被弹出。为了实现它，使用了堆栈的两个主要操作：push 和 pop。使用 push 操作，我们将数据元素推入堆栈，使用 pop 操作，我们将数据元素从堆栈中移除。

表达式树实现中堆栈的主要功能

首先，我们将从左到右扫描给定的表达式，然后逐个检查识别出的字符，

如果扫描到的字符是操作数，我们将应用 push 操作并将其推入堆栈。
如果扫描到的字符是运算符，我们将对其应用 pop 操作，从堆栈中移除两个值作为其子节点，然后将当前父节点推回堆栈。

C 编程语言中表达式树的实现

// C program for expression tree implementation
#include <stdio.h>
#include <stdlib.h>

/* The below structure node is defined as a node of a binary tree consists 
of left child and the right child, along with the pointer next which points to the next node */
struct node 
{
	char info ;
	struct node* l ;
	struct node* r ;
	struct node* nxt ;
};
struct node *head=NULL;
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newnode(char data)
{
	struct node* node = (struct node*) malloc ( sizeof ( struct node ) ) ;
	node->info = data ;
	node->l = NULL ;
	node->r = NULL ;
	node->nxt = NULL ;
	return ( node ) ;
}
void Inorder(struct node* node)
{
	if ( node == NULL)
		return ;
	else
	{
	/* first recur on left child */
	Inorder ( node->l ) ;

	/* then print the data of node */
	printf ( "%c " , node->info ) ;

	/* now recur on right child */
	Inorder ( node->r ) ;
	}
}

void push ( struct node* x )
{
	if ( head == NULL )
	head = x ;
	else
	{
		( x )->nxt = head ;
		head = x ;
	}
	// struct node* temp ;
	// while ( temp != NULL )
	// {
	//	 printf ( " %c " , temp->info ) ;
	//	 temp = temp->nxt ;
	// }
}
struct node* pop()
{
	// Poping out the top most [pointed with head] element
	struct node* n = head ;
	head = head->nxt ;
	return n ;
}
int main()
{
	char t[] = { 'X' , 'Y' , 'Z' , '*' , '+' , 'W' , '/' } ;
	int n = sizeof(t) / sizeof(t[0]) ;
	int i ;
	struct node *p , *q , *s ;
	for ( i = 0 ; i < n ; i++ ) 
	{
		// if read character is operator then popping two
		// other elements from stack and making a binary
		// tree
		if ( t[i] == '+' || t[i] == '-' || t[i] == '*' || t[i] == '/' || t[i] == '^' )
		{
			s = newnode ( t [ i ] ) ;
			p = pop() ;
			q = pop() ;
			s->l = q ;
			s->r = p;
			push(s);
		}
		else {
			s = newnode ( t [ i ] ) ; 
			push ( s ) ;
		}
	}
	printf ( " The Inorder Traversal of Expression Tree: " ) ;
	Inorder ( s ) ;
	return 0 ;
}

上述程序的输出为

X + Y * Z / W

C++ 编程语言中表达式树的实现

// C++ program for expression tree
#include <bits/stdc++.h>
using namespace std ;
/* The below class node is defined as a node of a binary tree consists 
of left child and the right child, along with the pointer next which points to the next node */

class node 
{
public:
	char info ;
	node* l ;
	node* r ;
	node* nxt = NULL ;
	node ( char c )
	{
		this->info = c ;
		l = NULL ;
		r = NULL ;
	}
	node()
	{
		l = NULL ;
		r = NULL ;
	}
	friend class Stack ;
	friend class tree ;
} ;
class Stack 
{
	node* head = NULL ;

public:
	void push ( node* ) ;
	node* pop() ;
	friend class tree ;
} ;
class tree 
{
public:
	void inorder ( node* x )
	{
		// cout<<"Tree in InOrder Traversal is: "<<endl;
		if ( x == NULL )
			return ;
		else 
		{
			inorder ( x->l ) ;
			cout << x->info << " " ;
			inorder ( x->r ) ;
		}
	}
} ;

void Stack::push( node* x )
{
	if ( head == NULL ) 
	{
		head = x ;
	}
	// We are inserting here nodes at the top of the stack [following LIFO principle]
	else 
	{
		x->nxt = head ;
		head = x ;
	}
}
node* Stack::pop()
{
	// Poping out the top most [ pointed with head ] element
	node* p = head ;
	head = head->nxt ;
	return p ;
}
int main()
{
	string str = "XYZ*+W/" ;
	// If you wish take input from user:
	//cout << "Insert Postorder Expression: " << endl;
	//cin >> s;
	Stack s ;
	tree t ;
	node *p, *q, *re;
	int n = str.length() ;
	for ( int i = 0 ; i < n ; i++ ) 
	{
		

		if ( str[ i ] == '+' || str[ i ] == '-' || str[ i ] == '*' || str[ i ] == '/' || str[ i ] == '^') 
		{
			re = new node( str[i] ) ;
			p = s.pop() ;
			q = s.pop() ;
			re->l = q ;
			re->r = p ;
			s.push(re) ;
		}
		else 
		{
			re = new node( str[ i ] ) ;
			s.push(re) ;
		}
	}
	cout << " The Inorder Traversal of Expression Tree: " ;
	t.inorder(re) ;
	return 0 ;
}

上述程序的输出为

X + Y * Z / W

Java 编程语言中表达式树的实现

// Java program for expression tree
import java.util.* ;
/* The below class node is defined as a node of a binary tree consists 
of left child and the right child, along with the pointer next which points to the next node */

class Node
{
    char info ;
    Node l , r ;
    public Node(char data)
	{
        this.info = data ;
        l = null ;
		r = null ;
    }
}

public class Main 
{
    public static boolean isOperator ( char ch )
	{
        if ( ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^' ) 
		{
            return true ;
        }
        return false ;
    }
    public static Node Tree ( String postfix )
	{
        Stack<Node> st = new Stack<Node>();
        Node t1,t2,temp ;

        for ( int i = 0 ; i < postfix.length(); i++ ) 
		{
            if ( !isOperator( postfix.charAt(i) ) )
			{
                temp = new Node( postfix.charAt(i) ) ;
                st.push( temp ) ;
            }
            else
			{
                temp = new Node ( postfix.charAt(i) ) ;

                t1 = st.pop() ;
                t2 = st.pop() ;

                temp.l = t2 ;
                temp.r = t1 ;

                st.push(temp) ;
            }

        }
        temp = st.pop() ;
        return temp ;
    }
    public static void inorder( Node parent ){
        if ( parent == null ) return ;  

        inorder ( parent.l ) ;
        System.out.print ( parent.info ) ;
        inorder ( parent.r ) ;
    }
    public static void main( String[] args ) 
	{
        String postfix = "XYZ*+W/" ;

        Node r = Tree( postfix ) ;
        inorder ( r ) ;
    }
}

上述程序的输出为

X + Y * Z / W

下一个主题数据结构中的垃圾回收

数据结构中的表达式树

表达式树的用途

表达式树的实现

表达式树实现中堆栈的主要功能

C 编程语言中表达式树的实现

C++ 编程语言中表达式树的实现

Java 编程语言中表达式树的实现

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

数据结构中的表达式树

表达式树的用途

表达式树的实现

表达式树实现中堆栈的主要功能

C 编程语言中表达式树的实现

C++ 编程语言中表达式树的实现

Java 编程语言中表达式树的实现

相关帖子

广义斐波那契数

C++ 中的链表数据结构及图解

对 0、1 和 2 的数组进行排序 | 荷兰国旗问题

股票收益问题

从目标节点开始烧毁二叉树

如何在一个数组中高效地实现 k 个栈

数组中的最大平衡和

查找和为零的三元组

检查字符串的某个回文排列是否存在

对给定矩阵进行排序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器