赛事页面：http://challenge.xmtorch.cn/competitions/wangsu
- 网宿赛道第三题：编程实现数学算式运算
目标：
- 基本数学运算，支持 + - * / () [] 运算符。
- 算式语法检查。
- 更多函数运算，支持 % sin cos tan 等。
- 实现激励函数Sigmoid。

2. 实现功能

公式计算。
- 支持功能
- 对公式字符串进行运算。
- 使用方式
  1. 终端交互页面 - 运行 main.py 或 main.exe，通过终端进行交互。
  2. 测试内置的测试案例。
  3. 输入公式以进行计算。
  4. 计算本地文件内公式。
  5. 外部调用 - 类似 Python 的 math 库
    - 调用：math_class().sin(x)
  6. 文件计算 - 读取文件中的公式与理论值进行计算
    - 调用：system_class().calculate_file(path)
- 实现方式
- 面向对象实现整个计算器系统。
- 使用运算符 + - * / %、类型转换 int(), float(), str() 实现数学计算。
- 使用列表操作 append(), pop() 实现栈。
位置明确的报错功能。
- 支持功能：
- 对出现错误的公式进行报错，包括错误位置，错误字符，错误信息。

3. 运算符及其实现简介

plus(x, y) - 用于两数相加，以及正号处理
- 实现：使用 Python 运算符'+'实现
minux(x, y) - 用于两数相减，以及负号处理
- 实现：使用 Python 运算符'-'实现
mutli(x, y) - 用于两数相乘
- 实现：使用 Python 运算符'*'实现
divide(x, y) - 用于两数相除
- 实现：使用 Python 运算符'/'实现
mod(x, y) - 用于取余
- 实现：使用 Python 运算符'%'实现
abs(x) - 取绝对值
- 实现：通过正负判断实现
ceil(x) - 向上取整
- 实现：通过 Python 类型转换实现
floor(x) - 向下取整
- 实现：通过 Python 类型转换实现
round(x) - 四舍五入
- 实现：通过 Python 类型转换实现
factorial(x) - 阶乘运算
- 实现：通过循环实现
pow(x, y) - 指数运算
- 实现：基于 $x^y = e^{y*lnx}$ ，通过 self.exp(x) 与 self.ln(x) 实现
exp(x) - 以 e 为底的指数运算
- 实现：基于泰勒展开实现
sqrt(x) - 开方
- 实现：借助 self.pow(x) 实现
ln(x) - 自然对数
- 实现：基于泰勒展开实现
lg(x) - 常用对数
- 实现：借助 self.ln(x) 实现
sin(x) - 取正弦值
- 实现：基于泰勒展开实现
csc(x) - 取余割值
- 实现：借助 self.sin(x) 实现
cos(x) - 取余弦值
- 实现：基于泰勒展开实现
sec(x) - 取正割值
- 实现：借助 self.cos(x) 实现
tan(x) - 取正切值
- 实现：基于 $tan(x) = sin(x) / cos(x)$ 实现
cot(x) - 取余切值
- 实现：借助 $cot(x) = cos(x) / sin(x)$ 实现
asin(x) - 取反正弦值
- 实现：基于泰勒展开实现
acsc(x) -取反余割值
- 实现：借助 self.asin(x) 实现
acos(x) - 取反余弦值
- 实现：基于 $acos(x) = \frac{\pi}{2} - asin(x)$实现
asec(x) - 取反正割值
- 实现：借助 self.acos(x) 实现
atan(x) - 取反正切值
- 实现：基于泰勒展开实现
acot(x) - 取反余切值
- 实现：借助 self.atan(x) 实现
sinh(x) - 取双曲正弦值
- 实现：基于 $sinh(x) = \frac{e^x - e^{-x}}{2}$ 实现
csch(x) - 取双曲余割值
- 实现：基于 self.sinh(x) 实现
cosh(x) - 取双曲余弦值
- 实现：基于 $cosh(x) = \frac{e^x + e^{-x}}{2}$ 实现
sech(x) - 取双曲正割值
- 实现：基于 self.cosh(x) 实现
tanh(x) - 取双曲正切值，作为激活函数
- 实现：基于 $sinh(x) = \frac{e^x - e^{-x}}{e^x + e^{-x}}$ 实现
coth(x) - 取双曲余切值
- 实现：基于 $sinh(x) = \frac{e^x + e^{-x}}{e^x - e^{-x}}$ 实现
asinh(x) - 取反双曲正弦值
- 实现：基于 $asinh(x) = ln(x + \sqrt{x^2 + 1})$ 实现
acsch(x) - 取反双曲余割值
- 实现：基于 $acsch(x) = ln(\frac{1}{x} + \frac{\sqrt{1+x^2}}{|x|})$ 实现
acosh(x) - 取反双曲余弦值
- 实现：基于 $acosh(x) = ln(x + \sqrt{x^2 - 1})$ 实现
asech(x) - 取反双曲正割值
- 实现：基于 $asech(x) = ln(\frac{1}{x} + \frac{\sqrt{1-x^2}}{x})$ 实现
atanh(x) - 取反双曲正切值，作为激活函数
- 实现：基于 $atanh(x) = \frac{1}{2}ln(\frac{1+x}{1-x})$ 实现
acoth(x) - 取反双曲余切值
- 实现：基于 $acoth(x) = \frac{1}{2}ln(\frac{x+1}{x-1})$ 实现
sigmoid(x) - 作为激活函数
- 实现：基于 $sigmoid(x) = \frac{1}{1+e^{-x}}$ 实现
relu(x) - 作为激活函数
- 实现：基于 $relu(x) = max(0, x)$ 实现
rad(x) - 角度转弧度
- 实现：基于 $rad(x) = \frac{\pi x}{180}$ 实现
deg(x) - 弧度转角度
- 实现：基于 $deg(x) = \frac{180 x}{\pi}$ 实现

二、模块实现

1. math - 数学计算模块

下面列出具有代表性的函数进行实现介绍。
计算器系统内的调用。

def __call__(self, opr_list, x_list, y_list=['0', -1]):
    # 传入的三个list中，list[0]为运算符字符串或操作数字符串，list[1]为在公式字符串中的位置。
    opr = opr_list[0];  opr_pos = opr_list[1]
    ...
    # 根据opr判断进行哪种操作，传入的opr_pos方便在出错的时候进行定位报错
    if opr == '+':
        result = self.plus(x, y, opr_pos)
    elif opr == '!':
        result = self.factorial(x, opr_pos)
    # 约束至计算精度，以免因误差导致类似阶乘运算等要求高的运算出错
    result = self.offset2decimal(result)
    return result

取余函数：
(1) 输入判断
(2) 实现：直接使用'%'实现
(3) 不同调用方式返回不同结果

def mod(self, x, y, pos=-1):
   # 输入判断，对错误输入进行报错
   if y == 0:
       self.check.error_message(pos+1, '%', '除数不能为0')
       return ['False', pos]
   elif not (self.check.is_int(x) and self.check.is_int(y)):
       self.check.error_message(pos+1, '%', '只能对整数取余')
       return ['False', pos]
   # 计算
   result = x % y
   # 整理结果并返回，pos==-1时表示是直接调用该函数，非计算器内部调用，无需返回指定格式
   return [str(result), pos] if pos != -1 else result

取整函数：
(1) 输入判断
(2) 正负处理
(3) 实现：借助int()实现

def round(self, x, pos=-1, decimal=0):
   # 输入判断与报错...
   # 根据精度decimal放缩_1
   x = x * self.pow(10, decimal)
   # 处理正负区别_1
   is_negative = False
   if x < 0:
       is_negative = False; x = -x
   # 利用int()进行取整
   result = int(x) if x - int(x) < 0.5 else int(x) + 1
   # 处理正负区别_2
   if is_negative:
       result = -result
   # 根据精度decimal放缩_2
   result = 0 if result == 0 else result / self.pow(10, decimals)
   # 整理结果并返回
   return [str(result), pos] if pos != -1 else result

指数函数：
(1) 实现：借助类中其它函数实现
(2) 优化1：特殊值直接返回
(3) 优化2：特殊值简化计算量

def pow(self, x, y, pos=-1):
   # 优化1：对特殊值直接返回
   if x == 0 or y == 1:
       return [str(x), pos] if pos != -1 else x
   # 优化2：对整数指数幂优化，简化计算量
   elif self.check.is_int(y):
       # 正负处理...
       for i in range(y)
        result *= x
       # 整理结果并返回
   # 正常处理
   else:
    # 正负处理...
       # 调用已实现好的内部函数来计算，
       result = self.exp(y * self.ln(x))
       # 整理结果并返回

自然对数：
(1) 输入判断
(2) 实现：泰勒展开实现
(3) 优化1：不同输入使用不同泰勒展开
(4) 优化2：对计算量大的数进行拆分，基于$ln(A*B) = lnA + lnB$
(5) 优化3：常用中间数先定义好，避免计算量
(6) 优化4：限制循环次数，大部分计算不需要太多循环也能实现高精度计算
(7) 优化5：通过变化大小提前结束，变化小于计算精度时跳出循环

def ln(self, x, pos=-1):
   # 输入判断与报错...
   # 优化1：对不同的输入使用不同的泰勒展开来计算，以提高精确度与效率
   if x < 1:
       # 优化2：对计算量大的数进行拆分，基于ln(A*B) = lnA + lnB
       x_2 = 0
       while x < 0.1:
           # 优化3：常用中间数先定义好，避免计算量
           x_2 -= self.ln10;    x *= 10
       # 实现1：使用泰勒展开对其计算
       x -= 1;      result = 0;     addition = 0
       # 优化4：通过循环次数限制计算量，大部分计算不需要太多循环次数也能实现高精度计算。
       for i in range(1, self.max_loop):
           addition = self.pow(-1, i+1)
           result += addition
           # 优化5：通过变化大小提前结束，变化小于计算精度时跳出循环
           if self.abs(addition) < self.pow(0.1, self.decimal):
               break
       # 优化2：对计算量大的数进行拆分，基于ln(A*B) = lnA + lnB
       result += x_2
       # 整理结果并返回
   # 优化1：对不同的输入使用不同的泰勒展开来计算，以提高精确度与效率
   else:
       # 优化2：对计算量大的数进行拆分，基于ln(A*B) = lnA + lnB
           # 优化3：常用中间数先定义好，避免计算量
       # 实现1：使用泰勒展开对其计算
       # 优化4：通过循环次数限制计算量，大部分计算不需要太多循环次数也能实现高精度计算。
           # 优化5：通过变化大小提前结束，变化小于计算精度时跳出循环
       # 优化2：对计算量大的数进行拆分，基于ln(A*B) = lnA + lnB
       # 整理结果并返回

2. stack - 栈模块

利用 Python 列表的 append(), pop() 操作实现。
提供一些辅助计算器系统运行的函数。

3. check - 检查模块

为计算器系统提供检查、报错函数
括号核对函数，基于栈实现
- 初始化方括号栈、圆括号栈、左括号栈
- 遍历输入的字符串，出现左括号则推入对应栈
- 出现右括号时，退出对应栈，并借助左括号栈判断是否是匹配的同类左右括号。

4. calculator - 计算器模块

对输入的公式字符串进行计算。

公式字符串解析

def parse2list(self, formula):
  # 初始化合法字符
  letters = 'abcdefghijklmnopqrstuvwxyz'
  nums = '0123456789.'
  # 初始化结果列表
  formula_list = []
  # 遍历公式字符串
  for pos in range(len(formula)):
      判断当前字符与前一字符的关系，。
        1.同类字符，则跳过。
          2.异类字符，则将前面的一系列同类字符加入结果列表。
          3.如果出现了非法的字符，则报错。

def append(self, f_list, f_str, start, end):
  # 用于辅助上面的解析函数
  # 初始化有效的运算符字符串
  operators = self.barckets + [key for key in self.math.oprs.keys()]
  # 取出需处理的字符串
  item = f_str[start:end] if end >= 0 else f_str[start:]
  判断字符串的类别，并为f_list推入[字符串，位置]
    1.字符串为'(', '['，则推入'('，简化后续计算。
    2.字符串为')', ']'，则推入')'，简化后续计算。
      3.字符串为'pi'或'e'，则推入math中的对应值。
      4.字符串为数字或有效运算符，则直接推入。
      5.字符串为空格或空，则跳过。
      6.其它情况则报错。

单目运算
实现复杂，关于符号情况的分类就有83行注释说明，这里简要介绍思路，详情见函数注释。

def calculate_unary(self, formula_list):
  result = stack('公式栈')
  for pos in range(len(formula_list)):
      1.双目运算符：判断合理后入栈。
      2.单目运算符：判断合理后入栈。
      3.正负或加减：
        若为加减，判断合理后入栈。
          若为正负，判断和前一个元素的同号异号后推入。
      4.数　　　　：计算前面的单目运算符，入栈。
      5.括号　　　：判断合理后入栈。
      6.阶乘运算符：计算前面的数，入栈。
  # 返回栈内的公式列表
  return result.stack

双目运算
实现复杂，关于符号情况的分类就有67行注释说明，这里简要介绍思路，详情见函数注释。

def calculate_binary(self, formula_list):
  s_opr = stack("opr");    s_num = stack("num")
  # 从头开始计算可以处理的运算符。
  for pos in range(len(formula_list)):
      1.数：推入s_num。
      2.运算符，且优先级高于s_opr.top。
        2.1 右括号：进行循环，处理内部运算符，出现对应左括号时结束。
          2.2 阶乘　：通过self.math('!', x)计算结果，并将结果入栈s_num。
          2.3 其它　：直接入栈s_opr。
      3.运算符，且优先级小于等于s_opr.top，开始循环，直到满足内部退出条件。
        通过判断前一个运算符的类别来计算。
        3.1 双目运算符：计算并入栈。
          3.2 单目运算符：计算并入栈。
          3.3 正负或加减：根据运算符与操作数位置关系判断正负操作还是加减操作，计算并入栈。
          3.4 左括号　　：当前为右括号则直接跳出循环，否则入栈后跳出循环。
          3.5 左括号　　：根据更前一个的符号类型来进一步计算。
          3.6 阶乘运算符：计算并入栈。
          3.7 空　　　　：判断当前运算符后，计算并入栈。
          3.8 其它情况　：直接入栈并跳出循环。
  # 收尾计算，主要目的是处理公式列表中最后一个元素
  while True:
      1.s_opr空，跳出循环
      2.s_opr仅一个运算符，计算该运算符
      3.s_opr超过一个运算符
        3.1 栈顶运算符优先级大于前一个运算符优先级，计算栈顶运算符
          3.2 其它情况直接入栈
  # 返回操作数栈与运算符栈
  return s_num, s_opr

操作数栈与运算符栈合并成公式列表

def merge_num_opr(self, stack_num, stack_opr):
  # 实现较简单，利用栈中元素保存的位置信息即可。
  result = stack("公式栈")
  while True:
      1. s_num的栈底元素在前，使其入栈result
      2. s_opr的栈底元素在前，使其入栈result
      3. 两栈空时退出
  # 返回公式列表
  return result.stack

对字符串公式进行计算

def calculate(self, formula):
  # 利用前面提到的函数来实现
  # 验证括号成对性
  self.formula_check.check_brackets(formula)
  # 解析公式字符串为列表
  f_list = self.parse2list(formula)
  # 进行单目运算符计算，去重多余运算符
  f_list = self.calculate_unary(f_list)
  # 开始计算
  while True:
      # 计算双目运算符
      s_num, s_opr = self.calculate_binary(f_list)
      # 汇聚两个栈为列表
      f_list = self.merge_num_opr(s_num, s_opr)
      # 一元计算
      f_list = self.calculate_unary(f_list)
      # 条件满足返回运算结果
      return f_list

5. system - 系统模块

提供一个方便的计算方式

def __call__(self, formulas):
  # 输入格式判断与修正
  # 开始计算，记录开始时间
  self.calculate_batch(formulas)
  # 计算完成，输出计算耗时

批量计算

def calculate_batch(self, formulas):
  # 遍历以计算所有公式
  for order in range(len(formulas)):
      # 公式序号输出
      print(f'{order+1}: ', end='')
      # 调用calculator计算
      result = self.calc(formulas[order][0])
      # 结果判断
      # 错误则报错
      if result == 'Error': 
          报错
      # 与理论值对比
      try:
          1.与理论值差别小于显示精度：正确
          2.反之则报错：与理论值不同
      except:
          无理论值，输出计算结果

文件计算

def calculate_file(self, path):
  # 读取文件
  with open(path, 'r') as f:
      lines = f.readlines()
  formulas = []
  for line in lines:
      # 去除分隔符
      line = line.split('\n')[0].split(',')
      if len(line) == 1:
          formulas.append([line[0]])
      else:
          # 使用eval，用python获得理论值
          formulas.append([line[0], eval(line[1])])
  # 计算
  self(formulas)

基本运算符测试样例

["               1.1 正确的数与括号           "],
["    注：为了可读性，算式前后 与 运算符中间 会有若干个空格填充  "],
["                      100                  ", 100],
["                 [( [(   )] )]             ", 0],
["                    ( 100 )                ", 100],
["               1.2 错误的数与括号            "],
["    注：为了方便核对错误位置，错误的算式会放在开头  "],
["1 1                                        "],
["(1(1))                                     "],

混合运算符测试样例

测试样例中的理论值均为python数学公式
["       1. 基本加减乘除正误示例                        "],
["                 4 * 8 / 16                          ", 4*8/16],
["4*8/16                                               ", 4*8/16],
["4*8/0                                                ", 4*8/16],
["            (2 - 4 * 8 / 16) * 2                     ", (2-4*8/16)*2],
[" (2-4*8/16)*2                                        ", (2-4*8/16)*2],
["((2-4*8/16)*2                                        ", (2-4*8/16)*2],
["       (1 + (2 - 4 * 8 / 16) * 2)                    ", 1+(2-4*8/16)*2],
["(1+(2-4*8/16)*2)                                     ", 1+(2-4*8/16)*2],
["(1 (2-4*8/16)*2)                                     ", 1+(2-4*8/16)*2],