CN101055568A

CN101055568A - 一种电子数据表的计算方法和装置

Info

Publication number: CN101055568A
Application number: CN 200710105710
Authority: CN
Inventors: 乔昕明
Original assignee: Kingdee Software China Co Ltd
Current assignee: Kingdee Software China Co Ltd
Priority date: 2007-05-25
Filing date: 2007-05-25
Publication date: 2007-10-17
Anticipated expiration: 2027-05-25
Also published as: CN100483396C

Abstract

本发明提供了一种电子数据表计算方法，创新的在电子数据表的计算过程中增加了堆栈操作，当电子数据表单元待计算时，将其压入堆栈，如果该单元公式中的某一项具有待计算支持单元，则中断该依赖单元的计算，先完成支持单元的计算，再根据支持单元的值完成该待计算依赖单元的计算。当支持单元又依赖其它支持单元时，再次重复以上步骤，直至能够完成待计算单元的计算。从而使所涉及的支持单元能够在依赖单元之前完成计算，避免了在计算过程中单元节点的移动，并能够避免冗余运算，对电子数据表计算效率的提高明显，节省了计算机系统资源。

Description

一种电子数据表的计算方法和装置

技术领域

本发明涉及电子数据表处理，特别是涉及一种对电子数据表进行计算的方法和装置。

背景技术

电子数据表(Spreadsheet)：是以单元形式来组织数据及信息的计算工具软件，譬如Microsoft Excel，Lotus1-2-3，Borland Quattro Pro，LinuxGnumeric，WPS表格，永中Office等等。

单元为电子数据表的最基本组成单元，其中可以包含计算公式，用以计算此单元的数值。电子数据表还可以预先设定或由二次开发者提供一些功能函数，这些函数可用于单元公式中，以方便用户使用。

传统的电子数据表如Microsoft Excel利用单个计算链处理电子数据表中公式的计算和重算，该计算链在本质上是被输入到Excel当前载入的所有工作表中的全部公式的有序列表。在公式被输入到电子表格时，该公式被添加到全局计算链的开始。当通过修改公式所依赖的单元的内容或手动请求重算操作触发重算(recalc)操作时，Excel将会循环访问计算链中，并重新计算已经被标记为“脏”(即，等待重算)的任何公式。如对单元C4＝A4+B4，代码从对第一个单元C4求值开始，在尝试对公式“＝A4+B4”求值时，计算代码发现，该公式依赖于单元A4，并且单元A4是“脏的”，即是说仍然要计算。在这一情况中，单元C4的公式“＝A4+B4”称为“依赖”公式，单元C4称为依赖单元，单元A4、B4称为支持单元，单元A4中的公式称为“支持”公式。代码停止对公式＝A4+B4求值，将单元A4的公式压入计算链，并将其再次插入到紧靠在单元C4的公式之前。然后，计算代码从单元A4的公式开始，重新开始其工作。毫无问题，计算代码对A4求值，转移到C4。在尝试对公式＝A4+B4求值时(第二次)，计算代码得知A4现在已经被计算(不再“脏”)，但发现公式也依赖于单元B4，并且B4也是“脏”的。这样，代码再次停止对该公式求值，并将B4的公式移到紧靠在C4的公式之前。然后，毫无问题，代码对B4求值，并转移到C4(现在是第三次)。现在可以对C4求值，完成该过程。

该所述计算方法会频繁移动原计算链中的节点，并导致C4公式冗余的两次计算。特别的，对于C4＝A4+B4+D4+E4+F4+G4+H4+I4，假设单元A4、B4、D4、E4、F4、G4、H4、I4都是“脏”的，则先把所有的单元节点移到单元C4前面，然后进行计算，在计算过程中，每遇到一个“脏”的单元，则把该“脏”单元计算完成后再重新计算C4，当遇到下一个“脏”单元时，前面的部分C4计算全部没用，引用计算到I4时才发现I4是“脏的”，前面的累加白费了，先算完I4再重来一遍，从而导致8次冗余计算。如果单元C4依赖更多的单元的话，所述节点的移动次数和冗余计算的次数则更多。对于极为复杂的电子数据表格，尤其在大型财务规划方案中，以上述方式完成长链式计算需要大量的处理时间，也会造成计算机系统资源的大量浪费。

因此，迫切需要一种对电子数据表进行计算的方法和装置，在对电子数据表的全部单元或部分单元进行计算时，不需要频繁的移动单元节点，减少冗余计算的次数。

发明内容

本发明所要解决的技术问题是提供一种电子数据表的计算方法和装置，可以大大提高电子数据表整体或局部的计算速度。

为了解决上述问题，本发明公开了一种电子数据表计算的方法，包括以下步骤：

a、将待计算单元压入堆栈；

b、判断该单元公式的第一项/下一项是否具有待计算支持单元，是则将该支持单元压入堆栈；否则对该单元公式的第一项/下一项直接求值；

c、对压入堆栈的支持单元按步骤b求值，完成后将该支持单元弹出堆栈；

d、重复步骤b、c，完成待计算单元的计算，并将该单元弹出堆栈。

依据另一实施例，还公开了一种电子数据表的计算方法，具体可以包括：

a、生成电子数据表的计算链；

b、按计算链的顺序进行第一/下一单元的计算，将该待计算单元压入堆栈；

c、判断该单元公式的第一项/下一项是否具有待计算支持单元，是则将该支持单元压入堆栈；否则对该单元公式的第一项/下一项直接求值；

d、对压入堆栈的支持单元按步骤c求值，完成后将支持单元弹出堆栈；

e、重复步骤c、d，完成待计算单元的计算，将该单元弹出堆栈，并返回步骤b，直到该计算链所有单元都计算完成。

优选的，步骤a所述电子数据表计算链的生成步骤包括：

a1、解析电子数据表各单元间的依赖关系；

a2、向计算链添加第一单元；

a3、根据依赖关系查询该单元的依赖单元，将所述依赖单元添加到计算链的尾部；

a4、根据依赖关系查询新添加单元的依赖单元，将所述新添加单元的依赖单元添加到计算链的尾部；

a5、重复步骤a4至计算链的最后一个单元；

a6、按照预置的遍历顺序将下一单元添加到计算链的尾部，对该单元按步骤a3、a4、a5完成计算链操作；

a7、重复步骤a6，得到电子数据表的计算链。

进一步，当计算链中已经存在要添加的单元时，不再添加该单元。

优选的，所述方法进一步可以包括：预设所述堆栈的容量临界值，当压入的单元个数达到临界值要发生堆栈溢出错误时，将压入堆栈中的各单元反序插入到计算链的待计算单元节点前，按照新的计算链重新计算。

依据另一实施例，本发明还公开了一种电子数据表的计算装置，可以包括：

堆栈，用于缓存电子数据表单元；

判断模块，判断压入堆栈的单元公式的第一项/下一项是否具有待计算支持单元，是则将该支持单元压入堆栈；否则对该单元公式的第一项/下一项直接求值；

计算模块，对新压入的单元重复调用判断模块，完成待计算单元的计算，并弹出该单元。

依据另一实施例，本发明还公开了另一种电子数据表的计算装置，可以包括：

堆栈，用于缓存电子数据表单元；

计算链生成模块，用于生成电子数据表的计算链；

进一步，该装置还可以包括：异常处理模块，当压入堆栈的单元个数达到堆栈的预设容量临界值时，将压入堆栈中的各单元反序插入到计算链的待计算单元节点前，生成新的计算链。

优选的，所述的计算链生成模块包括：解析模块，用于解析电子数据表各单元间的依赖关系；置入模块，用于向计算链添加单元；查询模块，用于根据解析模块查询电子数据表中单元的依赖单元；生成模块，用于调用置入模块添加电子数据表第一单元至计算链中，调用查询模块查询该单元的依赖单元，并再次调用置入模块将所述依赖单元添加到计算链的尾部；以及，针对新添加单元的依赖单元重复调用查询模块和置入模块，直到计算链的尾部；以及，针对电子数据表下一单元再次重复调用置入模块、查询模块，得到电子数据表的计算链。

优选的，对于计算链生成模块，当计算链中已经存在要添加的单元时，不调用置入模块添加该单元。

与现有技术相比，本发明具有以下优点：

本发明在电子数据表的计算过程中增加了堆栈操作，当电子数据表单元待计算时，将其压入堆栈，如果该单元公式中的某一项具有待计算支持单元，则中断该依赖单元的计算，先完成支持单元的计算，再根据支持单元的值完成该待计算依赖单元的计算。当支持单元又依赖其它支持单元时，再次重复以上步骤，直至能够完成待计算单元的计算。从而使所涉及的支持单元能够在依赖单元之前完成计算，避免了在计算过程中单元节点的移动，并能够避免冗余运算，对电子数据表计算效率的提高明显，节省了计算机系统资源。

进一步，在对电子数据表进行处理前，通过解析电子数据表各单元间的依赖关系，生成计算链，在该生成的计算链中，尽可能使被依赖单元位于依赖单元之前。生成计算链后，结合计算链和堆栈来完成电子数据表的计算，避免了在计算过程中单元节点的反复移动和冗余计算，大大提高电子数据表的计算效率，节省了计算机系统资源。

进一步，在堆栈操作中，当压入堆栈的单元数将要超过堆栈的容量时，即将发生调用堆栈溢出错误时，通过设定堆栈容量的临界值，主动抛出异常来抛弃当前函数调用堆栈，并且将当前堆栈中的单元倒序放到第一个求值单元之前，形成先计算被依赖者的计算顺序，按照新的计算链重新完成待计算单元的计算，从而能够顺利的完成电子数据表的计算。

附图说明

图1是本发明实施例一种电子数据表计算方法的流程图；

图2是本发明另一实施例一种电子数据表计算方法的流程图；

图3是本发明实施例优选的一种电子数据表计算链生成方法的流程图；

图4是本发明实施例一种电子数据表计算装置的结构框图；

图5是本发明实施例优选的一种电子数据表计算链生成系统的结构框图；

图6是本发明另一实施例一种电子数据表计算装置的结构框图。

具体实施方式

为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。

本发明的核心思想是在电子数据表的计算过程中采用堆栈操作，获取支持单元的内容的代码方法中调用支持单元的计算方法。当电子数据表单元待计算时，将其压入堆栈，如果有支持单元待计算，则中断该单元的计算，先完成支持单元的计算，再根据支持单元的值完成该待计算单元的计算。当支持单元依赖其它支持单元时，再次重复以上步骤，直至能够完成待计算单元的计算。从而使支持单元在依赖单元之前完成计算，避免了在计算过程中单元节点的反复移动，并能够避免冗余运算，对电子数据表计算效率的提高明显，节省了计算机系统资源。本发明进一步将电子数据表计算链的生成和堆栈操作结合在一起，即先构建电子数据表中各单元间的依赖关系。然后按照一定的遍历顺序向计算链中添加支持单元，查询该单元的依赖单元，将它们依次添加到计算链的尾部，从计算链中支持单元的第一个依赖单元开始，查询该单元的依赖单元，将它们依次添加到计算链的尾部；如此循环直到计算链尾部，从而将直接和间接依赖于支持单元的所有单元都添加进了计算链。按遍历顺序完成全部单元的添加，生成电子数据表的计算链。此时生成的整个计算链已经基本上保持了支持单元先进行计算的顺序。生成计算链后，结合计算链和堆栈来完成电子数据表的计算。

通过本发明，把边计算边生成计算链的方法，优化为先生成计算链，然后再根据该生成的计算链结合堆栈操作完成电子数据表的计算，避免在计算过程中单元节点的反复移动，并避免冗余运算，大大节省了计算机系统资源，提高了电子数据表的计算速度。

本发明可用于众多通用或专用的计算系统环境或配置中。例如：个人计算机、服务器计算机、手持设备或便携式设备、平板型设备、多处理器系统、基于微处理器的系统、置顶盒、可编程的消费电子设备、网络PC、小型计算机、大型计算机、包括以上任何系统或设备的分布式计算环境等等。

本发明可以在由计算机执行的计算机可执行指令的一般上下文中描述，例如程序模块。一般地，程序模块包括执行特定任务或实现特定抽象数据类型的例程、程序、对象、组件、数据结构等等。也可以在分布式计算环境中实践本发明，在这些分布式计算环境中，由通过通信网络而被连接的远程处理设备来执行任务。在分布式计算环境中，程序模块可以位于包括存储设备在内的本地和远程计算机存储介质中。

本发明所述的电子数据表的计算方法可以用于完成对电子数据表部分区域单元或单个单元的计算，还可以用于整张电子数据表的计算。

参照图1，示出了本发明一种电子数据表计算方法的流程图，包括以下步骤：

步骤101、将待计算单元压入堆栈。

许多处理系统具有存储器模块，在存储器模块中实现了堆栈。一个堆栈是一个数据结构。基中最近被保存的一个值被首先检索出来。有两个与一个堆栈相关的基本操作——一个压入操作，其中一个新的值被添加到堆栈中，和一个弹出操作，其中检索位于堆栈顶部的值。新的值被保存在堆栈顶部后面的一个存储器地址中。一般在中断中使用堆栈操作。在本发明中，所述值为电子数据表单元，通过堆栈实现待计算单元的中断操作。

步骤102、判断该单元公式的第一项是否具有待计算支持单元，是则将该支持单元压入堆栈；否则对该单元公式的第一项直接求值。

电子数据表通常由多个单元组成，这些单元相互之间有可能存在相互依赖的关系。如单元公式C4＝A4+B4，单元C4依赖于单元A4和单元B4，则所述单元C4为依赖单元，所述单元A4、B4为支持单元，A4+B4是单元C4的单元公式，其中A4是单元公式的第一项，B4是单元公式的第二/下一项，所述单元公式的项可以包括单元项，也可以包括常数或其他公式，本发明并不对此限定。单元A4、B4的公式是支持公式，A4+B4是依赖公式。在电子数据表中，依赖单元和支持单元并不是固定的，是可以相互转化的，即依赖单元可能是其他单元的支持单元。如D4＝C4+E4中，C4则是支持单元，D4是依赖单元。因此，在电子数据表中存在这样一种情况，一个支持单元的依赖单元是另一单元的支持单元。因为依赖单元依赖于支持单元，所以在电子数据表的计算等处理过程中，应该先对支持单元进行处理，当依赖单元的所有支持单元都处理后才能完成依赖单元的处理。

如果压入堆栈单元的单元公式的第一项依赖于其他单元，即该单元的值也是待计算时，则把该单元也压入堆栈。如果单元公式的第一项不是待计算单元，即该单元的值不需要计算即可以得到结果或者该单元的值是常数值时，则直接计算得到该结果值。

步骤103、判断步骤102中压入堆栈的单元是否还具有待计算支持单元，并按步骤102的步骤对该单元进行处理。

对于一个电子数据表单元来说，有可能存在这样的一种情况，单元间引用的嵌套层数比较多，如A单元引用B单元、B单元引用C单元、C单元引用D单元，在这样的情况中，单元A、B、C都是待计算单元。对于这种情况，本发明先把A压入堆栈，发现A单元待计算，且依赖于B单元，则再把B单元压入堆栈，又发现B单元待计算，且依赖于C单元，则再把C单元压入堆栈，C单元也待计算，且依赖于D单元，最后才发现D单元不是待计算单元，其值不需要计算就可直接得到，则通过D单元完成C单元的计算，并把C单元弹出堆栈，通过C单元完成B单元的计算，并把B单元弹出堆栈，最后通过B单元完成A单元的计算，将单元A弹出堆栈，从而通过堆栈完成了待计算单元A的计算。一直重复该步骤，从而对单元公式的项完成求值。

按步骤102、103完成待计算单元公式第一项的求值后，进行待计算单元公式下一项的求值，所述求值过程与步骤102、103相同，在此不再详述。

步骤104、完成待计算单元的计算，并将该单元弹出堆栈。

在步骤102、103中，待计算单元公式的各项的值都已经计算完成，根据各项的值完成该待计算单元的求值，并在求值完成后将该待计算单元弹出堆栈。

下面以一个例子对上述方法流程进行详细描述。

按照C4＝A4+B4这个例子：

第一步、将C4压入计算单元堆栈，开始公式计算；

第二步、计算到引用A4内容时发现A4待计算，将A4压入计算单元堆栈，计算完成A4，将A4弹出计算单元堆栈，去除A4“待计算”标志，继续C4计算；

第三步、计算到引用B4内容时发现B4待计算，将B4压入计算单元堆栈，计算完成B4，将B4弹出计算单元堆栈，去除B4“待计算”标志，继续C4计算；

第四步、C4计算完成，将C4弹出计算单元堆栈，去除C4“待计算”标志。

从总体上讲，本发明方法避免了单元节点在计算过程中的移动和冗余计算，提高了计算效率。本发明方法在电子数据表计算过程中增加了计算单元堆栈操作，相对于单元公式冗余计算的耗用来讲，代价是非常轻微的，电子数据表的整体计算效率有显著提升。

进一步，对于上述利用堆栈“获取被引用单元的内容的代码方法中调用被引用单元的计算方法”完成电子数据表单元的计算，如果引用的嵌套层数比较多，如A引用B、B引用C、C引用D……到引用N，会发生函数调用堆栈溢出错误。对于这种状况，通过设定计算单元堆栈容量临界值，主动抛出异常来解决。譬如如果引用嵌套510层会发生函数调用堆栈溢出错误，那就设定计算单元堆栈容量临界值为500，当堆栈要超出容量时，主动抛出异常，将函数调用返回到第一个求值单元A处。在异常处理中将当前计算单元堆栈中的单元倒序放到第一个求值单元A之前，从而形成了先计算被依赖者的计算顺序，可以继续正常计算。

参照图2，示出了本发明一种电子数据表计算方法的流程图，与图1所示方法的区别在于：本方法是结合计算链和堆栈完成电子数据表的计算。包括步骤：

步骤201、生成电子数据表的计算链。

电子数据表计算链的生成方法有很多，如按电子数据表中各单元的顺序生成电子数据表的计算链，所述顺序可以是先行后列或先列后行；边计算边生成计算链也是电子数据表计算链生成方法的一种，至于采用何种方法生成电子数据表的计算链，本发明并不对此进行限定。为了提高电子数据表的计算效率，本发明优先采用计算链生成方法的原理是：先构建电子数据表中各单元间的依赖关系，构建各单元间的依赖关系在不同的电子数据表的实现方式不同，但原理是相似的：当一个单元内容发生变化时要通知依赖此单元的其他单元，并更新各自的内容。然后按照一定的遍历顺序向计算链中添加支持单元，查询该单元的依赖单元，将它们依次添加到计算链的尾部，从计算链中支持单元的第一个依赖单元开始，查询该单元的依赖单元，将它们依次添加到计算链的尾部；如此循环直到计算链尾部，从而将直接和间接依赖于支持单元的所有单元都添加进了计算链。按遍历顺序完成全部单元的添加，生成电子数据表的计算链。此时生成的整个计算链已经基本上保持了支持单元先进行计算的顺序。

步骤202、按计算链的顺序进行第一/下一单元的计算，将该待计算单元压入堆栈。

按生成计算链中的各单元的顺序将第一/下一单元压入堆栈，如果计算链中的第一/下一单元能直接完成计算，则在完成计算后弹出该单元，如果计算链中的单元具有支持单元，不能直接完成计算，则转入步骤203。

步骤203、判断该单元公式的第一项/下一项是否具有待计算支持单元，是则将该支持单元压入堆栈；否则对该单元公式的第一项/下一项直接求值。

电子数据表通常由多个单元组成，这些单元相互之间有可能存在相互依赖的关系。

步骤204、判断步骤203中压入堆栈的单元是否还具有待计算支持单元，并按步骤203的方法对该单元进行处理。

按步骤203、204完成待计算单元公式第一项的求值后，进行待计算单元公式下一项的求值，所述求值过程与步骤203、204相同，在此不再详述。

步骤205、完成待计算单元的计算，并将该单元弹出堆栈。

在步骤203、204中，待计算单元公式的各项的值都已经计算完成，根据各项的值完成该待计算单元的求值，并在求值完成后将该待计算单元弹出堆栈。完成该待计算单元的计算后，对下一单元，返回步骤202，开始新一单元的计算。当电子数据表中所有单元都计算完成后，则不再返回步骤202。结束电子数据表的计算。

进一步，根据完成的电子数据表各单元的计算结果完成电子数据表全部或指定部分的计算。

进一步，对于上述利用堆栈完成电子数据表的计算，如果引用的嵌套层数比较多而发生堆栈计算溢出的情形。通过设定计算单元堆栈容量临界值，将压入堆栈中的各单元反序插入到计算链的待计算单元节点前，生成新的计算链的方法来解决堆栈溢出的错误。

如：a1＝a2，a2＝a3，a3＝a4，……，a1000＝a1001，计算链相应为：{a1，a2，a3，…，a1001}。

如果开始计算a1的话，会导致压栈a1(a2(a3(…(a1001))))，这实际是个函数压栈调用过程，对于现有计算环境，函数调用栈大小是有限制的，可能会发生超出调用栈导致栈溢出异常。

在这种情况下，设定堆栈容量临界值，主动捕获堆栈异常。如计算在510级时会发生堆栈溢出，则主动将堆栈容量临界值设为500。a1(a2(a3(…(a500))))时到达限值，这时停止当前单元格a1的计算，将堆栈中的各单元反序插入到计算链的当前节点a1前，从而原计算链变为{a500，a499，…，a1，a501，a502，…，a1001}，从a500开始计算又会发生刚才a1计算的情形，再次将压入堆栈中的各单元反序插入到计算链的待计算单元节点前，再次调整计算链为：{a1000，a999，…，a1，a1001}，从a1000开始计算，这时整个计算链可以顺利完成计算了。

本方法所述的在对电子数据表进行处理前，通过解析电子数据表各单元间的依赖关系，生成计算链，在该生成的计算链中，尽可能使被依赖单元位于依赖单元之前。生成计算链后，计算链结合堆栈来完成电子数据表的计算，避免了在计算过程中单元节点的反复移动和冗余计算，大大提高电子数据表的计算效率，节省了计算机系统资源。

参照图3，示出了本发明优选实施例一种电子数据表计算链生成方法的流程图，包括步骤：

步骤301、构建各单元间的依赖关系。

电子数据表通常由多个单元组成，这些单元相互之间有可能存在相互依赖的关系。如单元公式C4＝A4+B4，单元C4依赖于单元A4和单元B4，则所述单元c4为依赖单元，所述单元A4、B4为支持单元。在电子数据表中，依赖单元和支持单元并不是固定的，是可以相互转化的，即依赖单元在其他公式中可能就是支持单元了。如D4＝C4+E4中，C4是支持单元，D4是依赖单元。因此，在电子数据表中存在这样一种情况，一个支持单元的依赖单元是另一单元的支持单元。因为依赖单元依赖于支持单元，所以在电子数据表的计算等处理过程中，都是对支持单元先进行处理，当依赖单元的所有支持单元都处理后才能完成依赖单元的处理。

根据电子数据表各单元的关系构建依赖关系，所述构建的原则是：使支持单元在计算链中尽量位于依赖单元之前。对电子数据表中的单元构建这样的依赖关系有多种可实现的方法，如遍历所有单元，解析语法树，生成一个包含依赖关系的数据结构。具体来说，对于C4＝A4+B4，首先A4、B4是单元C4的支持单元，C4是依赖单元，解析A4、B4生成语法树的过程中，公式解析器识别了被依赖者A4和B4，从而建立依赖关系。

所述依赖关系数据结构的要求是可用电子数据表的单元作为“键值”来高效查询，用哈希表或者排序数组都可实现。单元的“键值”所指向的“值域”是个集合，用来包含依赖单元。

步骤302、向计算链中添加第一单元。

步骤303、查询该单元的依赖单元，将所述依赖单元添加到计算链的尾部。

在步骤301中已经构建好电子数据表中各单元间的依赖关系，因此，在本步骤中，以单元的“键值”或其他方法在依赖关系中进行查询即可得到该单元的依赖单元。考虑计算效率，步骤301中解析生成的单元语法树和构建的依赖关系需要缓存。一般会在文件打开时构建单元语法树。不一定要构建所有单元的语法树，在特别情况下，只构建当前活动表页的，其它表页的采用懒惰模式构建。或者将语法树、依赖关系保存在了文件里，直接加载即可。因此，通过构建的所述依赖关系数据结构，可以很容易的查询到各个单元的依赖单元。在电子数据表中，一个单元的依赖单元通常有多个，如果是多个依赖单元，则将该多个依赖单元依次添加到计算链该支持单元的后面。

步骤304、查询该新添加单元的依赖单元、将所述新添加单元的依赖单元添加到计算链的尾部。

该新添加的单元虽然是前一个支持单元的依赖单元，但在电子数据表中，它可能是其他单元的支持单元，根据依赖关系查询该新添加单元的依赖单元、将所述新添加单元的依赖单元添加到计算链的尾部。

当添加的单元有多个时，对每一个新添加的单元都重复步骤304，即从计算链紧接支持单元之后的单元开始，查询依赖于此单元的依赖单元，将它们依次添加到计算链的尾部；如此循环直到计算链的尾部。这样就将直接和间接依赖于支持单元的所有单元都添加进了计算链。

步骤305、按照预置的遍历顺序将下一单元添加到计算链的尾部，重复步骤304、305，将该支持单元的所有直接依赖和间接依赖单元都添加到计算链。

所述遍历顺序是可以是先行后列，也可以是先列后行，采用什么样的遍历顺序对本方法无影响，对此也不加以限制。

进一步，当要添加的单元已经被添加到计算链中时，则不再向计算链中添加该单元。因为电子数据表的单元是一个实现了“可计算接口”的小对象，可计算接口的其中一个方法就是设置“已添加”标记，所以在将单元添加到计算链中时，对该单元做“已添加”标记表明此单元已加入计算链，当有相同的单元要添加时，通过该“已添加”标志就可以实现不再重复添加。从而能够节省系统资源，也能提高效率。此时整个计算链已经基本上保持了被依赖单元先进行处理的顺序。

进一步，对于生成的计算链，可以采用数组或链表的方式进行存储，无论采用哪种方式，在访问效率、插入操作和内存占用成本上都各有千秋。当然也可以采用其它的方式对计算链进行存储，并不对此进行限定。

下面以一个具体的电子数据表详细说明现有技术的计算方法和本发明的计算方法。以及本发明所述方法与现在技术计算方法的有益效果。

所述电子数据表为：

	A	B	C
	A	B	C	1	＝4*B3	＝A1*C3	＝A1+B1+C2
2	3	＝3*B1	5	1	＝4*B3	＝A1*C3	＝A1+B1+C2
2	3	＝3*B1	5	3	2	＝A3*4	＝A1*A3

现有技术完成该电子数据表计算的方法：

计算链构造与计算同步进行，按照先行后列的顺序访问上列单元：

第一步、按照行列循环，计算A1，计算链{A1}；A1依赖B3，停止计算A1，将A1的支持者B3加入计算链A1前，计算链为{B3，A1}；

第二步、计算B3；计算A1；

第三步、按照行列循环，计算B1，计算链{B3，A1，B1}；B1依赖C3，停止计算B1，将B1的支持者C3加入计算链B1前，计算链为{B3，A1，C3，B1}；

第四步、计算C3；计算B1；

第五步、按照行列循环，计算C1，计算链{B3，A1，C3，B1，C1}；支持者A1，B1都已计算完成，C1计算完成；

第六步、按照行列循环，计算B2，计算链{B3，A1，C3，B1，C1，B2}；支持者B1已计算完成，B2计算完成；

第七步、按照行列循环，计算B3，B3刚已计算过；

第八步、按照行列循环，计算C3，C3刚已计算过；

第九步、计算全部完成，计算链也构造完成：{B3，A1，C3，B1，C1，B2}

本发明完成该电子数据表计算的方法：

先构建电子数据表的计算链：

按照先行后列的顺序访问上列单元，组织计算链时考虑当前单元的依赖者，[]内为当前单元：

第一步、按照行列循环，将A1加入计算链：{A1}；

第二步、[A1]将A1的依赖者[B1，C1，C3]加入计算链：{A1，B1，C1，C3}；从B1开始，按照计算链顺序循环至计算链结束；

第三步、[B1]试图将B1的依赖者C1加入计算链，但C1已在计算链中，不再添加；

第四步、[B1]将B1的依赖者B2加入计算链：{A1，B1，C1，C3，B2}；

第五步、[C1]C1无依赖者；

第六步、[C3]试图将C3的依赖者B1加入计算链，但B1已在计算链中，不再添加；

第七步、[B2]B2无依赖者；

第八步、按照行列循环，试图将B1加入计算链，但B1已在计算链中，不再添加；

第九步、按照行列循环，试图将C1加入计算链，但C1已在计算链中，不再添加；

第十步、按照行列循环，试图将A2加入计算链，但A2是常量无需计算，不再添加；

第十一步、按照行列循环，试图将B2加入计算链，但B2已在计算链中，不再添加；

第十二步、按照行列循环，试图将C2加入计算链，但C2是常量无需计算，不再添加；

第十三步、按照行列循环，试图将A3加入计算链，但A3是常量无需计算，不再添加；

第十四步、按照行列循环，将B3加入计算链：{A1，B1，C1，C3，B2，B3}；

第十五步、[B3]试图将B3的依赖者A1加入计算链，但A1已在计算链中，不再添加；

第十六步、按照行列循环，试图将C3加入计算链，但C3已在计算链中，不再添加；

第十七步、行列循环完成，生成该电子数据表的计算链，最终结果{A1，B1，C1，C3，B2，B3}。

根据计算链，应用堆栈完成电子数据表的计算：

1、计算A1：A1待计算，中断A1的计算，将A1压入堆栈；A1依赖于单元B3，且B3待计算，中断B3计算，将B3压入堆栈；B3依赖于A3，根据A3的值完成B3的计算，将B3弹出堆栈，根据B3的值完成A1的计算，将A1弹出堆栈。

2、计算B1：B1待计算，中断B1的计算，将B1压入堆栈；B1依赖于单元A1和C3，A1不需计算；计算C3，C3待计算，中断C3的计算，压入堆栈。C3依赖于A1和A3，A1不需计算，A3不需计算，根据A1、A3完成C3的计算，弹出堆栈；根据C3和A1完成B1的计算，并将B1弹出堆栈。

3、计算C1：C1待计算，中断C1的计算，将C1压入堆栈；C1依赖于A1和B3，A1不需计算，B1不需计算，C2不需计算，根据A1、B1、C2完成C1的计算，并将C1弹出堆栈。

4、计算C3：C3待计算，中断C3的计算，将C3压入堆栈；C3依赖于A1、A3，A1不需计算，A3不需计算，根据A1、A3完成C3的计算，并将C3弹出堆栈。

5、计算B2：B2待计算，中断B2的计算，将B2压入堆栈；B2依赖于B1，B1不需计算，根据B1完成B2的计算，将将B2弹出堆栈；

6、计算B3：B3待计算，中断B3的计算，将B3压入堆栈；B3依赖于A3，A3不需计算，根据A3完成B3的计算，将将B3弹出堆栈。计算全部完成。

通过上述计算过程可以很清楚的发现，现有方法进行了8次计算，其中有2次重复计算，本发明只进行了6次计算，没有重复计算。

进一步，对于更为复杂的计算来说，采用现有技术所述方法会有更多的重复计算，如：A1＝B1+C1+D1+E1，根据现有技术完成计算：

第一步、计算A1，计算链{A1}；A1依赖B1，停止计算A1，将A1的被依赖者B1加入计算链A1前，计算链为{B1，A1}；

第二步、计算B1；

第三步、计算A1，A1依赖C1，停止计算A1，将A1的被依赖者C1加入计算链A1前，计算链为{B1，C1，A1}；

第四步、计算C1；

第五步、计算A1，A1依赖D1，停止计算A1，将A1的被依赖者D1加入计算链A1前，计算链为{B1，C1，D1，A1}；

第六步、计算D1；

第七步、计算A1，A1依赖E1，停止计算A1，将A1的被依赖者E1加入计算链A1前，计算链为{B1，C1，D1，E1，A1}；

第八步、计算E1；

第九步、计算A1，完成计算。

可见A1共计算了5次，其中重复计算了4次。本发明应用堆栈式计算，没有重复计算。

因为本发明把边计算边生成计算链的方法，优化为先生成计算链，然后再根据该生成的计算链完成电子数据表的计算，并且进一步结合堆栈，完成电子数据表的计算，这样避免了在计算过程中单元节点的反复移动，并能够减少冗余运算，利用生成的计算链结合堆栈对电子数据表进行计算时效率有明显的提高，并大大节省了计算机系统资源。

参照图4、示出了本发明一种电子数据表计算装置的结构框图，包括：

堆栈401、用于缓存电子数据表单元。

判断模块402、用于判断压入堆栈的单元公式的第一项/下一项是否具有待计算支持单元，是则将该支持单元压入堆栈；否则对该单元公式的第一项/下一项直接求值。

如果压入堆栈单元的单元公式的第一项/下一项具有待计算支持单元，即该单元的值也是待计算时，则把该单元也压入堆栈。如果单元公式的第一项/下一项不是待计算单元，即该单元的值不需要计算即可以得到结果或者该单元的值是常数值时，则直接计算得到该结果值。

计算模块403、用于对新压入堆栈的单元重复调用判断模块，完成待计算单元的计算，并弹出该单元。

当压入堆栈的单元还是依赖其它单元时，则对该单元再次重复调用判断模块，直至所述单元各项的值都完成计算，根据各项的值完成待计算单元的计算。

参照图5，示出了本发明优选实施例一种电子数据表计算链生成系统的结构框图，包括：

解析模块501、用于解析电子数据表各单元间的依赖关系。

根据电子数据表各单元的关系构建依赖关系，所述构建的原则是：使支持单元在计算链中尽量位于依赖单元之前。对电子数据表中的单元构建这样的依赖关系有多种可实现的方法，如遍历所有单元，解析语法树，生成一个包含依赖关系的数据结构。所述依赖关系数据结构的要求是可用电子数据表的单元作为“键值”来高效查询，用哈希表或者排序数组都可实现。单元的“键值”所指向的“值域”是个集合，用来包含依赖单元。

置入模块502、用于向计算链添加单元。

查询模块503、根据解析模块查询电子数据表中单元的依赖单元。

以单元的“键值”或其他方法在依赖关系中进行查询即可得到该单元的依赖单元。

计算链生成模块504、调用置入模块添加第一单元至计算链中，调用查询模块查询该单元的依赖单元，并再次调用置入模块将所述依赖单元添加到计算链的尾部，对新添加的单元，重复调用查询模块和置入模块添加该新添加单元的依赖单元，直到计算链的尾部，这样就将直接和间接依赖于支持单元的所有单元都添加进了计算链。对下一单元再次重复调用置入模块、查询模块，生成电子数据表的计算链。

进一步，当要添加的单元已经被添加到计算链中时，则不再向计算链中添加该单元。因为电子数据表的单元是一个实现了“可计算接口”的小对象，可计算接口的其中一个方法就是设置“已添加”标记，所以在将单元添加到计算链中时，对单元做“已添加”标记表明此单元已加入计算链，从而当有相同的单元要添加时，通过该“已添加”标志就可以实现不再重复添加。从而能够节省系统资源，也能提高效率。此时整个计算链已经基本上保持了被依赖单元先进行计算的顺序。

进一步，对于生成的计算链，采用数组或链表的方式进行存储，无论采用哪种方式，在访问效率、插入操作和内存占用成本上都各有千秋。当然也可以采用其它的方式对计算链进行存储，并不对此进行限定。

参照图6、示出了本发明一种电子数据表计算装置的结构框图，包括：

堆栈601，用于缓存电子数据表单元。

计算链生成模块602，用于生成电子数据表的计算链。

堆栈和计算链生成模块在图4、图5所示的装置和系统中已有详细的描述，在此不再详述，参照前面即可。

判断模块603、用于判断压入堆栈的单元公式的第一项/下一项是否具有待计算支持单元，是则将该依赖单元压入堆栈；否则对该单元公式的第一项/下一项直接求值。

计算模块604、对新压入的单元重复调用判断模块，完成待计算单元的计算，并弹出该单元。

当压入堆栈的单元还是具有待计算单元时，则对该单元再次重复调用判断模块，直至所述单元各项的值都完成计算，根据各项的值完成待计算单元的计算。

进一步，所述电子数据表计算系统还可以包括异常处理模块605，当压入堆栈的单元个数达到堆栈的预设容量临界值时，将压入堆栈中的各单元反序插入到计算链的待计算单元节点前，生成新的计算链。

以上对本发明所提供的一种电子数据表的计算方法和装置，进行了详细介绍说明，本文中应用了具体个例对本发明的原理及实施方式进行了阐述，以上实施例的只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本发明的限制。

Claims

1、一种电子数据表计算方法，其特征在于，包括：

a、将待计算单元压入堆栈；

2、一种电子数据表的计算方法，其特征在于，包括：

a、生成电子数据表的计算链；

3、如权利要求2所述电子数据表的计算方法，其特征在于，步骤a所述电子数据表计算链的生成步骤包括：

a1、解析电子数据表各单元间的依赖关系；

a2、向计算链添加第一单元；

a5、重复步骤a4至计算链的最后一个单元；

a7、重复步骤a6，得到电子数据表的计算链。

4、如权利要求3所述电子数据表的计算方法，其特征在于：

当计算链中已经存在要添加的单元时，不再添加该单元。

5、如权利要求2所述电子数据表的计算方法，其特征在于，进一步包括：

预设所述堆栈的容量临界值，当压入的单元个数达到临界值要发生堆栈溢出错误时，将压入堆栈中的各单元反序插入到计算链的待计算单元节点前，按照新的计算链重新计算。

6、一种电子数据表的计算装置，其特征在于，包括：

堆栈，用于缓存电子数据表单元；

7、一种电子数据表的计算装置，其特征在于，包括：

堆栈，用于缓存电子数据表单元；

计算链生成模块，用于生成电子数据表的计算链；

8、如权利要求7所述电子数据表的计算装置，其特征在于，进一步包括：

异常处理模块，当压入堆栈的单元个数达到堆栈的预设容量临界值时，将压入堆栈中的各单元反序插入到计算链的待计算单元节点前，生成新的计算链。

9、如权利要求7所述电子数据表的计算装置，其特征在于，所述的计算链生成模块包括：

解析模块，用于解析电子数据表各单元间的依赖关系；

置入模块，用于向计算链添加单元；

查询模块，用于根据解析模块查询电子数据表中单元的依赖单元；

生成模块，用于调用置入模块添加电子数据表第一单元至计算链中，调用查询模块查询该单元的依赖单元，并再次调用置入模块将所述依赖单元添加到计算链的尾部；以及，针对新添加单元的依赖单元重复调用查询模块和置入模块，直到计算链的尾部；以及，针对电子数据表下一单元再次重复调用置入模块、查询模块，得到电子数据表的计算链。

10、如权利要求9所述的计算装置，其特征在于：

对于计算链生成模块，当计算链中已经存在要添加的单元时，不调用置入模块添加该单元。