Object Oriented 2023 作业 1

写在前面

由于目前距离第一单元作业结束还有很久很久，所以本文会较为简略的描述我的思路架构和测试。还请诸位谅解。

思路和架构

总体而言，思路和架构都可以大部分模仿 Training （两个 Training，一个是 正则表达式/逆波兰表达式，一个是 递归下降）我模仿的第二个。我的思路是一个 Lexer 分析 Token， 一个 Parser 解析字符串，最后 Simplifie 一下表达式就可以了。

主要类结构

1. BaseExpr - interface - 基类。
2. Expression - 存储由 Parser 分析而来的，由 Term 构成的表达式
3. Term - 储存由 Parser 分析而来的，由 Factor 构成的表达式
4. Factor - 储存由 Parser 分析而来的，由 base ** index 构成，其中 base 可能是 Expression，Constant，或 Variable。
5. Lexer - 词法分析
6. Parser - 表达式解析
7. Simple - 化简表达式

测试

自动化测试真好用。所以强烈建议大家都去自己写一下。如果自己不能写的话，记得请一个会写的大佬吃饭（确信）。

正确性测试

第一单元作业是表达式化简。人生苦短，我用 Python。sympy 库可以非常非常方便的帮助你验证两个表达式是否是等价的（唯一需要注意的是需要去除前导零）。

这里就贴个代码给大家参考参考吧（应该很好理解吧？）。

def parse_leading_zero(s: str):
    """Delete leading zero"""
    pattern = re.compile(r'(\D)0+(\d)')
    return pattern.sub(r'\g<1>\g<2>', s)


def judge(s1: str, s2: str):
    """
    s1 - input str; s2 - output str;
    return True if s1 == s2 else False
    """
    if '(' in s2 or ')' in s2:
        return False
    try:
        ifunc = sympy.sympify(parse_leading_zero(' ' + s1))
        ofunc = sympy.sympify(parse_leading_zero(' ' + s2))
        return True if ifunc.equals(ofunc) else False
    except ValueError: # sympify error
        return False

性能分测试

本次作业性能分可以理解为输出的化简后表达式越短分越高。不过由于你的表达式是否短取决于是否有其他同学比你更短。所以我们需要一个数据库保存大家测试的结果，然后找出每组数据最短的表达式的长度是多少，借此评估性能分。

这里我采用了 Lean Cloud 的免费数据库来储存数据，然后将测试脚本发给多人进行测试，这样下来，大家都知道自己的性能分处于什么水平了（当然这要求你的朋友们中都是些大佬）。

获得到得分后的计算就按照指导书中所述就可以啦：

def get_grade(lp: int, lmin: int, base=1):
    x = lp / lmin
    if x <= 1:
        return 1.0 * base
    elif x >= 1.5:
        return 0.0 * base
    return (-31.8239 * x**4 + 155.9038 * x**3 - 279.2180 * x**2 + 214.0743 * x - 57.9370) * base

Lean Cloud 的使用方法可以参考官方文档，这里就不详细介绍了。大家也可以使用其他数据库。

import leancloud


leancloud.init('appID', 'appKey')
HW1 = leancloud.Object.extend('HW1')


def fetch(sh: str, length: int):
    query = HW1.query
    query.equal_to('hash', sh)
    data_list = query.find()
    if data_list:
        data = data_list[0]
        last_length = data.get('lmin')
        if last_length > length:
            data.set('lmin', length)
            data.save()
            return length
        return last_length
    else:
        data = HW1()
        data.set('hash', sh)
        data.set('lmin', length)
        data.save()
        return length

数据生成

随机生成器通常就按照指导书上的介绍一一生成就可以了。框架如下：

# Generators
def white_space_term():
    length = randint(0, MAX_SINGLE_WHITE_SPACE_LENGTH)
    return reduce(lambda x, y: x + y, [choice(WHITE_SPACE[0]) for _ in range(length)], '')


def integer_with_leading_zeros():
    length = randint(1, MAX_INTEGER_LENGTH)
    return reduce(lambda x, y: x + y, [choice(DIGIT) for _ in range(length)], '')


def integer_with_signal():
    return choice(PLUS_MINUS + ['']) + integer_with_leading_zeros()


def exponent(smaller=False):
    if smaller:
        return '**' + white_space_term() + choice(['+', '']) + choice(['0', '']) + choice(INDEX[:20])
    return '**' + white_space_term() + choice(['+', '']) + choice(['0', '']) + choice(INDEX)


def power_function():
    if random() > PROBABILITY_OF_POWER_WITHOUT_EXPONENT:
        return choice(VARIABLES) + white_space_term() + exponent()
    return choice(VARIABLES)


def expression_factor(brackets):
    if random() > PROBABILITY_OF_EXPRESSION_WITHOUT_EXPONENT:
        return '(' + expression(brackets - 1) + ')' + white_space_term() + exponent()
    return '(' + expression(brackets - 1) + ')'


def factor(brackets):
    if brackets > 0:
        res = random()
        if res < PROBABILITY_OF_CONSTANT_FACTOR:
            return integer_with_signal()
        elif res < PROBABILITY_OF_CONSTANT_FACTOR + PROBABILITY_OF_VARIABLE_FACTOR:
            return power_function()
        else:
            return expression_factor(brackets)
    else:
        if random() < PROBABILITY_OF_CONSTANT_FACTOR \
                / (PROBABILITY_OF_CONSTANT_FACTOR + PROBABILITY_OF_VARIABLE_FACTOR):
            return integer_with_signal()
        else:
            return power_function()


def term(brackets, factors=MAX_FACTOR_PER_TERM):
    if random() < 1 / factors:
        return choice(PLUS_MINUS + ['']) + white_space_term() + factor(brackets)
    else:
        return term(brackets, factors - 1) + white_space_term() + '*' + white_space_term() + factor(brackets)


def expression(brackets, terms=MAX_TERM_PER_EXPRESSION):
    if random() < 1 / terms:
        return white_space_term() + choice(PLUS_MINUS + ['']) \
               + white_space_term() + term(brackets) + white_space_term()
    else:
        return expression(brackets, terms - 1) + choice(PLUS_MINUS) \
               + white_space_term() + term(brackets) + white_space_term()

强测和互测

强测和互测均没有出现 bug。甚至更离谱的是，互测整个 room 都没有发现 bug。

不过根据其他同学反馈的信息，有一些数据值得一试：

1. -1（单独的数字）
2. 0*x**0（零的零次幂以及零乘以零次幂）
3. 1+2+3\t \t \t\t（尾随空白符）
4. (x+y+z)**8（几千项的展开）
5. ---1（多重符号）