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

逆波兰表达式、波兰表达式【数据结构与算法】逆波兰表达式、波兰表达式【数据结构与算法】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，得到最终结果。

C语⾔简单计算器原理——表达式求值（采⽤逆波兰表达式和栈
结合）
表达式的求解的关键是将其转换成逆波兰表达式(即后缀表达式，如1+2*3它的逆波兰表达式为123*+)，在后缀表达式中已经考虑了运算符的优先级，
没有括号，只有操作数和运算符。

算术表达式转换成后缀表达式⽅法如下:
依次从键盘输⼊表达式的字符ch，对于每个ch：
(1)若ch为数字则直接将其放⼊后缀数组exp中并以#号标记数值串结束。

(2)若ch为"("，则直接将其压⼊字符栈op中。

(3)若ch为")"，则将栈中"("以前的字符依次全部删除并将其放⼊后缀数组exp中，然后再将字符ch放⼊字符栈op中。

(4)若ch为"+"."-"，则将栈中"("以前的运算符依次全部删除并将其放⼊后缀数组exp中，然后再将ch放⼊op栈中。

(5)若ch为"*"."/"，则将栈顶连续的"*"."/"删除，并放⼊后缀数组exp中，然后将ch放⼊op栈中。

(6)若字符串str扫描完毕，则将栈中所有运算符删除并放⼊后缀数组exp，最后在后缀数组exp中便可得到后缀表达式。

在对后缀表达式求值时要⽤到⼀个数值栈st，在后缀数组exp中从头开始扫描，若是数字则将其放⼊数值栈中，
若遇到字符就进⾏两次退栈，并将运算结果再放⼊栈中，如此重复下去，最后当后缀数组扫描完后数值栈st的栈顶元素便是所要求的表达式的值。

表达式求值算法表达式求值是一种将数学表达式转换为计算结果的算法。

在计算机程序中，表达式是由操作符和操作数组成的，操作符是执行特定计算操作的符号，操作数是参与计算的数值。

在表达式求值算法中，我们需要处理不同类型的表达式，例如算术表达式、逻辑表达式和位运算表达式等。

算术表达式包含加法、减法、乘法、除法等操作符，逻辑表达式包含与、或、非等操作符，位运算表达式包含位与、位或、位取反等操作符。

实现一个通用的表达式求值算法需要将所有这些操作符纳入考虑，并按照特定的规则进行计算。

在表达式求值算法中，首先需要对表达式进行解析，将其拆分为操作符和操作数。

通过使用逆波兰表达式或分析树等数据结构，我们可以更方便地对表达式进行计算。

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

例如，中缀表达式"3 + 4 * 2"可以转换为逆波兰表达式"3 4 2 * +"。

逆波兰表达式的好处是可以通过一个栈来进行计算。

遍历逆波兰表达式的每个元素，当遇到操作数时，将其压入栈中；当遇到操作符时，从栈中弹出相应数量的操作数进行计算，并将结果压入栈中。

最后，栈中剩下的唯一一个元素就是表达式的结果。

另一种求值算法是使用分析树。

分析树是一种用树结构表示表达式的方法，树的每个节点都是一个操作符，而叶子节点是操作数。

通过遍历分析树，从叶子节点开始计算，并将结果返回给父节点，直到整个树的根节点成为最终结果。

这种方法可以递归地处理任意复杂的表达式。

除了使用逆波兰表达式和分析树，我们还可以使用其他方法来实现表达式求值算法。

例如，我们可以使用栈来存储操作数，并在遍历表达式时进行计算。

当遇到操作符时，从栈中弹出相应数量的操作数进行计算，并将结果压入栈中。

在表达式求值算法中，需要注意处理运算符的优先级和结合性。

不同的运算符可能有不同的优先级，例如乘法和除法的优先级高于加法和减法。

结合性指的是同一级别的运算符如何进行计算，例如加法和减法是左结合的，而赋值运算符是右结合的。

数据结构树与⼆叉树常⽤计算公式在⼆叉树的理论推导以及⼀些⾼频类型题中，我们经常需要计算⼆叉树的总结点数，某⼀层的结点数以及已知结点数反推树的⾼度，本⽂围绕这⼏个⾼频知识点，归纳总结以下公式。

公式（1）⾮空⼆叉树叶⼦结点数 = 度为2的结点数 + 1 即，N0=N2+1（2）⾮空⼆叉树上第K层⾄多有2k−1个结点（K≥1）（3）⾼度为H的⼆叉树⾄多有2H−1 个结点（H≥1）（4）具有N个（N>0）结点的完全⼆叉树的⾼度为⌈log2(N+1)⌉或⌊log2N⌋+1（5）对完全⼆叉树按从上到下、从左到右的顺序依次编号1,2，...，N，则有以下关系：①当i>1 时，结点i的双亲结点编号为⌊i/2⌋，即当i为偶数时，其双亲结点的编号为i/2 ，它是双亲结点的左孩⼦；当i为奇数时，其双亲结点的编号为 (i−1)/2 ，它是双亲结点的右孩⼦。

②当 2i≤N时，结点i的左孩⼦编号为 2i，否则⽆左孩⼦。

③当 2i+1≤N时，结点i的右孩⼦编号为 2i+1 ，否则⽆右孩⼦。

④结点i所在层次（深度）为⌊log2i⌋+1 。

（设根结点为第1层）经典例题**408考研-2011-4** 若⼀棵完全⼆叉树有768个结点，则⼆叉树中叶结点的个数是_____。

A.257B.258C.384D.385解法1根据完全⼆叉树的性质，最后⼀个分⽀结点的序号为⌊n/2⌋=⌊768/2⌋=384 ，故叶⼦结点的个数为 768−384=384解法2由⼆叉树的性质N=N0+N1+N2和N0=N2+1 可知N=2N0−1+N1，2N0−1+N1=768显然，N1=1，2N0=768，则N0=384解法3完全⼆叉树的叶⼦结点只可能出现在最下两层，由题可计算完全⼆叉树的⾼度为10。

第10层的叶⼦结点数为 768−(29−1)=257第10层的叶⼦结点在第9层共有⌈257/2⌉=129 个⽗节点第9层的叶⼦结点数为 (29−1)−129=127则叶⼦结点总数为 257+127=384Processing math: 100%。

二叉树各种计算公式总结二叉树是一种常见的数据结构，它由一个根节点和最多两个子节点组成。

许多计算问题可以通过对二叉树进行各种操作和遍历来解决。

在本文中，将总结二叉树的各种计算公式。

1.二叉树节点个数：二叉树节点个数的计算公式是N=N1+N2+1，其中N表示二叉树的节点个数，N1表示左子树的节点个数，N2表示右子树的节点个数。

2. 二叉树的高度：二叉树的高度是指从根节点到最远叶子节点的最长路径上的节点数量。

计算二叉树的高度的公式是H = max(H1, H2) + 1，其中H表示二叉树的高度，H1表示左子树的高度，H2表示右子树的高度。

3.二叉树的深度：二叉树的深度是指从根节点到当前节点的路径的长度。

计算二叉树的深度的公式是D=D1+1，其中D表示二叉树的深度，D1表示父节点的深度。

4.二叉查找树：二叉查找树是一种有序二叉树，它要求对于树中的每个节点，左子树的值都小于节点的值，右子树的值都大于节点的值。

在二叉查找树中进行的公式是：-如果目标值等于当前节点的值，则返回当前节点；-如果目标值小于当前节点的值，则在左子树中继续；-如果目标值大于当前节点的值，则在右子树中继续。

5.二叉树的遍历：二叉树的遍历是指按照一定的顺序访问二叉树中的所有节点。

常见的二叉树遍历方式有三种：- 前序遍历：先访问根节点，然后递归地访问左子树，最后递归地访问右子树。

可以表示为：root -> 左子树 -> 右子树。

- 中序遍历：先递归地访问左子树，然后访问根节点，最后递归地访问右子树。

可以表示为：左子树 -> root -> 右子树。

- 后序遍历：先递归地访问左子树，然后递归地访问右子树，最后访问根节点。

可以表示为：左子树 -> 右子树 -> root。

6.二叉树的最大路径和：二叉树的最大路径和是指二叉树中两个节点之间路径上的节点值的最大和。

可以通过递归地计算每个子树的最大路径和，然后选择最大的子树路径和来得出最终结果。

表达式二叉树的构建
在计算机科学中，表达式二叉树是一种数据结构，用于表示数学表达式。

表达式二叉树通常使用二叉树的数据结构来表示数学表达式的运算符和操作数。

下面是一个简单的示例，说明如何构建一个表达式二叉树。

假设我们有一个数学表达式：(a + b) * (c - d) / e。

我们可以将这个表达式转换为一个二叉树，其根节点表示整个表达式，左子树表示第一个括号内的表达式，右子树表示第二个括号内的表达式。

下面是构建这个表达式二叉树的步骤：
1. 首先，将表达式转换为后缀表达式（也叫逆波兰表示法）。

后缀表达式是一种不需要括号的表示法，运算符位于操作数之后。

对于上面的例子，后缀表达式为：abc+d-e*。

2. 根据后缀表达式构建二叉树。

根节点是一个新的节点，它的左子树表示第一个操作数和第一个运算符（a、b、+），右子树表示第二个操作数和第二个运算符（c、d、-）。

根节点的父节点表示整个表达式。

3. 继续按照后缀表达式的顺序构建子树，直到所有的操作数和运算符都被处理。

通过这个过程，我们可以构建一个表示给定数学表达式
的二叉树。

然后，可以使用这个二叉树来进行表达式的求值和化简等操作。

问题描述：四则运算表达式求值，将四则运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。

一、需求分析：1、本程序是利用二叉树后序遍历来实现表达式的转换，同时可以使用实验三的结果来求解后缀表达式的值。

2、输入输出格式：输入格式：在字符界面上输入一个中缀表达式，回车表示结束。

请输入表达式：输入一个中缀表达式输出格式：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。

逆波兰表达式为：输出逆波兰表达式运算结果为：输出运算后的结果3、测试用例输入：21+23*（12-6）输出：21 23 12 6 -*+二、概要设计：抽象数据类型二叉树类BiTree算法的基本思想根据题目要求，利用栈计算，和二叉树存储，来计算表达式该算法的基本思想是：先利用栈进行计算，然后用二叉树进行存储，和实验三算法一样来计算逆波兰表达式的值程序的流程程序由三个模块组成：（1）输入模块：输入一个运算式（2）计算模块：利用栈进行表达式的计算，二叉树来存储。

（3 ）输出模块：屏幕上显示出后缀表达式和运算结果。

三、详细设计物理数据类型程序含有两个类，其中栈不再赘述，另一个类为二叉树class BiTree 包含私有成员struct BiTreeNode，根节点BiTreeNode *T;索引index; int number_of_point 优先级比较函数 compare(char a,char b);生成树的函数void InorderCreate(BiTreeNode *&T,char str[30][10],int start,int end);判断数字函数bool IsNumber(char a);求值函数double Operate(BiTreeNode *T);还有显示后缀表达式的函数void display(BiTreeNode *T) ;而公有成员函数则是对私有函数的重载，为方便使用，因为函数中普遍使用了递归的算法。

波兰表达式c语言什么是波兰表达式？波兰表达式，又称为前缀表达式，是一种数学表达式的表示方法。

波兰表达式的特点是运算符位于操作数之前，而不是在中间或之后，这样可以消除括号的使用，使表达式更加简洁和清晰。

波兰表达式的起源可以追溯到20世纪20年代的波兰数学家扬·延·路卡谢维奇(Jan Łukasiewicz)。

他在研究逻辑推理时，提出了波兰表达式的概念，并用于表示逻辑公式。

后来，波兰表达式被扩展到数学领域，成为一种常用的表示数学运算的方式。

准备工作在开始讨论如何编写波兰表达式的C语言代码之前，让我们先了解一些相关的术语和概念。

1. 运算符：波兰表达式中使用的运算符有加号(+)、减号(-)、乘号(*)、除号(/) 等。

2. 操作数：波兰表达式中的操作数是指参与运算的数值，可以是整数或小数。

3. 堆栈：为了处理波兰表达式，我们需要使用一个堆栈数据结构。

堆栈可以实现将数据按照后进先出(LIFO) 的顺序进行存储和访问。

编写波兰表达式的C语言代码现在让我们开始编写一个简单的C语言代码，用来计算给定的波兰表达式。

我们将假设输入的波兰表达式中只包含整数和四则运算符。

首先，我们需要创建一个堆栈数据结构，用来存储操作数。

堆栈可以采用数组实现，声明如下：c#define STACK_SIZE 100int stack[STACK_SIZE];int top = -1;void push(int operand){if (top < STACK_SIZE - 1){top++;stack[top] = operand;}else{printf("Stack Overflow!");exit(1);}}int pop(){int operand;if (top >= 0){operand = stack[top];top;return operand;}else{printf("Stack Underflow!");exit(1);}}在这段代码中，我们定义了一个最大容量为STACK_SIZE的整型数组作为堆栈，同时声明了一个top变量来指示堆栈的索引位置。