逆波兰式转换规则的推导过程

由中缀表达式到后缀的逆波兰表达式转换时是数据结构课程教学中一个重点,许多教材只罗列了转换规则步骤,并未阐明其背后的原理.解释了中缀到后缀表达式的转换目的,利用递归的思想,并结合栈的应用得出转换规则.     

一种前缀表达式直接转换为后缀表达式的算法

栈是一种重要的线性结构。后缀表达式的运算规则具有"后进先出"的特点。为了帮助学生掌握这个重要的线性结构,深刻体会栈的结构特性,在教学过程中后缀表达式常作为栈的应用实例给学生进行讲解。针对目前前缀表达式转换为后缀表达式的常用方法存在的不足,提出了一种直接转换算法。此算法的时间复杂度为O(n),空间复杂度为O(n)。     

中缀算术表达式的轻量化求值算法

针对当前中缀算术表达式求值算法笨重或者复杂的问题,提出了一种轻量化的中缀算术表达式求值算法。该算法基于逆向拆分中缀算术表达式的思路,使用递归解析的方法,等价于中缀算术表达式的构造二叉树表示。实验结果表明,该算法与传统逆波兰表达式(RPN)转换、求值算法相比,该算法无需做逆波兰表达式转换,无需人工栈辅助,实现代码量仅有其1/6,而效率仅下降6.9%。与W3Eval算法相比,该算法无需符号转置表,支持算符自定义或重定义,实现代码量不到其1/2。该算法实现代价低,适用于Web应用的Browser端,及嵌入式应用等轻量化应用场合。     

基于互关联后继树的数学表达式检索

数学表达式结构复杂多样,给检索带来困难。为此,提出一种数学表达式索引与检索方法。在索引阶段,通过对LaTeX数学表达式特点的分析与归纳,定义面向表达式二维结构特性的数学表达式特征表示方式,将互关联后继树索引模型应用于数学表达式索引的构建,以解决树结构表示表达式的层次增长问题。在匹配阶段,设计包括精确匹配、相容匹配、子式匹配、模糊匹配等查询模式的匹配算法。在浏览器/服务器模式下采用51 076条数学表达式进行索引与匹配。实验结果表明,提出的方法可加快查询速度,减小索引存储空间,能够适应数学表达式的结构特点,取得较好的检索效果。     

LaTeX数学表达式解析与索引方法

针对数学表达式复杂二维结构特性所导致的普通文本检索技术难以对其进行检索的问题,提出了一种面向数学检索的LaTeX数学表达式解析与索引方法。在充分考虑公式特点的基础上,通过对LaTeX构成特点的分析和归纳,设计了LaTeX数学表达式的解析和检索特征提取算法;以此为基础,构建了一种适应数学表达式特性的双层索引结构,利用所提取数学表达式各层次运算数和运算符信息,分别以Treap数据结构和倒排索引结构构成数学表达式索引,为实现进一步的数学表达式检索匹配打下基础。在浏览器/服务器模式下采用6234条数学教材中的公式作为数据集进行实验,在解析获得的124960个基线层数最高为11层的表达式节点上,建立索引平均耗时为33.8317 s。实验结果表明所提出的LaTeX表达式解析算法和索引结构能够适应数学表达式的特点,有助于实现具有较高效率和准确性的数学表达式检索。     

基于编译原理的表达式计算器设计

通过对计算器功能的概述和算法的探讨,使用算符优先算法实现了表达式计算器.该表达式计算器能分析用户输入的表达式是否正确,支持括号运算、浮点运算、简单的四则运算、复杂的表达式运算、进制之间的相互转换等.该计算嚣操作简单,界面清晰.     

面向联机手写数学表达式的实时识别方法

数学表达式识别一般分为字符识别和结构分析两部分,而且大多数现有的方法是先进行字符识别然后将字符识别的结果作为结构分析的输入再进行结构分析,在这种分步识别的过程中,字符识别的错误会被继承到结构分析阶段,最终导致识别错误。关于数学表达式结构分析的问题,现有的方法大多是在假设所有的符号已经识别的基础上进行的。为了解决上述问题,提出了一种实时识别联机手写数学表达式的方法。该方法基于字符识别和结构分析的结合,动态地构建一棵数学表达式结构树来识别该数学表达式。在构建数学表达式树的过程中,采用了影响区域定位的方法,免去了其他不受影响区域的重复识别过程,因而提高了再次识别的效率,同时还弥补了现有实时识别方法不能乱序输入的缺陷。实验结果表明提出的方法可以得到比较满意的识别结果。     

中缀及后缀算术表达式在运算中的应用研究

表达式求值是程序设计语言编译中的一个最基本问题。与人们习惯的中缀表示的表达式相比,后缀表达式不存在括号,没有优先级的差别,表达式中各个运算是按照运算符出现的顺序进行的。因此非常适合串行工作的计算机处理方式。该文首先对这两种表达式表示方法进行了分析比较,然后通过具体分析实现这两种表达式求值的算法来论证表达式后缀表示优于中缀表示。最后简要谈一下中缀表达式到后缀表达式的转换。     

语言表达式到Petri网模型的转化及其算法

已知一个语言的表达式,直接构造产生该语言的Petri网模型是Petri网语言理论中一个重要问题.本文分析、研究同步交错正规表达式中各种运算与Petri网模型的对应转换关系,分别给出正规表达式、α闭包表达式到Petri网模型的转换方法;定义了Petri网的有界覆盖合成运算,研究有界覆盖合成网的语言性质,给出将同步交错正规表达式转换为Petri网模型的算法,从而实现了语言表达式到Petri网模型的等价转化.     

Tabular表达式的指称语义研究

Tabular 表达式是一种采用表格化结构组织函数或关系的形式化描述工具,在需求工程领域中具有广泛的应用,为Tabular 表达式建立形式的语义模型是非常必要的.针对Tabular 表达式通用模型,给出了Tabular 表达式的形式文法及指称语义.通过定义形式文法中各语法单元的语义指派方程,描述了Tabular 表达式的指称语义,分别对传统类型Tabular 表达式和新类型Tabular 表达式中一些典型表类型的指称语义进行了描述,并与其他几种Tabular 表达式的语义描述方法进行了比较.分析结果表明：该语义描述方法不仅准确描述了Tabular 表达式的语义,而且不再受Tabular 表达式模型和Tabular 表达式类型的限制,打破了现有方法的局限性,是一种非常有效的方法.     

出栈序列的研究

栈是一种非常重要的数据结构,递归、函数调用都离不开栈。对n个元素入栈和出栈的研究是栈的一个主要研究内容。利用二叉树给出了入栈和出栈序列的表示;给出了由前置O栈序列构造出二叉树的算法;证明了对于按次序入栈的n个元素,其出栈序列总数为C(2n,n)/(n 1);对三种求解出栈序列算法进行了分析和研究,并提出一种时间复杂度为O(n)判断某一序列是否为出栈序列的算法,它提高了程序的执行效率。     

一种基于二叉树的数学公式抄袭检测算法

提出了一种基于二叉树的LaTeX格式数学公式抄袭检测算法。在待检测文档中提取数学公式,根据数学公式的LaTeX格式生成其二叉树表示,对树形结构作归一化处理得到结构码;在公式检测库中查找文件名为该结构码的数据表,若该数据表存在,则在数据表中查找与二叉树根结点公式元素和变量名归一化的先序遍历序列都相同的记录;根据查找结果确定数学公式是否为抄袭。实验结果表明,该算法准确地实现了数学公式的抄袭检测,是一种较实用的算法。     

遗传编程的Matlab语言实现

引入堆栈技术,采用后缀表达式使遗传编程的树型结构易于转换为线性序列,并解决了初始个体生成算法、杂交算子操作、表达式个体求值等问题,使遗传编程不再依赖于专用编程语言和指针操作,能够方便地用Matlab语言实现。     

一种基于分块树的手写数学公式结构分析算法

本文源于一个手写数学公式识别系统,该系统实现了手写数学公式到文本公式的自动转化。文中提出了一种基于分块树的数学公式结构分析方法,该方法首先根据其内部结构特征将数学表达式分解为若干子模块,并采用树型结构对每个子模块内部字符之间的结构关系进行表示,最终形成整个表达式的树型表示。该方法定义了一系列的字符结构属性,将字符及属性值作为结构分析的结果,这些属性值再现了公式的结构特征,并很容易被系统的公式文本显示部分所利用。另外,该方法对传统的字符空间关系类型进行了简化,减小了识别误差,而引入的分块处理方式更加适合具有根式和分式等多层嵌套结构公式的处理,并且具有较强的可扩展性。     

中序遍历二叉树的教学方法研究

结合教学中学生难以理解与掌握中序遍历二叉树这一实际情况,本文提出利用下压法进行二叉树的中序遍历,同时,利用栈的思想推导中序遍历二叉树的递归算法和非递归算法,清晰直观,便于学生更好的学习与理解。     

一种改进的动态二进制树防碰撞算法

在无线射频识别系统（RFID）中,标签的防碰撞问题是必须解决的关键问题之一。针对现有RFID系统中动态二进制树搜索算法识别效率较低、通信复杂度较高的问题,提出一种改进的动态二进制树防碰撞算法,在标签内设置一个计数器记录匹配位置信息,阅读器根据碰撞信息的高位与次高位产生下一级搜索前缀,并通过堆栈保存各搜索深度的前缀,从而减少搜索次数并降低数据通信量。经仿真分析表明,该算法在识别效率和通信复杂度两方面具有明显的优势。     

基于平衡因子的AVL树设计实现

平衡二叉树又称AVL树,得名于它的发明者G．M．Adelson—Velsky和E．M．Landis。作为一种常用的数据结构,许多教科书都详细描述了实现的算法,但是基本都是根据不同树形LL、RR、LR、RL给出相应逻辑,而且都是直接给出结论。而文中则以平衡因子为出发点,揭示了不同树形的一致性算法,第一次以数学公式推演,论证了AVL插入和删除操作在不同树形情况下,哪个节点开始失去平衡,怎么平衡以及哪个节点平衡结束,并给出算法的完整实现代码,使AVL的实现一致、简单、易懂。     

基于唯一二叉树的XML函数表达式标识转换

针对在不同XML语言产品间实现函数计算表达式转换比较复杂的问题,提出在构建函数表达式对应二叉树结构的基础上,通过在XML文档属性设置中用中序、前序遍历序列对二叉树结构进行唯一标识,使其他XML语言产品实现通用解析,阐述XML函数表达式的解析和转换中的关键技术。该方法能提高XML函数表达式转换的通用性,并提高转换效率。     

数据结构中二叉树的生成及遍历非递归算法浅析

本文主要介绍数据结构中二叉树的生成,以及二叉树的先序、中序和后序的非递归算法。     

基于GPU快速光线跟踪算法的设计与实现

设计和实现了GPU上基于流的光线跟踪算法，采用一种基于线索二叉树的KD-Tree结构组织场景，避免了传统KD-Tree结构在遍历场景时在堆栈上的开销。算法在组织复杂场景上，优于利用传统KD-Tree和均匀剖分结构加速场景遍历的方法，在普通PC上实现了光线跟踪的快速渲染。