波兰算法求二叉树表达式的值

逆波兰表达式、波兰表达式【数据结构与算法】逆波兰表达式、波兰表达式【数据结构与算法】1.前缀表达式⼜称波兰式，前缀表达式的运算符位于操作数之前。

⽐如:- × + 3 4 5 62.中缀表达式就是常见的运算表达式，如(3+4)×5-63.后缀表达式⼜称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后,⽐如:3 4 + 5 × 6 -⼈类最熟悉的⼀种表达式1+2，(1+2)3，3+42+4等都是中缀表⽰法。

对于⼈们来说，也是最直观的⼀种求值⽅式，先算括号⾥的，然后算乘除，最后算加减，但是，计算机处理中缀表达式却并不⽅便。

然后我们还需明确⼀些概念，下⾯通过我们最熟悉的中缀表达式画出⼀棵语法树来直观认识⼀下前后缀表达式的⽣成。

以A+B*(C-D)-E*F为例：中缀表达式得名于它是由相应的语法树的中序遍历的结果得到的。

上⾯的⼆叉树中序遍历的结果就是A+B*(C-D)-E*F。

前缀表达式是由相应的语法树的前序遍历的结果得到的。

上图的前缀表达式为- + A * B - C D * E F后缀表达式⼜叫做逆波兰式。

它是由相应的语法树的后序遍历的结果得到的。

上图的后缀表达式为：A B C D - * + E F * -下⾯我们关注两个点：1.如何根据⼀个逆波兰表达式求出运算结果？2.如果将⼀个中缀表达式转换成后缀表达式（逆波兰表达式）⼀.通过逆波兰表达式计算结果我们先看⼀个例⼦...后缀表达式3 4 + 5 × 6 -的计算1.从左⾄右扫描，将3和4压⼊堆栈；2.遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素，注意与前缀表达式做⽐较），计算出3+4的值，得7，再将7⼊栈；3.将5⼊栈；4.接下来是×运算符，因此弹出5和7，计算出7×5=35，将35⼊栈；5.将6⼊栈；6.最后是-运算符，计算出35-6的值，即29，由此得出最终结果。

从上⾯的过程我们如何编写代码实现呢？可以采⽤⼀个辅助的栈来实现计算，扫描表达式从左往右进⾏，如果扫描到数值，则压进辅助栈中，如果扫描到运算符，则从辅助栈中弹出两个数值参与运算，并将结果压进到栈中，当扫描表达式结束后，栈顶的数值就是表达式结果。

树的基本概念以及java实现二叉树（二）本文是我在学习了树后作的总结文章，接上篇文章，本节大致可以总结为：二叉树的遍历与实现（递归和非递归）获取二叉树的高度和度创建一棵二叉树其他应用（层序遍历，复制二叉树，判断二叉树是否相等）文章传送门：二叉树的遍历与实现递归实现二叉树的遍历非递归实现二叉树的遍历获取二叉树的高度和度获取二叉树高度获取二叉树的度非递归实现二叉树的遍历创建一棵二叉树其他应用（层序遍历，复制二叉树，判断二叉树是否相等）层序遍历通过前序遍历复制一棵二叉树判断两棵树是否相等4 二叉树的遍历与实现二叉树遍历：从树的根节点出发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被访问仅且一次。

普遍有三种遍历方式，前序、中序和后序；这里有两个关键词：访问和次序。

有一个基本思想要注意下：一个根结点+左右子树均可以看作一棵二叉树4.1 递归实现二叉树的遍历4.1.1 前序遍历基本思想：若二叉树为空，则返回。

否则从根结点开始，优先访问根结点，再前序遍历左子树，前序遍历右子树，即根——左——右图中按照前序遍历的访问结果为：A、B、D、G、H、C、E、I、F使用代码递归来实现前序遍历，如下所示：* 前序遍历（中左右）* output:A、B、D、G、H、C、E、I、F* @param rootpublic void preOrder(TreeNode root) {if (root == null) {System.out.println("preOrder data:" + root.getData());preOrder(root.leftChild);preOrder(root.rightChild);4.1.2 中序遍历基本思想：若二叉树为空，则返回。

否则优先中序遍历左子树，再访问根结点，再后序遍历右子树，即左——根——右图中按照中序遍历的访问结果为：G、D、H、B、A、E、I、C、F使用代码递归来实现中序遍历，如下所示：* 中序遍历（左中右）* output:G、D、H、B、A、E、I、C、F* @param rootpublic void midOrder(TreeNode root) {if (root == null) {midOrder(root.leftChild);System.out.println("midOrder data:" + root.getData());midOrder(root.rightChild);4.1.3 后序遍历基本思想：若二叉树为空，则返回。

波兰表达式和逆波兰表达式波兰表达式和逆波兰表达式是两种不同的数学表达式表示方法，它们都是数学领域中常用的算术表达式形式。

这两种表达式形式在计算机科学领域中也非常重要，尤其在编译器设计和计算机科学理论中有着广泛的运用。

一、波兰表达式（Polish Notation）波兰表达式是由波兰数学家扬·奥尔加罗夫斯基（JanŁukasiewicz）在1920年引入的一种新型数学表达式方式。

波兰表达式的特点是将操作符写在其对应的操作数之前，这样的表达方式也被称为前缀表达式。

例如，将传统的中缀表达式"3 + 4"转换成波兰表达式的形式，变为"+ 3 4"。

在波兰表达式中，操作符出现在对应的操作数之前。

波兰表达式的特点使得它具有一些优势。

首先，波兰表达式没有括号，因为操作符的位置明确，减少了解析表达式的复杂性；其次，波兰表达式可以直接用栈进行计算，简化了表达式的求值过程。

二、逆波兰表达式（Reverse Polish Notation）逆波兰表达式是由澳大利亚科学家查利斯·哈米脱（Charles Hamblin）在1957年引入的一种表达式形式。

逆波兰表达式的特点是将操作符写在对应的操作数之后，这种表达方式也被称为后缀表达式。

例如，将传统的中缀表达式"3 + 4"转换成逆波兰表达式的形式，变为"3 4 +"。

在逆波兰表达式中，操作符出现在对应的操作数之后。

逆波兰表达式相较于波兰表达式也有一些优势。

首先，逆波兰表达式同样没有括号，减少了解析表达式的复杂性；其次，逆波兰表达式的计算过程更加直观，可以通过简单的遍历来按照操作符进行计算。

三、波兰表达式和逆波兰表达式的应用波兰表达式和逆波兰表达式在计算机科学领域中有广泛的应用。

1.编译器设计：波兰表达式和逆波兰表达式是编译器设计中的重要概念。

编译器在解析和计算表达式时，可以通过将中缀表达式转换为波兰表达式或逆波兰表达式来简化计算过程。

实验报告课程名称： 程序设计与数据结构 指导老师： ljq 成绩： 实验名称：基于二叉树结构的表达式求值算法 实验类型： 上机 同组学生姓名：一、实验目的和要求（必填）三、代码缺陷及修正记录五、讨论、心得二、实验内容和代码（必填） 四、实验结果与分析（必填）一、实验目的和要求1. 掌握编程工具的使用2. 掌握二叉树数据结构在计算机上的实现3. 掌握通过计算机编程解决问题的基本方法二、实验内容和代码1．实验内容：● 编程实现基于二叉树结构的表达式求值算法● 表达式包含加减乘除四则运算以及至少一层括弧运算● 首先将输入的原表达式转换成二叉树结构，然后采用二叉树的后序递归遍历方法求得表达式的值● 将所有实验内容合并到一个工程，增加交互操作和循环处理（持续）2．代码1.头文件expnbitree .h装订 线1 2 3 4 5 6 7 8 91011121314151617181920212223 #include<stdio.h>#include<string.h>#include<stdlib.h>#define EXP_LEN 100 //定义表达式的最大长度#define DATA_LEN 20 //定义每个操作数的最大长度typedef struct BiTNode{int dflag; //标志域,值为1,data[]存放操作运算符;值为0,data[]存放操作数char data[DATA_LEN + 1]; //数据域,存放:操作运算符或操作数struct BiTNode *lchild, *rchild; //分别指向结点的左、右子树}BiTNode, *BiTree; //定义二叉树结点及二叉树类型指针int CreateBiTree(BiTree &bt, char *p, int len);//创建二叉树,并用bt返回树的根地址,p为表达式的首地址,l为表达式的长度int Calculate(BiTree bt, double &rst);//计算表达式的值,bt为据表达式创建的二叉树,用rst返回表达式的值int PreOrderTraverse(BiTree bt);//先序遍历二叉树bt,输出先序遍历序列int InOrderTraverse(BiTree bt); //中序遍历二叉树bt,输出中序遍历序列int PostOrderTraverse(BiTree bt); //后序遍历二叉树bt,输出后序遍历序列int DestroyBiTree(BiTree &bt); //销毁二叉树//二叉树结构的表达式求解算法入口void expnbitree();2.源文件expntree.c1 2 3 4 5 6 7 8 910111213141516 #include<stdio.h>#include<string.h>#include<stdlib.h>#include"expnbitree.h"//ExpnBiTree实现子程序入口void expnbitree(){int n, len, i; //n标志量,值为0,退出程序;len存储表达式的长度;i一般变量char expn[EXP_LEN + 1]; //存放表达式double rst; //存放表达式计算结果BiTree bt = NULL; //声明一个二叉树gets_s(expn);do{1718192021222324252627282930313233343536373839404142434445464748495051525354555657585960 i = 0;printf("请输入合法的表达式:\n");gets_s(expn);for (i = 0, len = 0; expn[i] != '\0'; i++) //去掉表达式中的空格,并计算表达式的长度if (expn[i] != ' ')expn[len++] = expn[i];expn[len] = '\0';printf("正在构建二叉树……\n");if (CreateBiTree(bt, expn, len))printf("二叉树构建成功!\n");else{ //销毁未成功建立的二叉树,释放动态申请的内存printf("二叉树构建失败!\n");printf("将销毁二叉树…………");if (DestroyBiTree(bt))printf("二叉树销毁成功!\n");else {printf("二叉树销毁失败!\n");exit(0);}continue;}printf("输出表达式的先序遍历序列……:\n");PreOrderTraverse(bt);printf("\n");printf("输出表达式的中序遍历序列……:\n");InOrderTraverse(bt);printf("\n");printf("输出表达式的后序遍历序列……:\n");PostOrderTraverse(bt);printf("\n");printf("计算表达式的值……:\n");if (Calculate(bt, rst))printf("%g\n", rst);elseprintf("计算表达式的值失败!\n");printf("即将销毁二叉树…………");if (DestroyBiTree(bt))printf("二叉树销毁成功!\n");else {printf("二叉树销毁失败!\n");exit(0);}printf("如果要继续计算下一个表达式,请输入1,否则,返回上一级:\n ");616263646566676869707172737475767778798081828384858687888990919293949596979899 100 101 102 103 104scanf_s("%d", &n);getchar();} while (n==1);}//创建二叉树int CreateBiTree(BiTree &bt, char *p, int len){int i = 0, lnum = 0, rpst1 = -1, rpst2 = -1, pn = 0;//lnum记录"("的未成对个数;//rpst1/rpst2记录表达式中优先级最低的("*"、"/")/("+"、"-")的位置;//pn记录操作数中"."的个数,以判断输入操作数是否合法if (len == 0)return 1;if (!(bt = (BiTree)malloc(sizeof(BiTNode)))) {printf("内存申请失败\n");return 0;}else{//初始化bt->lchild = bt->rchild = NULL;memset(bt->data, '\0', sizeof(bt->data));//memset是计算机中C/C++语言函数——memset(void*s,int ch,size_t n);//将s所指向的某一块内存中的后n个字节的内容全部设置为ch指定的ASCII值，//第一个值为指定的内存地址，块的大小由第三个参数指定，这个函数通常为新申请的内存做初始化工作，其返回值为s。

实验三——简易计算器（二叉树）05111341班李凌豪 11201312631．需求分析1.1.问题重述（1）问题描述由键盘输入一算术表达式，以中缀形式输入，试编写程序将中缀表达式转换成一棵二叉表达式树，通过对该的后序遍历求出计算表达式的值。

（2）基本要求a．要求对输入的表达式能判断出是否合法。

不合法要有错误提示信息。

b．将中缀表达式转换成二叉表达式树。

c．后序遍历求出表达式的值（3）数据结构与算法分析一棵表达式树，它的树叶是操作数，如常量或变量名字，而其他的结点为操作符。

a．建立表达式树。

二叉树的存储可以用顺序存储也可用链式存储。

当要创建二叉树时，先从表达式尾部向前搜索，找到第一个优先级最低的运算符，建立以这个运算符为数据元素的根结点。

注意到表达式中此运算符的左边部分对应的二叉绔为根结点的左子树，右边部分对应的是二叉绔为根结点的右子树，根据地这一点，可用递归调用自己来完成对左右子树的构造。

b．求表达式的值。

求值时同样可以采用递归的思想，对表达式进行后序遍历。

先递归调用自己计算左子树所代表的表达式的值，再递归调用自己计算右子树代表的表达式的值，最后读取根结点中的运算符，以刚才得到的左右子树的结果作为操作数加以计算，得到最终结果。

（4）测试1.2.问题分析本实验要求我们编写一个程序，利用二叉树，实现简易计算器的功能。

实现实数范围内的四则混合运算，而且要考虑括号对运算顺序的影响。

而且，题目要求用二叉树的知识来实现程序功能，因此需要将输入的中序表达式转换成逆波兰序列，然后就以此序列建立二叉链表，之后通过后序遍历实现运算的功能。

大概要求就是这样的。

2．概要设计2.1.抽象数据类型的定义考虑到，算符为字符型变量，算数为单精度浮点型变量。

考虑先讲输入的浮点数替换为char型的符号。

Struct jd为二叉链表的节点类型。

每一个节点都有字符域data，数字的话会有数值域shuzi为单精度浮点数。

struct jd{char data;float shuzi;struct jd *next1;struct jd *next2;};Struct haha 类型的数组ka[20]用来存放运算数，如果是运算数，就存进来，然后用字符域fuhao来代替数值域的单精度shuzi。

二叉树计算表达式计算表达式是计算机科学中常见的任务，而二叉树是一种常用的数据结构，用于表示表达式。

本文将介绍二叉树如何表示和计算表达式。

一、二叉树表示表达式二叉树是由节点和边组成的树状结构。

每个节点都包含一个值和两个指向左右子节点的指针。

二叉树可以用来表示数学表达式。

例如，下面是一个包含加、减、乘、除的表达式：```5 + 3 *6 / 2 - 4```将表达式转化为二叉树表示，根节点为`-`，其左子树是`+`，右子树是`4`。

`+`节点的左子树为`5`，右子树为`/`。

`/`节点的左子树为`*`，右子树为`2`。

`*`节点的左子树为`3`，右子树为`6`。

```-/ \+ 4/ \5 // \* 2/ \3 6```每个节点的值表示该节点的操作符或操作数。

叶子节点是操作数，内部节点是操作符。

二、计算二叉树表达式计算表达式需要递归地对二叉树进行遍历。

从根节点开始，如果是操作符节点，就对其左右子节点进行递归。

如果是操作数节点，就返回该节点的值。

等到递归完成后，就可以根据操作符节点的值和左右子节点的值对表达式进行计算了。

对于上面的表达式二叉树，计算的过程如下。

首先计算根节点的左右子节点，即`+`节点和`4`节点的值。

`+`节点还需要计算其左右子节点`5`和`/`节点的值。

`/`节点又需要计算其左右子节点`*`和`2`的值。

`*`节点需要计算其左右子节点`3`和`6`的值。

归纳起来，计算的顺序是从下到上，从左到右。

```-/ \+ 4/ \5 // \* 2/ \3 6```按照计算顺序求值：1. 计算`3 * 6`，得到18。

2. 计算`6 / 2`，得到3。

3. 计算`3 / 3`，得到1。

4. 计算`5 + 1`，得到6。

5. 计算`6 - 4`，得到2。

因此，表达式`5 + 3 * 6 / 2 - 4`的值是2。

三、扩展上面的例子说明了如何将表达式转为二叉树，并计算表达式的值。

但实际中会有更复杂的表达式，如函数调用、变量引用等。

树和二叉树的计算公式
树和二叉树是计算机科学中重要的数据结构，它们可以用于各种算法和数据处理应用。

在计算树和二叉树的性质和操作时，需要使用一些计算公式。

一、树的计算公式
1. 节点总数公式：假设一棵树有n个节点，那么它的节点总数
为n=1+r1+r2+...+rk，其中r1、r2、...、rk分别表示每个节点的
子节点数。

2. 叶子节点数公式：一棵树的叶子节点数等于每个非叶节点子
节点数之和加1，即l=r1+r2+...+rk+1。

3. 深度公式：一棵树的深度为从根节点到最深叶子节点的路径
长度，可以用递归的方式计算：d(T)=max{d(T1),d(T2),...,d(Tk)}+1，其中T1、T2、...、Tk是根节点的子树，d(Ti)表示第i个子树的深度。

二、二叉树的计算公式
1. 节点总数公式：假设一棵二叉树有n个节点，那么它的节点
总数为n=2^h-1，其中h为树的高度。

2. 叶子节点数公式：一棵二叉树的叶子节点数等于度数为2的
节点数加1，即l=n/2+1。

3. 深度公式：一棵二叉树的深度为从根节点到最深叶子节点的
路径长度，可以用递归的方式计算：d(T)=max{d(T1),d(T2)}+1，其
中T1、T2是根节点的左右子树，d(Ti)表示第i个子树的深度。

以上是树和二叉树的一些常用计算公式，可以用于分析和设计算法，帮助开发人员更好地理解和应用这些数据结构。

表达式求值算法表达式求值算法是计算机科学中的重要概念之一，用于计算数学表达式的结果。

在编程语言中，表达式求值是一项基本的操作，并且经常在计算过程中需要用到。

本文将介绍一些常见的表达式求值算法及其实现。

1. 逆波兰表达式法逆波兰表达式法是一种用于计算数学表达式的算法，它使用后缀表达式（也称为逆波兰表达式）来表示表达式。

逆波兰表达式是将操作符放在操作数之后的一种表示方法。

对于任意一个数学表达式，都可以通过将中缀表达式转换为后缀表达式，然后使用栈结构计算得到结果。

逆波兰表达式法的优点是计算顺序明确，不需要考虑运算符的优先级和括号的处理。

2. 中缀表达式转后缀表达式法中缀表达式是我们常见的数学表达式，如 3 + 4 * 5。

在中缀表达式中，操作符的优先级和括号起着很大的作用。

为了将中缀表达式转换为后缀表达式，我们需要使用到栈结构。

具体的算法如下：- 遍历中缀表达式的每个元素。

- 如果是操作数，则直接输出。

- 如果是操作符，则判断其与栈顶操作符的优先级，决定是否将其压入栈。

- 如果是左括号，则直接压入栈。

- 如果是右括号，则依次弹出栈顶操作符，并输出，直到遇到左括号为止。

- 遍历完表达式后，如果栈不为空，则依次弹出栈顶操作符，并输出。

3. 后缀表达式求值法后缀表达式（逆波兰表达式）的求值方法相对简单。

我们可以使用栈结构来计算后缀表达式的结果。

具体的算法如下：- 遍历后缀表达式的每个元素。

- 如果是操作数，则将其压入栈。

- 如果是操作符，则弹出栈顶的两个操作数，执行相应的计算，并将结果压入栈。

- 遍历完后缀表达式后，栈中最后剩下的元素即为计算结果。

4. 二叉树表示法除了逆波兰表达式法和中缀表达式法，我们还可以使用二叉树来表示表达式，并通过遍历二叉树来计算表达式的结果。

具体的算法如下：- 构建二叉树，将表达式的操作符作为根节点，将操作数作为叶节点。

- 通过后序遍历二叉树，计算出每个子树的值，并将结果返回给其父节点。

c语言基于二叉树的表达式求值算法C语言中，基于二叉树的表达式求值算法主要包括两部分：中缀表达式转换为后缀表达式和后缀表达式求值。

1.中缀表达式转换为后缀表达式中缀表达式是我们常见的数学表达方式，例如3 + 4 * 2 - 5。

为了方便计算机求值，我们需要将中缀表达式转换为后缀表达式，也叫做逆波兰表达式。

转换的过程使用栈数据结构来实现。

具体算法如下：1.定义一个栈和一个结果字符串，栈用于存储操作符，结果字符串用于保存后缀表达式。

2.从左到右遍历中缀表达式的每一个字符。

3.如果当前字符是数字，直接将其加入结果字符串。

4.如果当前字符是左括号"("，将其入栈。

5.如果当前字符是右括号")"，则依次将栈顶的操作符弹出并加入结果字符串，直到遇到左括号为止，同时将左括号从栈中弹出。

6.如果当前字符是操作符，需要将栈中优先级比当前操作符高或者相等的操作符弹出并加入结果字符串，然后将当前操作符入栈。

7.遍历完所有字符后，将栈中剩余的操作符依次弹出并加入结果字符串。

8.最终结果字符串就是后缀表达式。

例如，对于中缀表达式3 + 4 * 2 - 5，转换为后缀表达式为3 4 2 * + 5 -2.后缀表达式求值后缀表达式求值算法使用栈数据结构来实现。

具体算法如下：1.定义一个栈，用于存储操作数。

2.从左到右遍历后缀表达式的每一个字符。

3.如果当前字符是数字，则将其转换为对应的整数并入栈。

4.如果当前字符是操作符，则从栈中弹出两个操作数，先弹出的作为右操作数，后弹出的作为左操作数，根据操作符进行运算，得到结果后入栈。

5.遍历完所有字符后，栈顶的数字即为最终的结果。

例如，对于后缀表达式3 4 2 * + 5 -，求值的过程如下：1.入栈3。

2.入栈4。

3.入栈2。

4.弹出2和4，计算4 * 2 = 8，将8入栈。

5.弹出8和3，计算3 + 8 = 11，将11入栈。

6.入栈5。

7.弹出5和11，计算11 - 5 = 6，得到最终结果。