GPCalc详细文档

GPCalc by 刘奕聪

题目

我们需要完成一个可以自动解析计算表达式，并进行运算返回结果的一个科学计算器程序。
详细：完整题目

使用平台

• 语言平台：Python 2.7
• 操作系统：兼容Python 2.7 的所有系统
• 开发IDE：PyScripter 2.5.3 x86
• 程序入口：main.py
• 使用的第三方库：pytest（仅用于单元测试，实际使用不需要）

作品说明

数据类型

实数

基本数值类型，如：123，123.45，.123，123.。
可以使用8进制和16进制表示，但仅支持表示整数：

• 8进制：0o125。
• 16进制：0xAC，0Xb1。

复数

使用Python表示方式，其中虚部数值后必须加上复数单位量j，如：1+2j，0.5j，0.5-0.5j。
当实数和复数混合运算时会隐式转换成复数。
复数单位量j之前必须有系数。

数组

复合类型，多个数据的集合，表示方式：括号包围，逗号分割元素，如：[1,2]，(3.5,1+0j),(1,(2,3),(4,(5,6)))。
嵌套型数组会被系统降维成一维数组。

运算符

单目运算符

单目运算符包括以下三种：

1. +：表示正数。
2. -：表示负数。
3. 引用符：包括变量引用符$和自定义函数引用符#。
4. 函数：由英文开始且仅包含英文数字和下划线的符号。

双目运算符

1. +：加。
2. -：减。
3. *：乘。
4. /：除。
5. mod：模除，同%，但mod运算符后不能粘连变量或数值。
6. ^：乘幂，同**。
7. ,：数组化操作。

优先级说明

以下运算符优先级从高到低排序：

1. 单目运算符：+，-，引用符与函数。
2. 乘幂和模除：mod与^。
3. 乘法和除法：*与/。
4. 假发和减法：+与-。
5. 数组化操作符：逗号,。
6. 括号：()同[]。

特殊说明

• 数组作为一种特殊的数据类型，仅有少数个可用的运算符，仅包括数组的拼接,和函数。
• $变量引用符仅能作用于变量。
• #函数引用符仅能作用于自定义函数。

变量

变量是数据暂存的存储单元，在一定程度上简化表达式和免去重复计算而提高效率。
变量声明格式如下：

$变量名:表达式

其中，$为变量引用符，变量名仅能使用若干个仅包含英文数字和下划线的符号，:为声明符，其后跟表达式，系统会计算表达式的值并将结果赋值给变量。
初始化后的变量能够作为表达式的一份子参与计算，如：$x + $$ans。

自定义函数

系统允许用户定义临时的lambda表达式，其使用方式与内置函数一样。
对于一些被大量重复计算的表达式推荐定义成函数，第一个好处是避免重复输入表达式，第二个是自定义函数比重复输入表达式的方式的性能要高。
声明格式如同变量：

#函数名:表达式

和变量类似，#为函数引用符，命名规则同变量，和变量相同的命名不会造成冲突。:为声明符，其后跟表达式，函数中使用位置变量来代替参数，如形为：#f (5,6,7,8)的函数调用，则在自定义函数#f中可以使用$1，$2，$3，$4来分别表示参数5，6，7，8。特殊的，$0表示整个参数数组。

内置常量

• $$ans：上次表达式的结果。
• $$0：空数组。
• $$pi：圆周率。
• $$e：自然底数。
• $$c：真空中光速。
• $$h：普朗克常数。
• $$g：引力常数。
• $$f：法拉第常数。
• $$inf：无穷大。

方程

系统提供了解一元一次方程的功能。
方程格式如下：

表达式1 = 表达式2

其中，用$$表示未知数，方程的结果是$$的值。
注意，$$不能用于函数，不能作为数组元素。

正确格式如：fact(10) * sin($$pi * 2) * $$ = sum([1, 2, 3, 4, 5]) - 1。
未知数$$不能在表达式中作为分母，分母中含有未知数的方程是分式方程，不属于一元一次方程。

在Google Talk上使用

1. 添加帐号：lycbot@appspot.com。
2. 请向该帐号发送你的表达式，每个表达式占一行。
3. 因为该聊天机器人托管在Google App Engine上，因此一次执行完后会退出，所定义的函数和变量会被删除。

注：因为GAE的Python版本较低和限制较多，其上面搭载的GPClac是修改过的，会有一些差别。

开发说明文档

设计理念

原则

• 功能完善
• 结构精细
• 易于扩展
• 更多创意

表达式的结构分析

题目中对于表达式要求支持数组与函数，其中形式分别如下：
数组：

[element1,element2,element3]

函数：

funcname(arg1,arg2)

其中数组要求以中括号[]作为定界符，,作为元素分割符，题目中的示例数组元素皆为数值，但并没有定义数组元素是否能为数组，但通过观察题目，总结出嵌套型数组是没有意义的结论。

我们知道数组是一种复合的数据类型，其之所以能将元素组合起来，其主要原因是逗号,的存在，而并非其两侧的定界符，定界符的用途仅是为了避免与外界元素的混淆，达到一种封闭的意义而已。

那么我们将逗号,定义成一种二目运算符，用以将其两侧的元素进行数组化的操作，特殊的，单一元素（数值）与数组进行数组化操作产生一个由两者拼接成的数组，如：1,2 == [1,2]，1,2,3 == [1,2,3]。
注：如果觉得难以理解1,2,3 == [1,2,3]这个表达式，请按照1+2+3 == 6的原理来理解。

在定义了数组化操作运算符,后，我们再看函数的表示方式，通过观察函数的参数列表表示形式，尤其是多参数的函数，与数组相比，除了定界符不是中括号[]而是小括号()外，其它形式几乎一致。

而在现实的数学中，中括号[]和小括号()都是表示一种封闭的意义，如封闭一个局部表达式以改变其上一级表达式的运算符优先级，其中中括号[]的优先级低于小括号()。因此在计算机科学中用以改变运算符优先级仅保留小括号()而将中括号[]移作它用（但使用的效果一样）。

如果我们将小括号()和中括号[]统一看作括号的话，此时多参数的函数的参数列表则变成了一个数组，而函数名则类似于单目运算符，对其后的元素（单参数看作数值，多参数看作数组）进行操作。

我们通过一些扩展将函数的表示形式变换成一种单目运算符，而将逗号,定义成一种二目运算符以简化表达式结构，此时表达式有如下基本元素：

1. 可计算元素：数值，数组
2. 运算符：单目运算符，双目运算符
3. 括号：()，[]

表达式分析阶段

1. 预处理：通过字符串操作的方式进行预处理。
2. 记号分析：通过分析器分割记号并对记号进行归约。
3. 表达式转换：分析表达式各个运算符的优先级并进行转换。

预处理

预处理阶段主要有以下操作：

1. 去除前后空白字符。
2. 表达式转为小写。
3. 对变量和函数引用符进行替换。

记号分析

记号分析其实为简化的词法分析和语法分析，词法分析主要工作是将表达式中的元素分割成记号，其中会将8进制整数和16进制整数转换成10进制表示形式。

语法解析器会对记号进行预读，并按照语法图的流程读入所有记号并进行识别，语法分析使用以下文法进行分析：
$V_t = \{num, var, uop, bop, cmm, lbk, rbk, ε\}$
$V_n = \{E, O, R, U, V, B\}$
$S = \{E\}$

$P=\{$
$\quad E→OR$
$\quad O→UV$
$\quad R→BE \;|\; ε$
$\quad U→uop \, U \;|\; ε$
$\quad V→lbk \, E \, rbk \;|\; num \;|\; var$
$\quad B→bop \;|\; cmm$
$\}$

表达式转换

根据运算符的优先级对表达式进行转换，以下运算符优先级从高到低排序：

1. 括号：()同[]。
2. 单目运算符：+，-，引用符与函数。
3. 乘幂和模除：mod与^。
4. 乘法和除法：*与/。
5. 加法和减法：+与-。
6. 数组化操作符：逗号,。

因有别于Python的表达式运算符优先级，因此需要进行转换，转换算法后面给出。

YCPY：GPCalc的引擎

YCPY最初是在项目LYCBot中使用的解释器，用于提供基于Python的虚拟运行环境，以隔离内部运行的代码对外部的影响。

YCPY的工作

提供虚拟环境Environment

其实际是一个字典，YCPY会将其映射到内部环境以提供服务。

stdin，stdout和stderr的重定向

通过重定向使得在虚拟环境中的输出输入和异常不会影响到外部。并有对于在偶然的情况下因为把YCPY暴露到内部环境时被间接递归调用引发的错误重定向问题时提供了一个安全机制，用于保证第一个调用方对其的控制权，详见switch_stream。
原理简述：

switch_stream保存着一个key（成员变量，初始值为1），如果oldkey和当前key相同，则执行切换，执行完oldkey=newkey。

外部调用时，如果当前是第一层调用，则switch_stream的key应该是初始值，因此oldkey为初始值，另产生一个随机的newkey作为参数，调用switch_stream后则拥有了对switch_stream的控制权，以后用newkey就可以继续调用switch_stream。而如果有递归的情况，因为oldkey已经不是初始值了导致调用switch_stream失败。

限制__builtins__的功能

__builtins__保存了Python中的内建对象，通过限制__builtins__的功能来防止内部代码注入到外部。

GPCalc中的YCPY

求值

GPCalc将表达式转换成等价的Python表达式后送入YCPY进行求值。

函数支持

通过将math库或其他库中提供的函数映射到YCPY内部以成为系统内置的函数，而且扩展代价极小，只需把包装好的函数加到YCPY.Environment上即可。

存储系统

利用了YCPY进行变量存储和自定义函数。

异常保护

当遇到异常情况时，利用YCPY给出的异常信息来进行提示，而且因为YCPY的隔离使得异常不会抛到外部以导致程序关闭。

GPCalc模块说明

Tools

为其他模块提供一些工具和支持。

expelement.py：表达式元素

概览：

• ElementType：表达式元素类型。
• ElementTypeEnum：表达式元素类型枚举。
• Element：表达式元素（一个具体元素拥有类型和其具体的值）。

operators.py：表达式运算符

概览：

• Operator：运算符类型。
• UnaryOperator：单目运算符类型。
• BinaryOperator：双目运算符类型。
• operator_factory：运算符工厂函数。

grape.py：默认智能数值类型

概览：

• grape_operator：智能类型转换装饰器。
• graperesult：将方法结果包装成Grape类型装饰器。
• autonum：智能数字工厂方法。
• GrapeType：Grape类的元类。
• Grape：继承自decimal.Decimal的智能高精度数值。

Convertor

转换器部分，用以将葡萄表达式装换成等价的Python表达式。

grapetokenizer.py：Grape表达式的Tokenizer

概览：

• pretokens：利用tokenize.generate_tokens进行预处理的生成器。
• GrapeToken：记号分析器类，基于pretokens生成器。

GrapeToken类的实现基于前面给出的文法，基于这个文法，构建出以下的状态转移图：

其中状态2是终态。

符号说明：

1. NUM：对应于$V_t$的$num$，表示数值。
2. VAR：对应于$V_t$的$var$，表示变量。
3. UOP：对应于$V_t$的$uop$，表示单目运算符。
4. BOP：对应于$V_t$的$bop$，表示双目运算符。
5. CMM：对应于$V_t$的$cmm$，表示数组化操作符。
6. LBK：对应于$V_t$的$lbk$，表示左括号。
7. RBK：对应于$V_t$的$rbk$，表示右括号。
8. NON：对应于$V_t$的$ε$，表示空。

通过输入记号并通过状态转移图的决策后可以判断表达式的结构正确与否，并识别各个记号的类型和属性。

convertor.py：将记号转换为Python表达式的转换器

Convertor类中有两个较复杂的算法，在此进行简要说明。

Convertor.topostfix(tokens)：记号转为后缀表达式

1. 建立一个运算符栈op_stack和后缀表达式列表。
2. 遍历tokens直至末尾，跳至7。
3. 遇到数字和变量直接追加到后缀表达式。
4. 否则遇到右括号,逗号和双目运算符从op_stack弹出一部分合适的运算符（栈顶运算符优先级小于当前运算符或遇到左括号），追加到后缀表达式中，如果当前运算符是右括号则还需把栈顶的左括号弹出。
5. 如果遇到单目运算符，左括号和双目运算符则直接压入op_stack。
6. 跳至2。
7. 将栈中剩余的操作符追加到表达式。

Convertor.gptopyexp(gtk)：葡萄表达式转为Python表达式

算法原型：Wikipedia

1. 先将gtk转换为后缀表达式postfix。
2. 建立一个操作数栈。
3. 遍历postfix的记号直至末尾，跳至7。
4. 遇到数值和变量则直接入栈，其中数值使用grape.autonum进行注入变为自动类型。
5. 如果是运算符则出栈运算符对象指定数目（opnum）的操作数进行转换，将转换结果压入操作数栈，如果栈中元素少于指定数目则报错。
6. 跳至3。
7. 如果栈内只有一个值，这个值就是整个计算式的结果。
8. 如果多于一个值，用户输入了多余的操作数，报错。

Calculator

ycpy.py：解释引擎

YCPY最初是在项目LYCBot中使用的解释器，用于提供基于Python的虚拟运行环境，以隔离内部运行的代码对外部的影响。

supporter.py：功能支持和扩展

概览：

• func_lambda：自定义函数类，解决了自定义函数嵌套调用的参数冲突和递归情况。
• Supporter：支持类，导出包括但不限于所有GPClac的数值计算函数。

func_lambda优化方法

预转换：在声明函数的时候进行转换，以达到语法错误提前检查和优化性能的效果。

参数冲突：因为自定义函数的参数是暴露在YCPY全局成为全局变量的方式的，所以在自定义函数嵌套调用的时候会引发参数冲突，因此func_lambda会在调用时备份上一层的参数（如果有）并在表达式执行完后恢复。

无限递归：如果有在自定义函数表达式中存在引用当前函数（直接或间接）的情况，如果不处理会导致无限递归进而导致程序崩溃的情况，因此不允许递归，但因递归调用的复杂性，因此不会在预转换中检查，而是在调用的过程中动态检查。

Supporter的函数包装

因为在GPCalc中对函数的特殊定义导致了对导出到YCPY的函数也需要进行包装，Supporter提供了几个装饰器来进行对函数的包装：

• tuple：参数包装成数组并降维（一维数组）。
• list2args：将数组参数展开成参数列表（多参数）。
• args2list：将参数列表包装成数组参数（单参数）。

calculator.py：计算器

利用YCPY和Convertor等提供计算表达式，自定义变量和函数，计算一元一次方程等功能。

其他

gpcalccfg.py：定义配置信息

用以保存在程序中需要用到的数值或其他字符串常量等信息。

main.py：程序入口

有两种启动方法：

1. 直接启动：进行控制台交互方式。
2. 带参启动：计算参数指定的表达式。

各模块交互时序

交互时序图

步骤详解

1. 用户输入表达式。
2. 创建Calculator对象。
3. Calculator对象使用Supporter导出的API来初始化YCPY。
4. 主函数将表达式送入Calculator。
5. Calculator利用Convertor转换表达式。
6. Convertor将表达式送入GrapeToken进行记号分析。
7. 进行记号分析。
8. 返回葡萄表达式的记号。
9. 转换为等价的Python表达式。
10. 返回Python表达式。
11. 将表达式送入YCPY。
12. YCPY对表达式进行求值。
13. 返回结果。
14. 返回结果。

附录

内置常量与函数

内置常量

• $$ans：上次表达式的结果。
• $$0：空数组。
• $$pi：圆周率。
• $$e：自然底数。
• $$c：真空中光速。
• $$h：普朗克常数。
• $$g：引力常数。
• $$f：法拉第常数。
• $$inf：无穷大。

实数函数

• sin(x)：正弦。
• cos(x)：余弦。
• tan(x)：正切。
• arcsin(x)：反正弦。
• arccos(x)：反余弦。
• arctan(x)：反正切。
• rsin(x)：使用弧度表示的正弦。
• rcos(x)：使用弧度表示的余弦。
• rtan(x)：使用弧度表示的正切。
• rarcsin(x)：使用弧度表示的反正弦。
• rarccos(x)：使用弧度表示的反余弦。
• rarctan(x)：使用弧度表示的反正切。
• sinh(x)：双曲正弦函数。
• cosh(x)：双曲余弦函数。
• tanh(x)：双曲正切函数
• log(x, nBase)：以 nBase 为底，值 x 的对数。
• log10(x)：求给定值 x 的常用对数。
• ln(x)：求给定值 x 的自然对数。
• pow(x, nPower)：求值 x 的 nPower 次幂。
• exp(x)：求数学常数 e 的 x 次幂。
• fact(x)：求 x 的阶乘
• mod(x, y)：模运算，等同 x mod y。
• sqrt(x)：开平方根。
• cuberoot(x)：开三次方根。
• yroot(x)：求值 x 的 y 次方根。
• rad(x)：角度转为弧度。
• ang(x)：弧度转为角度。

复数函数

• zsqrt(x)：对复数开平方.
• zexp(x)：对复数求数学常数 e 的 x 次幂。
• zlog(x, nBase)：以 nBase 为底，值 x 的复数的对数。
• zlog10(x)：求给定值 x 的复数的常用对数。
• zln(x)：求给定值 x 的复数的自然对数。
• zsin(x)：复数的正弦。
• zcos(x)：复数的余弦。
• ztan(x)：复数的正切。
• zarcsin(x)：复数的反正弦。
• zarccos(x)：复数的反余弦。
• zarctan(x)：复数的反正切。
• zsinh(x)：复数的双曲正弦函数。
• zcosh(x)：复数的双曲余弦函数。
• ztanh(x)：复数的双曲正切函数。
• real(x)：数值的实部。
• imag(x)：数值的虚部。

数组函数

• avg([…])：数组的算术平均值。
• sum([…])：数组的统计。
• var([…])：数组的估算方差。
• stdev([…])：数组的总体方差。
• varp([…])：数组的估算标准差。
• stdevp([…])：数组的总体标准偏差。
• floor([…])：对数组向下取整。
• len([…])：计算数组元素个数。
• tuple([…])：包装成数组。
• head([…])：取数组头部。
• tail([…])：取数组除头部外剩下的所有元素。
• left([…])：取数组左半部分。
• right([…])：取数组右半部分。
• seek(n, […])：返回指定下标 n 的元素。
• val([…])：转换并打印各个进制下数组中元素的表示。

运算符优先级表

表达式类型	名称	表示	优先级权值
单目运算符	正号	+	50
单目运算符	负号	-	50
单目运算符	引用符	$ #	50
单目运算符	函数	函数	50
双目运算符	求余	mod	40
双目运算符	乘幂	^	40
双目运算符	乘号	*	30
双目运算符	除号	/	30
双目运算符	加号	+	20
双目运算符	减号	-	20
双目运算符	数组化	,	10
括号	括号	() []	00