用栈和二叉树实现中缀表达式转后缀表达式构建计算机并求值实验报告

中缀表达式转后缀表达式---栈--⼆叉树---四则运算 我们平常书写的四则运算表达式属于中缀表达式，形式为"9+（3-1）*3+10/2"，因为所有的运算符号都在两操作数之间，所以称为中缀表达式。

我们使⽤中缀表达式来计算表达式的值，不过这种形式并不适合计算机求解。

接下来，我们将中缀表达式转化为后缀表达式，所谓的后缀表达式就是操作符位于操作数后⾯的不包含括号的算数表达式，也叫做逆波兰表达式。

1）⾸先介绍⼀种⼈⼯的转化⽅法()。

以"9+（3-1）*3+10/2"为例，按照运算的规则，找出⾸先计算的部分，这部分包含两个操作数和⼀个操作符，将操作符移动到两个操作数右侧，这就完成了第⼀部分的转换，将这部分看作⼀个操作数，按照运算规则，以相同的⽅法转换，转换过程如下：2）还可以利⽤⼆叉树求得后缀表达式，⾸先利⽤中缀表达式构造⼆叉树，数字是叶⼦节点，操作符为根节点。

每次找到“最后计算”的运算符，作为当前根节点，运算符左侧表达式作为左节点，右侧表达式作为右节点，然后递归处理()。

9+（3-1）*3+10/2对应的⼆叉树的构造过程如下图所⽰： 此⼆叉树做后序遍历就得到了后缀表达式。

对应代码：3）还可以利⽤栈来实现中缀表达式转化为后缀表达式。

转化⽅法如下所述：a.从左向右扫描表达式，如果是数字就输出，否则转b。

b.如果当前扫描的字符是")"，则栈顶元素出栈并输出⼀直到栈顶元素为"("，然后删除栈顶元素"("，并不输出。

c.如果扫描的字符或者栈顶元素是“(”，扫描的字符直接⼊栈。

即使扫描的字符是")"也不会⼊栈，因为如果是")"，会出栈⾄栈顶元素是"("。

d.如果扫描字符是"+"或者"-",则⼀直出栈⾄栈顶元素为"+"或者"-"或者"("。

浙江大学城市学院实验报告课程名称python高级程序设计实验项目名称实验五二叉树的应用----表达式求值实验成绩指导老师（签名）日期一.实验目的和要求1、掌握二叉树的链式存储结构；2、掌握在二叉链表上的二叉树的基本操作；3、掌握二叉树的简单应用----表达式树的操作。

二.实验内容1、在实验四中，已经实现了对一个中缀表达式可以用栈转换成后缀表达式，并可对后缀表达式进行求值计算的方法。

另一种思路是可以利用二叉树建立表达式树，通过对该表达式树进行求值计算，本实验实现：输入一个中缀表达式，建立该表达式的二叉树，然后对该二叉树进行表达式值的计算。

如一个中缀达式(6+2)*5 的二叉树表示为如下所示时，该二叉树的后序遍历62+5*正好就是后缀表达式。

设一般数学表达式的运算符包括+、-、*、/ 四种，当然允许（），且（）优先级高。

为方便实现，设定输入的表达式只允许个位整数。

要求设计一个完整的程序，对输入的一个日常的中缀表达式，实现以下功能：⏹建立对应的二叉树⏹输出该二叉树的前序序列、中序序列、后序序列⏹求该二叉树的高度⏹求该二叉树的结点总数⏹求该二叉树的叶子结点数⏹计算该二叉树的表达式值分析：（1）表达式树的构建方法：●构建表达式树的方法之一：直接根据输入的中缀表达式构建对于任意一个算术中缀表达式，都可用二叉树来表示。

表达式对应的二叉树创建后，利用二叉树的遍历等操作，很容易实现二叉树的求值运算。

因此问题的关键就是如何创建表达式树。

对于一个中缀表达式来说，其表达式对应的表达式树中叶子结点均为操作数，分支结点均为运算符。

由于创建的表达式树需要准确的表达运算次序，因此，在扫描表达式创建表达式树的过程中，当遇到运算符时不能直接创建结点，而应将其与前面的运算符进行优先级比较，根据比较结果进行处理。

这种处理方式在实验四中以采用过，可以借助一个运算符栈，来暂存已经扫描到的还未处理的运算符。

根据表达式树与表达式对应关系的递归定义，每两个操作数和一个运算符就可以建立一棵表达式二叉树，而该二叉树又可以作为另一个运算符结点的一棵子树。

目录一、设计思想 (01)二、算法流程图 (02)三、源代码 (04)四、运行结果 (14)五、遇到的问题及解决 (16)六、心得体会 (16)一、设计思想（1）中缀表达式转后缀表达式并计算创建一个数组存储输入的计算表达式。

另创建一个数组储存将要生成的后缀表达式。

创建一个栈储存操作符。

对已存储的表达式数组扫描。

判断当前节点，如果是操作数或’.’，直接加入后缀表达式中，如果是操作符，则比较前一个操作符与当前操作符的优先级。

如果前一个操作符的优先级较高，则将前一个操作符加入后缀表达式中，否则将操作符压入操作符栈。

如果遇到左括号’(’，直接入栈；如果遇到右括号’)’,则在操作符栈中反向搜索，直到遇到匹配的左括号为止，将中间的操作符依次加到后缀表达式中。

当执行完以上操作，发现栈中仍有剩余操作符，则将操作符依次加到后缀表达式中。

此时中缀表达式已经转换成了后缀表达式。

对后缀表达式进行计算。

如果后缀表达式为大于0小于9的字符，则将它转换成浮点型数据并存入数栈中。

如果遇到操作符，则从数栈中提取两个数，进行相应的运算。

依次进行下去，当没有运算符是，运算结束得到最后的结果。

（2）直接表达式求值创建一个数组存储输入的计算表达式。

创建两个栈，一个字符型的栈，一个双精度型的栈。

分别用来存储字符和数。

对已存储的表达式数组扫描。

判断当前节点，如果是操作数和’.’，将字符型的操作数转换为浮点型的数后存入操作数栈。

如果是操作符则判断操作符的优先级。

如果字符栈中已存储符号的优先级小于要存入的字符的优先级，则直接让字符入操作符栈。

如果字符栈中已存储符号的优先级大于或等于要存入的字符的优先级，则取出操作符栈中的一个字符和操作数栈中的两个数进行计算，然后将结果存入操作数栈中，同上进行下去，直到字符栈中已存储符号的优先级小于要存入的字符的优先级时，将操作符存入操作符栈中。

当遇到左括号’(’，将左括号直接存入操作符栈中。

当遇到右括号’)’，则在操作符栈中反向搜索，并且每搜到一个字符就在操作数栈中取两个数进行相应的计算。

目录1. 课题分析 (1)1．1设计目的 (1)1．2主要内容 (1)1．2．1中缀表达式转换为后缀表达式 (1)1．2．2后缀表达式求值 (1)1．3设计要求 (2)2.总体设计 (2)2．1数据类型的定义 (2)2．2主程序的流程 (3)3．详细设计（源代码） (4)4．调试分析 (4)4．1问题1 (8)4．2问题2 (8)4．3问题3 (9)5．测试结果 (9)6．心得体会 (10)7．参考文献 (10)1.课题分析1．1设计目的（1）掌握栈“后进先出”的特点。

（2）掌握栈的典型应用——中缀表达式转后缀表达式，并利用后缀表达式求值。

（3）掌握串或者数组的相关操作。

1．2主要内容1．2．1中缀表达式转换为后缀表达式（1）定义一个运算符栈，并输入一个中缀表达式（运算对象存在多位整数，运算符为+、-、*、/、%及括号），然后从中缀表达式中自左至右依次读入各个字符。

（2）如果是第一次读入运算对象，也是直接输出到后缀表达式；如果不是第一次读入运算对象，并且前一个读入的字符是运算对象，也是直接输出到后缀表达式；如果不是第一次读入运算对象，并且前一个读入的字符是运算符，则先输出逗号作为分隔符，然后再将该运算对象输出到后缀表达式。

（3）如果读入的是运算符，并且运算符栈为空，则将该运算符直接进栈；如果栈不为空，则比较该运算符和栈顶运算符的优先级。

若该运算符高于栈顶运算符的优先级，则将该运算符直接进栈；若该运算符低于或等于栈顶运算符的优先级，则将栈中高于或等于该运算符优先级的元素依次出栈，然后再将该运算符进栈。

每出栈一个运算符时，先输出一个逗号到后缀表达式作为分隔符，然后再将出栈运算符输出到后缀表达式。

（4）如果读入的是开括号“（”，则直接进栈；如果读入的是闭括号“）”，则一直出栈并输出到后缀表达式，知道遇到一个开括号“（”为止。

开括号“（”和闭括号“）”均不输出到后缀表达式。

（5）重复②、③、④步，知道中缀表达式结束，然后将栈中剩余的所有运算符依次出栈。

北京工业大学- 第学期信息学部计算机学院3月31日报告题目：输入中缀体现式，输出后缀体现式，并对体现式求值A．分析中缀体现式旳运算顺序受运算符优先级和括号旳影响。

因此，将中缀体现式转换成等价旳后缀体现式旳核心在于如何恰当旳去掉中缀体现式中旳括号，然后在必要时按照先乘除后加减旳优先规则调换运算符旳先后顺序。

在去括号旳过程中用栈来储存有关旳元素。

基本思路：从左至右顺序扫描中缀体现式，用栈来寄存体现式中旳操作数，开括号，以及在这个开括号背面旳其她临时不能拟定计算顺序旳内容。

（1）当输入旳是操作数时，直接输出到后缀体现式（2）当遇到开括号时，将其入栈（3）当输入遇到闭括号时，先判断栈与否为空，若为空，则表达括号不匹配，应作为错误异常解决，清栈退出。

若非空，则把栈中元素依次弹出，直到遇到第一种开括号为止，将弹出旳元素输出到后缀体现式序列中。

由于后缀体现式不需要括号，因此弹出旳括号不放到输出序列中，若没有遇到开括号，阐明括号不匹配，做异常解决，清栈退出。

（4）当输入为运算符时（四则运算+ - * / 之一）时：a.循环，当（栈非空&&栈顶不是开括号&&栈顶运算符旳优先级不低于输入旳运算符旳优先级）时，反复操作将栈顶元素弹出，放到后缀体现式中。

b.将输入旳运算符压入栈中。

（5）最后，当中缀体现式旳符号所有扫描完毕时，若栈内仍有元素，则将其所有依次弹出，放在后缀体现式序列旳尾部。

若在弹出旳元素中遇到开括号，则阐明括号不匹配，做异常解决，清栈退出。

B．实现#include<stdio.h>#include<string.h>#include<stdlib.h>#include<stack>using namespace std;#define N 1000char infix[N]; //中缀体现式（未分离，都在一种字符串里）char expression[N][10]; //保存预解决过旳体现式，也就是每个元素都分离过旳体现式char suffix[N][10]; //保存后缀体现式旳操作数int count;//体现式中元素旳个数（一种完整到数字（也许不止一位数）或者符号）int suffixLength;//后缀体现式旳长度int level(char a){switch(a){case '#':return 0;case '+':case '-':return 1;case '*':case '/':return 2;case '^':return 3;default:break;}return -1;}int isDigital(char x){if( (x>='0'&&x<='9') || (x>='A'&&x<='Z') || (x>='a'&&x<='z') || (x=='.') )return 1;return 0;}int isNumber(char *str){int i;for(i=0;str[i];i++){if(isDigital(str[i])==0)return 0;}return 1;}/*************************************预解决中缀体现式，把持续旳字符分离成不同旳元素，用字符串数组（expression[][]）保存，以便背面旳计算，由于这里考虑了运算数也许不全是个位数例如：（12+3）在解决成后缀体现式时，是123+，容易产生歧义（1+23 ? 12+3）*************************************/void pretreatment(char *str){int i,j,numberFlag;char temp[3];char number[10];count=0;numberFlag=0;for(j=0,i=0;str[i];i++){if(isDigital(str[i])==0){if(numberFlag==1){number[j]=0;strcpy(expression[count++],number); j=0;numberFlag=0;}if(str[i]!=' '){temp[0]=str[i];temp[1]=0;strcpy(expression[count++],temp); }}else {numberFlag=1;number[j++]=str[i];}}puts("分离后旳体现式为");for(i=0;i<count;i++){printf("%s ",expression[i]);}puts("");puts("");}/*****************************************中缀体现式转后缀体现式遍历字符串，对于str[i]str[i]是运算数（或者是字母替代旳运算变量）输出；str[i]是符号，有两种状况(1)，是右括号，栈顶元素输出，直到与str[i]匹配旳左括号出栈（左括号不用输出打印）(2)，是运算符，判断str[i]与栈顶元素旳优先级，str[i]优先级不高于栈顶符号，则栈顶元素输出，直到栈空或者栈顶符号优先级低于str[i]*****************************************/void infix_to_suffix(char str[N][10]){memset(suffix,0,sizeof(suffix));suffixLength=0;stack <char*> st;int i=0;char Mark[2]="#";st.push(Mark);do{if(isNumber(str[i])==1)//运算数直接保存到后缀体现式中strcpy(suffix[suffixLength++],str[i]);else if(str[i][0]=='(') //是左括号，直接入栈st.push(str[i]);else if(str[i][0]==')'){ //是右括号，栈顶出栈，直到与其匹配旳左括号出栈while( strcmp(st.top(),"(")!=0 ){char temp[10];strcpy(temp,st.top());strcpy(suffix[suffixLength++],temp);st.pop();}st.pop();}else if( strcmp(st.top(),"(")==0 )//是运算符，且栈顶是左括号，则该运算符直接入栈st.push(str[i]);else { //是运算符，且栈顶元素优先级不不不小于运算符，则栈顶元素始终//出栈，直到栈空或者遇到一种优先级低于该运算符旳元素while( !st.empty() ){char temp[10];strcpy(temp,st.top());if( level(str[i][0]) > level(temp[0]) )break;strcpy(suffix[suffixLength++],temp);st.pop();}st.push(str[i]);}i++;}while(str[i][0]!=0);while( strcmp(st.top(),"#")!=0 ){ //将栈取空结束char temp[10];strcpy(temp,st.top());strcpy(suffix[suffixLength++],temp);st.pop();}puts("后缀体现式为：");for(i=0;i<suffixLength;i++){printf("%s",suffix[i]);}puts("");puts("");}/**************************************计算后缀体现式旳值**************************************/char kt[N][10];int stackTop;void getResult(char str[N][10]){stackTop=0;/*这里要注意，内存旳分派方案导致 i 旳位置就在temp[9]旁边，然后strcpy()函数直接拷贝内存旳话，在temp越界状况下会覆盖 i 旳值*/int i;char temp[10];for(i=0;i<suffixLength;i++){if(isNumber(str[i])==1){strcpy(kt[stackTop++],str[i]);}else {char a[10],b[10];double na,nb,nc;strcpy(a,kt[stackTop-1]);na = atof(a);stackTop--;strcpy(b,kt[stackTop-1]);nb = atof(b);stackTop--;if(str[i][0]=='+')nc=nb+na;else if(str[i][0]=='-')nc=nb-na;else if(str[i][0]=='*')nc=nb*na;else if(str[i][0]=='/')nc=nb/na;sprintf(temp,"%lf",nc);strcpy(kt[stackTop++],temp);}}puts("\nThe result is : %f\n");printf("%s\n",kt[stackTop-1]);}int main(){printf("Please input calculate Expression :\n"); char temp[N];while(gets(infix)){strcpy(temp,infix);pretreatment( strcat(temp," ") );infix_to_suffix(expression);getResult(suffix);}return 0;}C．总结实验需要细心细心再细心。

数据结构表达式求值实验报告数据结构表达式求值实验报告1. 引言表达式求值是计算机科学中的一个重要问题，也是数据结构的一个经典应用。

通过将中缀表达式转换为后缀表达式，并利用栈这一数据结构，可以实现对表达式的有效求值。

本实验旨在探究数据结构在表达式求值中的应用。

2. 实验内容本实验中，我们将实现一个表达式求值的程序。

具体步骤如下：1. 将中缀表达式转换为后缀表达式。

2. 使用栈来求解后缀表达式。

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

而后缀表达式是将操作符放在操作数后面的表达式，上述中缀表达式的后缀表达式为 2 3 4 +。

中缀表达式到后缀表达式的转换可以通过以下步骤完成：1. 初始化一个栈和一个输出队列。

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

3. 如果当前字符是数字，将其加入输出队列。

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

5. 如果当前字符是右括号，将栈中的操作符依次弹出并加入输出队列，直到遇到左括号为止。

6. 如果当前字符是操作符，将其与栈顶操作符进行比较：1. 如果栈为空，或者栈顶操作符为左括号，直接将当前操作符压入栈。

2. 否则，比较当前操作符与栈顶操作符的优先级，如果当前操作符的优先级较低，将栈顶操作符弹出并加入输出队列，然后将当前操作符压入栈。

3. 如果当前操作符的优先级大于等于栈顶操作符的优先级，则直接将当前操作符压入栈。

7. 遍历完中缀表达式后，将栈中的操作符依次弹出并加入输出队列。

3.2 后缀表达式求值通过将中缀表达式转换为后缀表达式，我们可以利用栈来对后缀表达式进行求值。

具体求值操作如下：1. 初始化一个栈。

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

3. 如果当前字符是数字，将其加入栈。

4. 如果当前字符是操作符，从栈中弹出两个数字，进行相应的运算，然后将结果加入栈。

5. 遍历完后缀表达式后，栈中的元素即为最终的结果。

4. 实验结果我们用中缀表达式\。

利用栈或二叉树将算术表达式输入串(只要求1位整数)转换为后缀式,然后计算该表达式利用栈或二叉树将算术表达式输入串(只要求1位整数)转换为后缀式,然后计算该表达式算术表达式的计算通常需要将中缀表达式转换为后缀表达式，然后使用栈或二叉树对后缀表达式进行计算。

首先，我们需要定义运算符的优先级。

在本例中，我们只考虑加法'+'和减法'-'两个运算符，其中加法的优先级较低。

接下来，我们可以使用栈来转换中缀表达式为后缀表达式。

具体步骤如下：1. 创建一个空栈和一个空字符串，用于存储后缀表达式。

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

3. 对于每个字符，进行如下处理：- 如果是数字，则直接添加到后缀表达式字符串中。

- 如果是运算符，则比较其与栈顶运算符的优先级。

- 如果栈为空或栈顶运算符为'('，则直接将当前运算符入栈。

- 如果当前运算符的优先级大于栈顶运算符的优先级，则将当前运算符入栈。

- 如果当前运算符的优先级小于或等于栈顶运算符的优先级，则将栈顶运算符弹出并加入后缀表达式字符串中，直到栈为空或栈顶运算符为'('，然后将当前运算符入栈。

- 如果是左括号'('，则直接将其入栈。

- 如果是右括号')'，则将栈顶运算符弹出并加入后缀表达式字符串中，直到遇到左括号'('，然后将左括号出栈但不加入后缀表达式字符串。

4. 遍历完中缀表达式后，将栈中剩余的运算符依次弹出并加入后缀表达式字符串中。

现在，我们已经将中缀表达式转换为后缀表达式。

接下来，我们可以使用栈或二叉树来计算后缀表达式。

1. 创建一个空栈，用于存储操作数。

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

3. 对于每个字符，进行如下处理：- 如果是数字，则将其转换为整数并入栈。

- 如果是运算符，则从栈中弹出两个操作数，进行相应的运算，并将结果入栈。

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

中缀表达式改后缀表达式一、需求分析１．本程序采用的是二叉树后序遍历来实现四则运算的中缀表达式改为后缀表达式;２．需要用一个类来代表数据的结构；３.输入输出格式：输入:在字符界面上输入一个中缀表达式，回车表示结束。

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

二、概要设计ﻩ抽象数据类型用Nodｅ类来定义一个结点：classＮｏｄe｛ｐuｂlｉc:ﻩchar ｃh[maｘ］；/／每个结点的字符串Node* ｌChild;//左指针Ｎｏｄe＊rＣｈild;/／右指针Ｎｏde();~Nｏde(）;};算法的基本思想1.输入中缀表达式，用函数对字符串中的空格或者等号进行处理,由于程序需要，会在输入的字符串结尾加入‘＝’;2.用函数一次扫描每一个字符，有异常字符，报错；没有，则每次取出连续的数字字符或加减乘除的符号,放入结点，并按规则,将上一结点的左或右指针指向该结点;2.扫描：①扫描过程在树的建立过程中；②每次扫描,获得数字字符作为一个结点,并返回数字字符后的算数运算符或者括号;③根据返回的运算符或括号,确定相应的指针赋值或是新建结点；(有错时,会退出程序）3.后序遍历法输出获得结果。

算法的时空分析因为在处理字符串时，需要逐一扫描，也建立了新的字符数组，所以时间复杂度为Θ（n);同样，扫描的循环,也与字符串的长度有关,时间复杂度也为Θ（n)输入和输出的格式ﻩ输入:3.4+５*（2*(4＋5）＋７)输出:3．4 5 ２4 5 + * 7 +* +五、测试结果六、实验总结这个程序好难,自己很难想到这方法。

不过,没想法时,看不懂别人的程序时,可以通过调试的方法，去获取程序的主要思想,从而变为自己的想法,去实现他。

代码嘛,主要是多写，多仿,写代码的能力自然而然就提高了。

七、附录（可选）#inｃlｕｄｅ<ｉｏsｔｒeam＞＃inclｕde<stｒｉnｇ＞uｓing naｍeｓpace std;ｃonｓｔintｍaｘ=１０0;class Node{puｂlic：ｃhaｒch[max］;Node* ｌＣhiｌd；Nｏｄe* rCｈiｌd；ﻩNode(）;ﻩ~Noｄe（）；};Nｏde::Node（)｛sｔrｃpy(cｈ,""）;ﻩｌCｈild=rＣhild=ＮUＬＬ;}Nｏde::~Ｎodｅ(){ｉｆ（lChild!=ＮULL）ﻩﻩｄelete lChild；if（rChilｄ!=NＵLL）ﻩﻩｄelete rCｈild;}static int counｔ=0;statiｃchａr array[mａx］;／/保存原始的中缀表达式ｓｔatｉc chａr str[2＊ｍaｘ]；／/保存后序遍历出来的字符串,为表达式求值提供方便ｓtatiｃint k=0;voiｄenteｒ(）;／/输入函数ｃhar gｅｔOp(Noｄe *tｅmp）；//temp指针保存每个接点的,返回的是运算符或者Ｎodｅ* ｃrｔTrｅe(Nodｅ* root); //传入根结点指针,返回根结点指针ｖoｉｄoutpuｔ(Nｏde *rｏot);／/获得处理后的字符串boｏl ｉsErroｒ（ｃｈaｒ）;//判断字符是否有问题void ｄｅal(）；/／对字符数组进行处理int maiｎ()｛ﻩＮode* root=ＮUＬL;cin.ｇeｔline(ａrray，4０)；deal();root=crｔTree(rｏoｔ);ﻩｏutｐｕt(root);ﻩcout ＜< str;retｕｒn0;}char getOp(Noｄe *teｍp）//将数字字符存入一/／个结点，并返回数字字符的后一个符号｛ｉｎt i=０；if(iｓErｒｏr（ａrray[couｎt]))ﻩ{ﻩﻩeｘit(0）；ﻩ}ﻩｗhｉｌe(ａｒrａy［count]＜='９'&＆array[ｃｏuｎt]>=＇０＇||ａrｒay［couｎt］=='.'){ﻩﻩｔｅｍｐ->ｃh[i]＝ａrray[coｕnt]；ﻩi＋+;count++;｝ﻩtｅmp->ｃh[i]='\0';count++；ﻩｒetｕrn arraｙ[cｏunt-1］;}Ｎoｄｅ* ｃrｔTrｅe（Node* ｒｏot）{Node ＊p,＊ｑ；char ｏp；ﻩｉf(root==NULＬ){ﻩroot=nｅｗNodｅ；ﻩp＝new Nodｅ;｝ﻩｏp＝getOp(root);ﻩwhｉle(op！=＇=')ﻩ{ﻩq＝ｎeｗNoｄe；ﻩq-＞ch[０]=op；ﻩq->ch[1]＝'＼0'；ﻩｓwiｔcｈ(ｏp)ﻩﻩ｛ﻩﻩｃａse '＋':ﻩcａse '-': q－>lChｉld=root;ﻩﻩｒoot＝q;ﻩﻩp=ｎeｗＮode;ﻩﻩﻩｏp＝gｅtOp(ｐ);ﻩﻩﻩﻩﻩroot->rChｉlｄ＝ｐ;ﻩﻩbreaｋ;ﻩﻩcase '*＇:ﻩｃase '/'：if(ｒoot->ch[０］＝='＋'|｜root-＞cｈ[0]=＝'-')ﻩﻩﻩﻩ{ﻩﻩﻩﻩp＝new Noｄe;ﻩstrｃpy(p－＞ｃh,ｒooｔ－>ch）;ﻩﻩﻩｐ-＞lChｉld=ｒoｏt;ﻩﻩﻩﻩｐ－>rCｈild=q;ﻩﻩﻩｏp＝gｅtOp(rooｔ）；ﻩﻩﻩﻩrｏoｔ=p；ﻩﻩﻩ }ﻩeｌｓeﻩﻩﻩ{ﻩｑ－＞ｌChｉld=root；ﻩﻩﻩｒoｏt=q;ﻩﻩﻩp=new Node；ﻩﻩﻩop=gｅｔOp（p）;ﻩﻩrｏot->rChilｄ=p；ﻩﻩﻩﻩ｝ﻩﻩｂreａk;ﻩｃaｓe '（＇:p=ｒoｏt；ﻩﻩﻩｗhile(p->ｒChiｌｄ)ﻩﻩﻩp=ｐ-＞rChild;ﻩﻩif(ｐ->lChｉｌd==NUＬＬ)ﻩ{ﻩﻩﻩﻩp->lChild=crtTree（p->lChｉｌd)；//递归创建//括号里的指针ﻩｏp=aｒray［ｃount］；ﻩﻩｃount++；ﻩﻩﻩbreak;ﻩﻩﻩ}ﻩｅlseﻩﻩﻩﻩ{ﻩﻩﻩﻩp-＞rChｉld=crtＴｒee(ｐ－＞rChild)；／/递归创//建括号里的指针ﻩﻩﻩﻩｏp=arｒaｙ[coｕnt];ﻩﻩﻩcoｕnt++;ﻩﻩﻩﻩｂreak;ﻩﻩ}ﻩcaｓe ')':rｅｔurｎroｏｔ;｝｝ﻩｒeｔurn root;}void oｕtpｕt(Noｄe*rｏot) //传入根结点,后/／序遍历历赋值给另一个字符数组（主要是//为了给后序的计算表达式值提供方便){ﻩint n;ﻩｉf(ｒooｔ)ﻩ{ﻩﻩoutpｕt(rｏｏｔ－>lChiｌd）;ﻩoutｐut(root-＞rChiｌd);ﻩﻩn=０；ﻩｗｈiｌe(ｒｏｏt->cｈ［ｎ]!='\0')ﻩstr[k+＋]=root－>ch［n＋+];ｓtr[k++]=' ';ﻩ}}bool isＥrror(ｃhar ch) //判断每个字符//是否有错｛ﻩiｆ(cｈ!='＋'&&ch!＝'-＇＆&cｈ!='*＇＆&ch！='／'&&!(ｃh<=＇9'&&ch>=＇０'）&&ch!＝'．'&&ch！=＇（'＆&ch!='）'）{ﻩcoｕt << "字符错误！";ﻩｒeturn truｅ;}rｅｔurn false;}voｉd deal（) //对字符数组进行处理｛ﻩint i=０,n＝０;ﻩwhiｌe(array［i］)ﻩ{ﻩif(arrａy[i]==＇'||arｒay［i］=＝'=') ﻩﻩi+＋;ﻩﻩarｒay[n＋+]=aｒray[i＋+];ﻩ｝array[n++］='='；aｒray[n]＝＇\0＇；}－-。

实验题目：中缀表达式转后缀表达式实验报告一、实验目的本实验旨在通过编写程序，掌握中缀表达式转后缀表达式的算法，并进行实际的转换操作，加深对中缀表达式和后缀表达式的理解，提高编程能力。

二、实验原理1. 中缀表达式：中缀表达式是我们平常常见的算术表达式，如 a + b * c。

2. 后缀表达式（逆波兰表达式）：后缀表达式是没有括号，而操作符号放在两个操作数之后的表达式，如 a b c * +。

中缀表达式转后缀表达式的算法步骤如下：- 从左到右遍历中缀表达式的每个数字和操作符；- 如果是数字，则直接输出到后缀表达式；- 如果是操作符，则将其与栈顶元素进行比较，如果比栈顶元素的优先级高或相等，则将栈顶元素弹出，输出到后缀表达式中，直到栈顶元素优先级低于该操作符，然后将该操作符压入栈中；- 遍历完中缀表达式后，将栈中的操作符依次弹出，输出到后缀表达式中。

三、实验过程1. 设计程序我们设计了一个简单的算法，实现中缀表达式转后缀表达式的功能。

我们采用了栈的数据结构来辅助转换过程，具体实现如下：```pythonclass InfixToPostfix:def __init__(self):self.stack = []self.output = []def is_higher_precedence(self, op1, op2):precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}return precedence[op1] >= precedence[op2]def convert(self, infix):for char in infix:if char.isalnum():self.output.append(char)elif char in '+-*/^':while self.stack andself.is_higher_precedence(self.stack[-1], char):self.output.append(self.stack.pop())self.stack.append(char)while self.stack:self.output.append(self.stack.pop())return ''.join(self.output)```2. 编写测试用例为了验证程序的正确性，我们编写了一系列的测试用例，包括简单的表达式（如 a+b*c）、带括号的表达式（如 (a+b)*c）、带有多位数的表达式（如 12+34*56）等多种情况。