面向对象设计与构造-hw2思路

面向对象设计与构造迭代开发hw2

目标

本次作业加入了三角函数和递推函数,递推函数的展开可以用简单的字符串替换实现,我们为三角函数构造一类新的节点,并将由三角函数节点组成的列表与BigInteger xp(x的次方)共同构成Pair类

hw2 UML图

目标1:递推函数展开

根据题目中说明,递推函数定义式可能有以下四种情况:

f{n}(x) = 递推表达式
f{0}(x) = 函数表达式
f{1}(x) = 函数表达式

f{n}(y) = 递推表达式
f{0}(y) = 函数表达式
f{1}(y) = 函数表达式

f{n}(x, y) = 递推表达式
f{0}(x, y) = 函数表达式
f{1}(x, y) = 函数表达式

f{n}(y, x) = 递推表达式
f{0}(y, x) = 函数表达式
f{1}(y, x) = 函数表达式

当然此处的可能性并未囊括递推函数定义式的随机顺序.

我们新建一个Spreader,负责对输入字符串的展开,它具有两个属性:String[] definitionsList, int flag,definitionsList按照0,1,n的顺序存储三个定义式,flag(1~4)指示函数因子的类型(1->f{n}(x),2->f{n}(y)...)

在输入定义式后,我们将这三个定义式存入definitionsList,并通过正则表达式获得flag

进一步,我们对input字符串调用spread方法,我们利用正则表达式持续寻找f{n|1|2}格式的字符串,并根据definitionsList将其替换为展开的表达式,直到input字符串中不再存在f{n|1|2},这意味着我们已经实现了将所有递推函数展开,接下来的计算思路就和hw1一致了

目标2:三角函数

trigNode类属性如下:

class TrigNode {
    String type; // "cos" | "sin"
    ExpressionNode children; // 子表达式节点形式
    String childrenString; // 子表达式字符串
    BigInteger exp; // 指数
}

当我们构建TrigNode时,传入type, chlidren, exp,构造方法内调用Printer类的打印方法将children转化为字符串形式childrenString,便于后面判断两个三角函数类型是否相同

表达式即使字符串形式一致,节点形式也不一定一致

trigNode表示三角函数,结构组成为type(childrenString)^exp

目标3:新增Pair类

Pair类属性如下:

class Pair {
    BigInteger xp;
    ArrayList<TrigNode> trigList;
}

它表示不含前导系数的项,与系数组成HashMap<Pair, BigInteger>,表示表达式的整体.

目标4:三角函数的化简

1. 项内合并

我们修改Pair的add()方法,Pair相加即两项算术相乘,xp相加,而trigList使用addAll()方法,将两个ArrayList的内容合并并返回.这里我们要注意ArrayList可能会出现同类三角函数元素,即类型相等且子表达式相等.我们找到所有满足这类合并条件的式子,将他们的exp相加得到一个新的元素.举个例子:

cos(x)*cos(x)->cos(x)^2

原先的两个Pair个各有一个size=1的trigList,合并时,我们通过遍历时发现两个trigList的元素trig1与trig2可以合并,得到一个type=cos,childrenString=x,children=trig1.getChildren(),exp=trig1.getExp()+trig2.getExp()的三角函数节点

这里我们为什么要保留TrigNode的Chlidren这种节点形式的子字符串呢?输出时直接打印字符串不就好了?这里保留Chilldren主要是为了可以实现和差化积(后面会提及),这种简化会得到新的子字符串,但已经转成字符串的childrenString就无法实现计算和简化功能了.

2.特殊值

三角函数存在特殊值.如cos(0)=1,sin(0)=0.我这里采取的方法是在Parser类识别三角函数类时加入特判:

if (trigNode.getType().equals("sin") && trigNode.getChildrenString().equals("0")) {
    // sin(0) -> 0
    numberNode.add(new Pair(BigInteger.ZERO, trigList), BigInteger.ZERO);
} else if (trigNode.getType().equals("cos") &&
        trigNode.getChildrenString().equals("0")) {
    // cos(0) -> 1
    numberNode.add(new Pair(BigInteger.ZERO, new ArrayList<>()), BigInteger.ONE);
} else {
    numberNode.add(new Pair(BigInteger.ZERO, trigList), BigInteger.ONE);
}

3. 和差化积

我们这里需要实现的是:

cos^2(h(x,y))+sin^2(h(x,y))=1
cos^2(h(x,y))-sin^2(h(x,y))=cos(2f(x,y))

其中h(x,y)是指含x,y的表达式

这里借鉴OO课程网站提供思路

基本思路

表达式满足结构\(expr = term_1\pm\cdots\pm term_{n}\)

我们遍历表达式的每个项,对于每个项\(term_i\),我们遍历\(term_{i+1}\)到\(term_{end}\),依次两两判断能否合并.

对于两个项,首先要求它们的x次幂相等,系数的绝对值相等.然后是先将它们的公因式提取出来:

for (Factor factor1: Term1.getFactors()) {
    for (Factor factor2: diffTerm2.getFactors()) {
        若factor1与factor2相等，则:
        <factor1,min{pow1,pow2}> 塞入sharedTerm
        <factor1,pow1-min{pow1,pow2}> 塞入diffTerm1,若pow1 == min{pow1,pow2}则不管
        将diffTerm2中 factor2次数修改为 pow2-min{pow1,pow2},为0则remove
    }
}

得到两项各自的独因式,若两项的独因式有至少一个的三角函数因子数大于1,则判定两项不能实现合并.否则继续根据三角函数因子的类型和子表达式判断能否合并.两个三角函数因子合并的条件如下:

// cos^2 + sin^2
coeff1.equals(coeff2) && 
(trigList1.size() == 1 && trigList2.size() == 1) &&
((trig1.type.equals("cos") && trig2.type.equals("sin") ) ||
 (trig1.type.equals("sin") && trig2.type.equals("cos") )  )
&& trig1.childrenString.equals(trig2.childrenString) // childrenString是三角函数内子表达式的字符串形式
// cos^2 - sin^2
coeff1.equals(coeff2.negate()) &&  
(trigList1.size() == 1 && trigList2.size() == 1) &&
((trig1.type.equals("cos") && trig2.type.equals("sin") ) ||
    (trig1.type.equals("sin") && trig2.type.equals("cos") ) )
&& trig1.childrenString.equals(trig2.childrenString)
// cos^2 - 1 | sin^2 - 1
coeff1.equals(coeff2.negate()) &&  
((trigList1.empty() && trigList2.size() == 1) ||
 (trigList2.empty() && trigList1.size() == 1) )&&
trig1.childrenString.equals(trig2.childrenString)  

例如:\(2*x*\cos(x)^2+2*x*\sin(x)^2\),我们先判断系数绝对值和x的幂次相等,接着提取出三角函数公因式None,两项各自的独因式分别为\(\cos(x)^2\)和\(\sin(x)^2\),合并后得到1,因此两项合并结果为\(2*x*1=2*x\)