下载文档原格式
数据库技术知识数据结构的算法对于将要参加计算机等级考试的考生来说，计算机等级考试的知识点辅导是非常重要的复习资料。
以下是收集的数据库技术知识数据结构的算法，希望大家认真阅读!1、数据：数据的基本单位是数据元素。
数据元素可由一个或多个数据项组成。
数据项是数据的不可分割的最小单位2、数据结构：数据的逻辑结构、数据的存储结构、数据的运算3、主要的数据存储方式：顺序存储结构(逻辑和物理相邻，存储密度大)和链式存储结构顺序存储结构：顺序存储计算公式Li=L0+(i-1)×K顺序结构可以进行随机存取;插人、删除运算会引起相应节点的大量移动链式存储结构：a、指针域可以有多个，可以指向空，比比顺序存储结构的存储密度小b、逻辑上相邻的节点物理上不一定相邻。
c、插人、删除等不需要大量移动节点4、顺序表：一般情况下，若长度为n的顺序表，在任何位置插入或删除的概率相等，元素移动的平均次数为n/2(插入)和(n-1)/2(删除)。
5、链表：线性链表(单链表和双向链表等等)和非线性链表线性链表也称为单链表，其每个一节点中只包含一个指针域，双链表中，每个节点中设置有两个指针域。
(注意结点的插入和删除操作)6、栈：“后进先出”(LIFO)表。
栈的应用：表达式求解、二叉树对称序周游、快速排序算法、递归过程的实现等7、队列：“先进先出”线性表。
应用：树的层次遍历8、串：由零个或多个字符组成的有限序列。
9、多维数组的顺序存储：10、稀疏矩阵的存储：下三角矩阵顺序存储其他常见的存储方法还有三元组法和十字链表法11、广义表：由零个或多个单元素或子表所组成的有限序列。
广义表的元素可以是子表，而子表的元素还可以是子表12、树型结构：非线性结构。
常用的树型结构有树和二叉树。
二叉树与树的区别：二叉树不是树的特殊情况，树和二叉树之间最主要的区别是：二叉树的节点的子树要区分左子树和右子树，即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。
数据结构：线性结构—栈实现表达式求值一．问题分析利用栈这种数据结构存储数字和运算符，并实现表达式求值。
为实现按运算符优先顺序进行计算，需要在执行程序的过程中对运算符的优先顺序做出判断。
利用栈先进后出的特点，同时保证优先级最高的运算符始终在栈顶。
当栈顶元素优先级低于读入的运算符时，将该栈顶运算符推出。
这就保证了优先级高的运算符先计算。
二．数据结构—栈1.优先关系表：prior[7][7]={// +-*/()#'>','>','<','<','<','>','>','>','>','<','<','<','>','>','>','>','>','>','<','>','>','>','>','>','>','<','>','>','<','<','<','<','<','=',' ','>','>','<','>',' ','>','>','<','<','<','<','<',' ','='};将关系表直接用字符型的二维数组存储。
ＸＸXＸXX大学《数据结构》课程设计报告班级：学号：姓名：指导老师:目录一算术表达式求值一、需求分析二、程序得主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码二感想体会与总结算术表达式求值一、需求分析一个算术表达式就是由操作数(oｐeranｄ）、运算符(operator）与界限符（deｌimiter)组成得。
假设操作数就是正整数，运算符只含加减乘除等四种运算符,界限符有左右括号与表达式起始、结束符“#”，如：＃(7+15）*（2３—２8/４）#。
引入表达式起始、结束符就是为了方便.编程利用“算符优先法”求算术表达式得值.二、程序得主要功能（1）从键盘读入一个合法得算术表达式，输出正确得结果。
(2）显示输入序列与栈得变化过程。
三、程序运行平台Ｖｉsｕaｌ C＋+6、0版本四、数据结构本程序得数据结构为栈。
（1）运算符栈部分：struct SqStaｃk ／/定义栈{char *base； //栈底指针ｃｈａr *toｐ; ／/栈顶指针inｔstacｋsiｚe； //栈得长度};inｔInitSｔack (SqＳｔack &ｓ) //建立一个空栈S{ｉf （!(s、ｂａse= (char ＊）ｍalloc(5０＊ｓizeof（chａr）)）)exｉt（0）；ｓ、ｔop=s、bａse;s、staｃksiｚｅ=５0；retuｒn OK；}ｃhar GeｔTop（SqStack s,char &e) /／运算符取栈顶元素｛iｆ (s、ｔop==s、ｂase) //栈为空得时候返回EＲROR｛ﻩ prｉntf(＂运算符栈为空！＼n")；ﻩ reｔurn ERＲＯR;｝elsee＝*（s、ｔoｐ-1); //栈不为空得时候用ｅ做返回值，返回S得栈顶元素，并返回OK returnＯＫ;｝ｉnt Push(SqStacｋ＆s，cｈａr ｅ） //运算符入栈｛if （s、tｏp—s、baｓe >= ｓ、ｓtacksｉzｅ）ﻩ{ｐriｎtf（＂运算符栈满!＼n"）;ﻩs、basｅ=（cｈaｒ*）reａlloｃ(s、bａｓe，(s、sｔackｓｉze+5)*ｓizeoｆ(cｈar））；//栈满得时候,追加5个存储空间ｉf(！s、basｅ)exｉt （OVERＦＬOW）；s、top=s、ｂａsｅ+s、ｓｔacｋsize;s、ｓtaｃksiｚｅ+=５;}ﻩ＊(s、ｔop）＋＋=e；／/把e入栈ﻩｒeturn OK;}ｉnｔ Pop(SqStaｃk &ｓ，char ＆ｅ） /／运算符出栈｛ｉｆ (s、toｐ==s、base) ／/栈为空栈得时候，返回ERＲOＲ｛ｐrintf（＂运算符栈为空!\n”）;ﻩ return ERROＲ;}else｛ﻩﻩe=＊-—ｓ、tｏp；/／栈不为空得时候用e做返回值，删除S得栈顶元素，并返回ＯK return OK；}}iｎt StackTｒaｖerse（ＳqStacｋ&ｓ)／/运算符栈得遍历｛ﻩchar ＊t；ﻩt=s、ｂａｓｅ；ﻩif (s、top＝=s、baｓe）｛ﻩ printｆ（”运算符栈为空！\ｎ”)； //栈为空栈得时候返回ＥＲRORｒeturn ERＲOＲ;}ｗhile（t！＝s、tｏp)｛ﻩﻩｐrｉｎｔf（" %c",＊t)； //栈不为空得时候依次取出栈内元素t++;ﻩ}ｒeturｎ EＲRＯR；｝（2）数字栈部分：strｕｃt SqSｔackn//定义数栈｛ｉnt *bａse; //栈底指针ｉnt＊tｏp； //栈顶指针ｉnｔ sｔacksｉze； //栈得长度｝;inｔIｎｉtStackｎ (SqSｔackn &s) //建立一个空栈Ｓ{s、base=（int＊）malｌoc（50*sｉzeof(int）);if(！ｓ、ｂase）eｘiｔ（OVEＲFLＯW）；//存储分配失败s、top=s、base；s、stacksizｅ=5０;reｔuｒn OK；｝ｉｎt GｅtToｐn(ＳqＳtａcｋn s,inｔ＆e) //数栈取栈顶元素{if（s、ｔop=＝s、base）{prinｔｆ(＂运算数栈为空!\ｎ＂);//栈为空得时候返回ERRORﻩ rｅturｎ ERROR;}eｌseﻩe＝＊（s、toｐ-1);／/栈不为空得时候，用e作返回值，返回S得栈顶元素，并返回OＫreturｎＯK；｝int Pｕshn（SｑStａckn ＆s，int ｅ) //数栈入栈｛if（s、tｏp—s、ｂasｅ＞＝s、stacksiｚe)｛ﻩﻩprｉｎｔf（"运算数栈满!\ｎ"）；／/栈满得时候,追加5个存储空间ﻩs、base=(int＊）realloc (s、baｓe,(s、stａcksize＋5)＊sｉzｅof（ｉnt));ｉf（!s、base) ｅxit (ＯＶERFLOW)；ﻩs、top=ｓ、bａsｅ＋ｓ、stacｋsize;//插入元素e为新得栈顶元素s、stacksｉｚe+=5；}*（s、top）++=e; /／栈顶指针变化returｎOK;}ｉｎt Popｎ(ＳｑSｔacｋn ＆s，iｎt &e)//数栈出栈｛ﻩif （s、top=＝ｓ、base）｛ﻩ pｒiｎtｆ（"运算符栈为空！\n＂);//栈为空栈得视时候，返回ERRＯＲﻩ retｕrn ERROR；ﻩ｝ｅlse｛ﻩﻩe=＊—-ｓ、tｏp；／/栈不空得时候，则删除S得栈顶元素,用e返回其值，并返回OK ﻩreturｎOK；｝}ｉnt StacｋＴraveｒsｅn（SqStackn &s)/／数栈遍历{ﻩiｎｔ＊t;ﻩｔ=s、basｅ ;ﻩif（s、top==s、basｅ）ﻩ｛pｒinｔf(＂运算数栈为空！\n”）；//栈为空栈得时候返回ERRORﻩ rｅｔｕrn ERＲＯＲ；ﻩ｝ﻩwｈile（t！=ｓ、ｔop)ﻩ{priｎtf(” ％d”，*ｔ); /／栈不为空得时候依次输出t＋＋;｝return ERRＯR；｝五、算法及时间复杂度１、算法:建立两个不同类型得空栈,先把一个‘＃’压入运算符栈。
表达式求值(数据结构)表达式求值(数据结构)1.引言在计算机科学中，表达式求值是一项重要的任务。
它涉及解析和计算数学或逻辑表达式，以得出最终结果。
表达式可以包括数字、变量、运算符和函数，通过采用特定的计算规则，我们可以将这些表达式转化为具体的数值或逻辑结果。
2.表达式的基本概念2.1 数字在表达式中，数字是最基本的元素。
可以是整数或浮点数，用于进行算术计算。
2.2 变量变量是用于存储和代表值的符号，它可以在表达式中使用。
变量可以通过赋值操作来获得具体的值，在表达式求值过程中，变量会被相应的数值替换。
2.3 运算符运算符是用于执行特定操作的符号。
常见的算术运算符包括加法(+), 减法(-), 乘法和除法(/）逻辑运算符包括与(&&), 或(--------) 和非(!）在表达式求值中，运算符的优先级和结合性规则是非常重要的。
2.4 函数函数是一段封装了特定功能的代码块，可以接受输入参数并返回一个结果。
在表达式中，函数可以用于处理特定的数据操作或算法。
例如，sin(x) 和cos(x) 是常见的三角函数。
3.表达式求值的步骤3.1 词法分析首先，需要对表达式进行词法分析，将表达式分解为一个个的词法单元，例如数字、变量、运算符和函数等。
词法分析可以使用正则表达式或者逐字符扫描的方式进行。
3.2 语法分析在得到词法单元序列后，需要进行语法分析，根据语法规则验证表达式的结构是否正确。
语法分析可以使用自顶向下的LL(1)分析方法或者自底向上的LR分析方法。
3.3 语义分析一旦表达式的结构验证通过，就需要进行语义分析。
语义分析的任务是根据语法树运用特定的求值规则，将表达式转换为具体的数值或逻辑结果。
在语义分析过程中，需要处理变量的赋值和函数的调用。
4.表达式求值的例子为了更好地理解表达式求值的过程，以下是一个例子：________表达式：________ 2 (3 + 4) ●5 / 24.1 词法分析：________将表达式分解为以下词法单元：________ 数字(2, 3, 4, 5), 运算符(, +, -), 括号(), 除法运算符(/)4.2 语法分析：________根据语法规则验证表达式的结构是否正确，构建语法树：________-/ \\// \\ / \\2 + 5 2/ \\3 44.3 语义分析：________根据语法树使用求值规则，依次计算每个节点的值：________●节点：________ 2 (7) ●5 / 2●节点：________ 2 7 ●5 / 2●节点：________ 14 ●5 / 2●节点：________ 14 ●2.5●最终结果：________ 11.55.附件本文档没有涉及附件。
二叉树计算表达式计算表达式是计算机科学中常见的任务，而二叉树是一种常用的数据结构，用于表示表达式。
本文将介绍二叉树如何表示和计算表达式。
一、二叉树表示表达式二叉树是由节点和边组成的树状结构。
每个节点都包含一个值和两个指向左右子节点的指针。
二叉树可以用来表示数学表达式。
例如，下面是一个包含加、减、乘、除的表达式：```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。
三、扩展上面的例子说明了如何将表达式转为二叉树，并计算表达式的值。
但实际中会有更复杂的表达式，如函数调用、变量引用等。
数据结构实验报告（第三章）实验类型：综合性实验班级：学号：姓名：实验日期：2014年5月24日一、表达式求值1.问题描述表达式是数据运算的基本形式。
人们的书写习惯是中缀式，如：11+22*(7-4)/3。
中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。
表达式还有后缀式（如：22 7 4 - * 3 / 11 +）和前缀式（如：+ 11 / * 22 – 7 4 3）。
后缀表达式和前缀表达式中没有括号，给计算带来方便。
如后缀式计算时按运算符出现的先后进行计算。
本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。
2.基本要求●从文件或键盘读入中缀表达式。
●设计操作数为多位整数，操作符为加、减、乘、除、求模的中缀表达式求值算法。
●设计将中缀表达式转换为后缀表达式的算法。
●设计将中缀表达式转换为前缀表达式的算法。
●设计后缀表达式求值算法。
●设计前缀表达式求值算法。
●输出各种形式的表达式。
3.数据结构设计任何一个表达式都是由操作符，运算符和界限符组成的。
我们分别用顺序栈来寄存表达式的操作数和运算符。
栈是限定于紧仅在表尾进行插入或删除操作的线性表。
顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，base为栈底指针，在顺序栈中，它始终指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1，删除栈顶元素时，指针top减1。
typedef struct{int *base;int *top;int numstacksize; //数字栈}numstack;typedef struct{char *base;char *top;int charstacksize;//字符栈}charstack;4.算法设计（1）中缀表达式求值1.从左到右读入中缀表达式，每次一个字符。
2.如果是操作数，压入操作数栈。
需求分析(附代码)一、需求分析（1）首先定义两个栈OPTR、OPND，栈OPTR用于存放运算符，栈OPND 用于存放操作数；定义一个一维数组expr【】存放表达式串。
（2）主函数主要包括两部分：（1）判断运算符优先权，返回优先权高的；（2）操作函数。
（3）开始将‘#’入操作符栈，通过一个函数来判别算术运算符的优先级。
且规定‘#’的优先级最低。
在输入表达式的最后输入‘#’，代表表达式输入结束。
在表达式输入过程中，遇操作数则直接入栈。
遇到运算符则与栈顶运算符比较优先级,当前运算符优先级高(前面的运算还不应执行)则当前运算符入栈,扫描下一符号;否则栈顶运算符出栈,两操作数出栈,进行运算,所得结果入数栈,重新比较当前运算符(注意当前运算符未变)与新栈顶运算符。
如此重复直到栈顶运算符与当前符号均为‘#’，运算结束。
（4）最初实现的加、减、乘、除及带小括号的基本运算，但考虑到实用性，后来的设计中有加上了乘方运算。
在乘方运算中借用了C库中自带的乘方函数pow。
二、概要设计1、设定栈的抽象数据类型定义：ADT Stack {数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }数据关系：R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n }约定an 端为栈顶，a1 端为栈底。
基本操作：InitStack(&S)操作结果：构造一个空栈S。
DestroyStack(&S)初始条件：栈S 已存在。
操作结果：栈S 被销毁。
StackEmpty(S)初始条件：栈S 已存在。
操作结果：若栈S 为空栈，则返回TRUE，否则FALE。
StackLength(S)初始条件：栈S 已存在。
操作结果：返回S 的元素个数，即栈的长度。
GetTop(S, &e)初始条件：栈S 已存在且非空。
操作结果：用e 返回S 的栈顶元素。
ClearStack(&S)初始条件：栈S 已存在。
一、设计思想（一）先将输入的中缀表达式转为后缀再计算的设计思想我们所熟知的计算表达式为中缀表达式，这之中包含运算符的优先级还有括号，这对我们来说已经习以为常了，但是在计算机看来，这是非常复杂的一种表达式。
因此我们需要有一种更能使计算机理解的不用考虑优先级也不包括括号的表达式，也就是后缀表达式。
我们可以借助栈将其实现。
首先，我们需要将中缀表达式转换为后缀表达式，这也是这个算法的关键之处。
我们将创建两个栈，一个是字符型的，用来存放操作符；另一个是浮点型的，存放操作数。
接着，开始扫描输入的表达式，如果是操作数直接进入一个存放后缀表达式的数组，而操作符则按照优先级push进栈（加减为1，乘除为2），若当前操作符优先级大于栈顶操作符优先级或栈为空，push进栈，而当其优先级小于等于栈顶操作符优先级，则从栈内不断pop出操作符并进入后缀表达式数组，直到满足条件，当前操作符才能push 进栈。
左括号无条件入栈，右括号不入栈，而不断从栈顶pop出操作符进入后缀表达式数组，直到遇到左括号后，将其pop出栈。
这样当扫描完输入表达式并从操作符栈pop 出残余操作符后并push进栈，后缀表达式数组中存放的就是我们所需要的后缀表达式了。
扫描后缀表达式数组，若是操作数，将其转换为浮点型push进数栈；若是操作符，则连续从数栈中pop出两个数做相应运算，将结果push进数栈。
当扫描完数组后，数栈顶便为最终结果，将其pop出，输出结果。
（二）一边扫描一边计算的设计思想由于第一种算法需要进行两遍扫描，因此在性能上不会十分优秀。
而此种算法只用扫描一遍，当扫描完输入的表达式后便可以直接输出最终结果。
是第一种算法的改进版，性能上也得到提升，与第一种算法所不同的是其需要同时使用两个栈，一个操作符栈，一个数栈。
当扫描表达式时，若是操作数则将其转换为浮点型后直接push进数栈，而若是操作符则按照优先级规则push进操作符栈（加减为1，乘除为2），若当前操作符优先级大于栈顶操作符优先级或栈为空，push进栈，而当其优先级小于等于栈顶操作符优先级，则从栈内不断pop出操作符，直到满足条件，当前操作符才能push进栈。
左括号无条件入栈，右括号不入栈，而不断从栈顶pop出操作符，直到遇到左括号后，将其pop出栈。
这中间pop出操作符后直接从数栈中pop出两个数并计算，将结果push进数栈。
括号的处理与第一个算法相同。
扫描完成后，从操作符栈pop出残余操作符，从数栈中pop出两个数并计算并进行计算，将结果push进数栈。
数栈顶便为最终结果，将其pop出，输出结果。
两种算法各有各的优缺点，第一种算法过程比较清晰，使我们能够更加容易理解栈的使用规则，但是其性能不如第二种。
第二种算法相比第一种来说性能提高了，但是理解起来就不如第一种那么清晰了。
二、算法流程图以下是先将输入的中缀表达式转为后缀再计算算法：图1 中缀转后缀算法流程图以下是一边扫描一边计算算法：图2一边扫描一边计算算法流程图三、源代码以下为先将输入的中缀表达式转为后缀再计算算法代码：#include "stdio.h"#include "stdlib.h"/*定义存放操作符的结构体*/struct OpStrack{char op[100];/*存放操作符的数组*/int top;/*栈顶索引*/int level[100];/*存放操作符优先级的数组*/}OpStrackArray;/*定义存放语素的结构体*/struct OdStrack{float od[100];/*存放操作数的数组*/int top;/*栈顶索引*/}OdStrackArray;/*声明需要用到的函数*/int judge(char,char[],int,int);int stackIsEmpty();void pushOp(char,int);char popOp();void pushOd(float);float popOd();void compute(char);/*主函数*/void main(){char data[100];/*声明存放中缀表达式的字符串*/char tempdata[200];/*声明存放后缀表达式的字符串*/int i=0;/*作为遍历字符串的索引*/int j=0;/*作为输出后缀表达式的索引*/int z=0;/*作为存放后缀表达式的索引*/int k=0;/*作为将后缀表达式赋给临时转float的索引*/int eq=0;/*判断括号是否正确的条件*/float result;/*声明存放最终结果的float*/scanf("%s",data);/*输入中缀表达式*//*中缀转后缀，并将结果放入tempdata*/while(data[i]!='\0'){if((data[i]>='0'&&data[i]<='9')||data[i]=='.')/*如果是语素则存放至temp数组*/{tempdata[z]=data[i];z++;}else{switch(data[i]){case '+':z+=judge(data[i],tempdata,i,1);break;case '-':z+=judge(data[i],tempdata,i,1);/*加减优先级为1*/break;case '*':z+=judge(data[i],tempdata,i,2);/*乘除优先级为2*/break;case '/':/*返回出栈操作符的数量，以便将z索引向后推相应步*/z+=judge(data[i],tempdata,i,2);break;case '(':pushOp(data[i],-1);/*'('直接入栈，但入栈后优先级最小*/eq++;/*有一个'('eq+1*/break;case ')':while(OpStrackArray.op[OpStrackArray.top-1]!='(')/*')'不入栈*/{/*不断弹出操作符并进入后缀表达式数组，直到遇到'('*/tempdata[z]=popOp();z++;/*索引+1*//*如果发现还没碰到与之匹配的'('时栈已空则说明表达式不合法*/ if(stackIsEmpty()==1){printf("Expression is not valid!Press any key to continue...");getch();return;}}popOp();/*弹出'('*/eq--;/*如有与'('配队的')'则eq-1*/break;}}i++;}if(eq!=0)/*如果eq!=0说明'('与')'不能完全配队，输入的表达式不合法*/{printf("Expression is not valid!Press any key to continue...");getch();return;}/*将操作符栈内存留的操作符放入tempdata*/while(stackIsEmpty()==0){/*如果操作符栈不空则不断弹出操作符并进入后缀表达式数组*/tempdata[z]=popOp();z++;}/*扫描后缀表达式，计算后放入操作数栈*/while(k<z){char temp[20]={'\0'};/*声明临时的存放操作数的数组并附初值*/int t=0;/*作为temp数组的索引*/float f;/*存放转换为float的数*//*如果是语素则存放至temp数组*/while((tempdata[k]>='0'&&tempdata[k]<='9')||tempdata[k]=='.'){temp[t]=tempdata[k];k++;t++;}if(temp[0]!='\0')/*判断temp数组是否为空，是则将其转换为float并压栈*/ {f=atof(temp);/*字符串转float*/pushOd(f);/*操作数入栈*/}if(tempdata[k]=='+'||tempdata[k]=='-'||tempdata[k]=='*'||tempdata[k]=='/'){compute(tempdata[k]);/*如果扫描到操作符则作相应计算*/ }k++;}/*输出后缀表达式*/printf("The postfix expression is:");for(j=0;j<z;j++){printf("%c",tempdata[j]);}printf("\n");/*从操作数栈内弹出最终结果并输出*/result=popOd();printf("The result is:%.2f",result);/*结果取两位小数*/printf("\n");printf("Press any key to continue...");getch();}/*判断操作符优先级并作出相应处理，返回出栈操作符数量*/int judge(char op,char tempdata[],int index,int level){int cont=0;if(stackIsEmpty()==1||OpStrackArray.level[OpStrackArray.top-1]<level){/*如果栈为空或栈顶操作符优先级小于当前操作符优先级则将其压栈*/pushOp(op,level);cont++;/*使z索引向后推1*/}else{while(stackIsEmpty()!=1&&OpStrackArray.level[OpStrackArray.top-1]>=level){/*操作符不断出栈并入后缀表达式数组直到栈为空或栈顶操作符优先级大于等于当前操作符优先级*/tempdata[index]=popOp();index++;/*后缀表达式数组索引+1*/cont++;/*出栈操作符数量+1*/}pushOp(op,level);/*将当前操作符压栈*/}return cont;}/*判断操作符栈是否为空，是则返回1，否返回0*/int stackIsEmpty(){if(OpStrackArray.op[0]=='\0'){return 1;}return 0;}/*将操作符压入栈*/void pushOp(char op,int level){OpStrackArray.op[OpStrackArray.top]=op;/*操作符进入数组*/OpStrackArray.level[OpStrackArray.top]=level;/*为对应操作符附优先级*/ OpStrackArray.top++;/*top索引+1*/}/*操作符出栈，返回栈顶操作符*/char popOp(){char c=OpStrackArray.op[OpStrackArray.top-1];/*取得栈顶操作符*/OpStrackArray.op[OpStrackArray.top-1]='\0';/*分别将op数组与level数组还原为默认值*/OpStrackArray.level[OpStrackArray.top-1]=0;OpStrackArray.top--;/*top索引-1*/return c;/*返回栈顶操作符*/}/*将操作数压入栈*/void pushOd(float f){OdStrackArray.od[OdStrackArray.top]=f;/*操作数进入数组*/OdStrackArray.top++;/*top索引+1*/}/*操作符出栈，返回栈顶操作数*/float popOd(){float f=OdStrackArray.od[OdStrackArray.top-1];/*取得栈顶操作数*/OdStrackArray.od[OdStrackArray.top-1]=0.0;/*将od数组还原为默认值*/ OdStrackArray.top--;/*top索引-1*/return f;/*返回栈顶操作数*/}/*根据传入操作符运算，并将结果压入操作数栈*/ void compute(char op){float tempresult;/*临时计算结果*/float od1=popOd();float od2=popOd();/*连续pop出两个操作数*/switch(op)/*根据传入操作符计算*/{case '+':tempresult=od2+od1;break;case '-':tempresult=od2-od1;break;case '*':tempresult=od2*od1;break;case '/':tempresult=od2/od1;break;}pushOd(tempresult);/*将计算结果压栈*/}以下为一边扫描一边计算算法代码：#include "stdio.h"#include "stdlib.h"/*定义存放操作符的结构体*/struct OpStrack{char op[100];/*存放操作符的数组*/int top;/*栈顶索引*/int level[100];/*存放操作符优先级的数组*/}OpStrackArray;/*定义存放语素的结构体*/struct OdStrack{float od[100];/*存放操作数的数组*/int top;/*栈顶索引*/}OdStrackArray;/*声明需要用到的函数*/void pushOp(char,int);char popOp();void pushOd(float);float popOd();int stackIsEmpty();void judge(char,int);void compute(char);/*主函数*/void main(){char data[100];/*声明存放中缀表达式的字符串*/int i=0;/*作为遍历字符串的索引*/int eq=0;/*判断括号是否正确的条件*/float result;/*声明存放最终结果的float*/scanf("%s",data);/*输入中缀表达式*//*扫描输入的表达式并作出相应处理*/while(data[i]!='\0'){char temp[20]={'\0'};/*声明临时的存放操作数的数组并附初值*/int j=0;/*作为temp数组的索引*/float f;/*存放转换为float的数*/while((data[i]>='0'&&data[i]<='9')||data[i]=='.')/*如果是语素则存放至temp数组*/{temp[j]=data[i];j++;i++;}if(temp[0]!='\0')/*判断temp数组是否为空，是则将其转换为float并压栈*/{f=atof(temp);/*字符串转float*/pushOd(f);/*操作数入栈*/}switch(data[i]){case '+':judge(data[i],1);break;case '-':judge(data[i],1);/*加减优先级为1*/break;case '*':judge(data[i],2);break;case '/':judge(data[i],2);/*乘除优先级为2*/break;case '(':pushOp(data[i],-1);/*'('直接入栈，但入栈后优先级最小*/eq++;/*有一个'('eq+1*/break;case ')':while(OpStrackArray.op[OpStrackArray.top-1]!='(')/*')'不入栈*/{compute(popOp());/*不断弹出操作符并计算，直到遇到'('*//*如果发现还没碰到与之匹配的'('时栈已空则说明表达式不合法*/ if(stackIsEmpty()==1)/{printf("Expression is not valid!Press any key to continue...");getch();return;}}popOp();/*弹出'('*/eq--;/*如有与'('配队的')'则eq-1*/break;}i++;}/*扫描操作符栈内残余操作符并做相应计算*/while(stackIsEmpty()==0){compute(popOp());/*如果操作符栈不空则弹出操作符并计算*/}/*从操作数栈内弹出最终结果并输出*/if(eq==0)/*如果eq=0说明'('与')'可以完全配队，输入的表达式合法*/{result=popOd();printf("The result is:%.2f",result);/*结果取两位小数*/}else/*如果eq!=0说明'('与')'不能完全配队，输入的表达式不合法*/{printf("Expression is not valid!Press any key to continue...");}printf("\n");printf("Press any key to continue...");getch();}/*将操作符压入栈*/void pushOp(char op,int level){OpStrackArray.op[OpStrackArray.top]=op;/*操作符进入数组*/OpStrackArray.level[OpStrackArray.top]=level;/*为对应操作符附优先级*/OpStrackArray.top++;/*top索引+1*/}/*操作符出栈，返回栈顶操作符*/char popOp(){char c=OpStrackArray.op[OpStrackArray.top-1];/*取得栈顶操作符*/OpStrackArray.op[OpStrackArray.top-1]='\0';OpStrackArray.level[OpStrackArray.top-1]=0;/*分别将op数组与level数组还原为默认值*/ OpStrackArray.top--;/*top索引-1*/return c;/*返回栈顶操作符*/}/*将操作数压入栈*/void pushOd(float f){OdStrackArray.od[OdStrackArray.top]=f;/*操作数进入数组*/OdStrackArray.top++;/*top索引+1*/}/*操作符出栈，返回栈顶操作数*/float popOd(){float f=OdStrackArray.od[OdStrackArray.top-1];/*取得栈顶操作数*/OdStrackArray.od[OdStrackArray.top-1]=0.0;/*将od数组还原为默认值*/OdStrackArray.top--;/*top索引-1*/return f;/*返回栈顶操作数*/}/*判断操作符栈是否为空，是则返回1，否返回0*/int stackIsEmpty(){if(OpStrackArray.op[0]=='\0'){return 1;}return 0;}/*判断操作符优先级作出相应处理*/void judge(char op,int level){if(stackIsEmpty()==1||OpStrackArray.level[OpStrackArray.top-1]<level){/*如果栈为空或栈顶操作符优先级小于当前操作符优先级则将其压栈*/pushOp(op,level);}else{while(stackIsEmpty()!=1&&OpStrackArray.level[OpStrackArray.top-1]>=level){/*操作符不断出栈并计算直到栈为空或栈顶操作符优先级大于等于当前操作符优先级*/ compute(popOp());}pushOp(op,level);/*将当前操作符压栈*/}}/*根据传入操作符运算，并将结果压入操作数栈*/void compute(char op){float tempresult;/*临时计算结果*/float od1=popOd();float od2=popOd();/*连续pop出两个操作数*/switch(op)/*根据传入操作符计算*/{case '+':tempresult=od2+od1;break;case '-':tempresult=od2-od1;break;case '*':tempresult=od2*od1;break;case '/':tempresult=od2/od1;break;}pushOd(tempresult);/*将计算结果压栈*/}四、运行结果图3中缀转后缀算法运算结果图4 一边扫描一边计算算法运算结果五、遇到的问题及解决这部分我主要遇到了如下几个问题，其内容与解决方法如下所列：中缀转后缀算法：●问题1：扫描完成后输出的后缀表达式会带有’(’，从而导致计算不正确。
