OO第一单元总结

OO 第一单元总结

本文为OO第一单元总结，本单元主要任务是表达式的展开与化简。核心思想是递归下降法，主要分为预处理、解析、多项式生成、化简四个个核心步骤。三次作业增量迭代的要求如下

  • 第一次作业

    • 去括号
      • 一层括号
    • 多项式化简

  • 第二次作业

    • 括号嵌套
    • 自定义函数
      • 无递归定义，有递归调用
    • 新增三角函数因子

  • 第三次作业

    • 自定义函数

      • 递归声明与调用

    • 新增求导因子

      • 仅出现一次

一、程序结构

1.类图(第三次作业)

classDiagram
Main --> StrHandler : preprocess the input by the method"strHandler"
Main --> Parser : parse the input by the method"parseExpr"
Main --> Poly : print the result by the method"getPrint"
StrHandler --> Func : replace the input's functions with expr
class Main{
      +main()$
}
class StrHandler{
      +strHandler()$ String
      +parseFunc()$ String
      +funcHandle()$ String
      +findBracket()$ int
      +remZero()$ String
      +noSignNum()$ String
      +noBracket()$ boolean
      +isNum()$ boolean
      +isTurnNeg()$ boolean
}
class Func {
      -String content
      -int sum
      -HashMap~Integer, String~ parameters
      +getSum() int
      +funcStruct() coid
      +getContent() String
}
Parser --> Factor : Parse the factor(Expr/Term/Factor)by Lexer
Parser ..> Lexer : contains 
Poly ..> Mono : contains
Factor --> Poly : turn to Poly from Factor by the method "getPoly()"

class Poly {
      -int sign
      -ArrayList~Mono~ monos
      +turnNeg() void
      +addPoly() void
      +addMono() void
      +multPoly() Poly
      +getPrint() String
}
class Mono {
      -int sign
      -BigInteger con
      -BigInteger xin
      -BigInteger yin
      -BigInteger zin
      -HashMap~String,BigInteger~ sins
      -HashMap~String,BigInteger~ coss
      +setMono() void
      +clearHash() void
      +turnNeg() void
      +addSame() void
      +mulMono() Mono
      +addTris() void
      +addSin() void
      +addCos() void
      +isSame() boolean
      +isSameFang() boolean
      +getPrint() String
      +printTri() String
      +compareTo() int
      
      
}
class Parser{
      -Lexer lexer
      +parseExpr() Expr
      +parseTerm() Term
      +parseFac() Factor
      +parseDer() Deri
      +parseSin() Sin
      +parseCos() Cos
}


Factor <|-- Expr
Factor <|-- Term
Factor <|-- Cos
Factor <|-- Sin
Factor <|-- Num
Factor <|-- Var
Factor <|-- Deri
Factor <|-- Power


class Factor{
      -int sign
      +getSign() int
      +setSign() void
      +getPoly() Poly
      +derivation() Poly
}
class Lexer{
      -String input
      -int pos
      -String curToken
      +next() void
      +getNum String
      +getCurToken() String
      
}
class Expr{
      -int sign
      -ArrayList~Term~ terms
      +addTerm() void
      +getPoly() Poly
      +derivation() Poly
}
class Term{
	  -int sign
	  -ArrayList~Factor~ factors
	  +addFac void
	  +getPoly Poly
	  +derivation() Poly
	  
}
class Power {
      -Expr base
      -BigInteger index
      -Poly basePoly
      +getPoly() Poly
      +derivation() Poly
}
class Cos{
	  -int sign
	  -Factor parameter
	  -BigInteger index
	  -Poly selfPoly
	  -String paraStr
	  +setIndex() void
	  +getPoly() Poly
	  +derivation() Poly
	  +setParameter void
	  
}
class Sin{
	  -int sign
	  -Factor parameter
	  -BigInteger index
	  -Poly selfPoly
	  -String paraStr
	  +setIndex() void
	  +getPoly() Poly
	  +derivation() Poly
	  +setParameter void
	  
}
class Num{
      -int sign
      -BigInteger value
      +getPoly() Poly
      +derivation() Poly
}
class Var{
      -String name
      +getPoly() Poly
      +derivation() Poly
}
class Deri{
      -int sign
      -String fac
      -Expr expr
      +setFac() void
      +setExp() void
      +getPoly() Poly
      +derivation() Poly
}

2.代码结构

2.1代码行数

Source File Total Lines Source Code Lines Source Code Line[%] Comment Lines Comment Lines[%] Blank Lines Blank Lines[%]
Factor.java 22 17 0.7727272727272727 0 0.0 5 0.22727272727272727
Deri.java 24 19 0.7916666666666666 0 0.0 5 0.20833333333333334
Main.java 28 27 0.9642857142857143 0 0.0 1 0.03571428571428571
Num.java 32 27 0.84375 0 0.0 5 0.15625
Expr.java 39 32 0.8205128205128205 0 0.0 7 0.1794871794871795
Var.java 44 39 0.8863636363636364 0 0.0 5 0.11363636363636363
Func.java 45 41 0.9111111111111111 0 0.0 4 0.08888888888888889
Term.java 48 42 0.875 0 0.0 6 0.125
Power.java 54 47 0.8703703703703703 0 0.0 7 0.12962962962962962
Lexer.java 66 58 0.8787878787878788 0 0.0 8 0.12121212121212122
Poly.java 77 69 0.8961038961038961 0 0.0 8 0.1038961038961039
Cos.java 98 90 0.9183673469387755 0 0.0 8 0.08163265306122448
Sin.java 102 95 0.9313725490196079 0 0.0 7 0.06862745098039216
Parser.java 151 140 0.9271523178807947 0 0.0 11 0.0728476821192053
StrHandler.java 245 228 0.9306122448979591 1 0.004081632653061225 16 0.0653061224489796
Mono.java 315 295 0.9365079365079365 0 0.0 20 0.06349206349206349

###2.2方法

Method CogC ev(G) iv(G) v(G)
Cos.Cos() 0 1 1 1
Cos.derivation(String) 5 3 4 4
Cos.getIndex() 0 1 1 1
Cos.getPoly() 8 1 6 6
Cos.setIndex(String) 0 1 1 1
Cos.setParameter(Factor) 4 1 4 4
Deri.derivation(String) 0 1 1 1
Deri.getPoly() 0 1 1 1
Deri.setExp(Factor) 0 1 1 1
Deri.setFac(String) 0 1 1 1
Expr.Expr() 0 1 1 1
“Expr.addTerm(Term, int)” 0 1 1 1
Expr.derivation(String) 2 1 3 3
Expr.getPoly() 2 1 3 3
Factor.derivation(String) 0 1 1 1
Factor.getPoly() 0 1 1 1
Factor.getSign() 0 1 1 1
Factor.setSign(int) 0 1 1 1
“Func.funcStruct(String, HashMap<String, Func>)” 2 1 3 3
Func.getContent(String[]) 1 1 2 2
Func.getSum() 0 1 1 1
Lexer.Lexer(String) 0 1 1 1
Lexer.getCurToken() 0 1 1 1
Lexer.getNum() 2 1 3 3
Lexer.getPos() 0 1 1 1
Lexer.isSign() 4 3 3 5
Lexer.next() 9 2 3 8
Main.main(String[]) 2 1 3 3
Mono.Mono() 0 1 1 1
Mono.Mono(Mono) 0 1 1 1
“Mono.addCos(String, BigInteger)” 2 1 2 2
Mono.addSame(Mono) 6 1 7 7
“Mono.addSin(String, BigInteger)” 2 1 2 2
Mono.addTris(Mono) 2 1 3 3
Mono.clearHash() 0 1 1 1
Mono.compareTo(Mono) 0 1 1 1
“Mono.getPrint(int, int)” 28 3 20 22
Mono.isFang(Mono) 34 9 15 15
Mono.isSame(Mono) 4 3 2 4
Mono.isSameFang(Mono) 2 2 1 2
Mono.mulMono(Mono) 8 1 7 7
Mono.printTri(int) 47 1 17 17
“Mono.setMono(BigInteger, BigInteger, BigInteger, BigInteger, int)” 0 1 1 1
Mono.turnNeg() 0 1 1 1
Num.Num(String) 0 1 1 1
Num.derivation(String) 0 1 1 1
Num.getPoly() 0 1 1 1
Parser.Parser(Lexer) 0 1 1 1
Parser.paresDer(int) 0 1 1 1
Parser.paresSin(int) 1 2 2 2
Parser.parseCos(int) 1 2 2 2
Parser.parseExpr() 7 1 4 5
Parser.parseFac() 15 8 11 11
Parser.parseTerm() 1 1 2 2
Poly.Poly() 0 1 1 1
Poly.addMono(Mono) 10 5 5 6
Poly.addPoly(Poly) 1 1 2 2
Poly.getPrint() 3 1 2 3
Poly.mulPoly(Poly) 3 1 3 3
Poly.turnNeg() 1 1 2 2
“Power.Power(Factor, String)” 0 1 1 1
Power.derivation(String) 4 2 3 3
Power.getPoly() 2 2 2 3
Sin.Sin() 0 1 1 1
Sin.derivation(String) 5 3 4 4
Sin.getIndex() 0 1 1 1
Sin.getPoly() 8 1 6 6
Sin.setIndex(String) 0 1 1 1
Sin.setParameter(Factor) 9 1 6 6
StrHandler.findBracket(String) 7 5 1 5
“StrHandler.funcHandle(String, HashMap<String, Func>)” 5 1 3 5
StrHandler.isNum(String) 5 4 1 5
StrHandler.isTurnNeg(String) 9 1 1 9
StrHandler.noBracket(String) 12 2 1 9
StrHandler.noSign(String) 3 3 3 4
StrHandler.noSignNum(String) 8 4 3 8
StrHandler.noZero(String) 3 2 2 4
“StrHandler.parseFunc(String, HashMap<String, Func>)” 12 1 5 7
StrHandler.strHandler(String) 17 1 4 8
“StrHandler.strHandler(String, HashMap<String, Func>)” 17 1 4 8
Term.Term() 0 1 1 1
Term.addFac(Factor) 0 1 1 1
Term.derivation(String) 7 1 5 5
Term.getPoly() 2 1 3 3
Var.Var(String) 0 1 1 1
Var.derivation(String) 2 1 2 2
Var.getPoly() 3 1 4 4
Total 359 136 247 307
Average 4.13 1.56 2.84 3.53

###2.3类

Class OCavg OCmax WMC
Cos 2.83 6 17
Deri 1.00 1 4
Expr 2.00 3 8
Factor 1.00 1 4
Func 2.00 3 6
Lexer 2.50 7 15
Main 3.00 3 3
Mono 4.50 17 72
Num 1.00 1 3
Parser 3.00 9 21
Poly 2.83 6 17
Power 2.33 3 7
Sin 3.17 6 19
StrHandler 5.18 7 57
Term 2.50 5 10
Var 2.33 4 7
Total 270
Average 3.10 5.12 16.88

二、核心架构

1.表达式

graph TB
Expr --> Term_1
Expr --> Term_2
Expr --> Term_n
Term_1 --> Factor_1
Term_1 --> Factor_2
Term_1 --> Factor_3
Term_1 --> Factor_4
Term_1 --> Factor_5
Term_1 --> Factor_6
Term_1 --> Factor_7
Factor_2 --> p_expr
Factor_2 --> p_num
Factor_3 --> d_expr
Factor_3 --> d_var
Factor_4 --> s_fac
Factor_4 --> s_index
Factor_5 --> c_fac
Factor_5 --> c_index
Expr((Expr))
Term_1((Term_1))
Term_2((Term_2))
Term_n((Term_n))
Factor_1((Expr))
Factor_2((Power))
Factor_3((Deri))
Factor_4((Sin))
Factor_5((Cos))
Factor_6((Var))
Factor_7((Num))
p_expr((Expr))
p_num((index))
d_expr((Expr))
d_var((var))
s_fac((Factor))
s_index((index))
c_fac((Factor))
c_index((index))

2.多项式

graph LR
Expr((Expr))
Term1((Term_1))
Term2((Term_2))
Termn((Term_n))
Factor1((Factor_1))
Factor2((Factor_2))
Factorn((Factor_n))
Expr --> Term1
Expr --> Term2
Expr --> Termn
Term1 --> Factor1
Term1 --> Factor2
Term1 --> Factorn
Factor1 --getPoly--> fp1((Poly1))
Factor2 --getPoly--> fp2((Poly2))
Factorn --getPoly--> fpn((Polyn))
tp1((newPoly1))
tp2((newPoly2))
tpn((newPolyn))
fp1 --multPoly--> tp1
fp2 --multPoly--> tp1
fpn --multPoly--> tp1
Term2 --Factors getPoly multPoly-->tp2
Termn --Factors getPoly multPoly-->tpn
ep1((resultPoly))
tp1 --> ep1
tp2 --> ep1
tpn --> ep1

3.数学公式

resultPoly=∑i=0n∏j=0mfactorPolyresultPoly = \sum_{i=0}^n \prod_{j=0}^m factorPoly

4.架构设计体验

第一次作业

    第一次作业比较简单，但由于考虑到之后的迭代开发，还是选择了递归下降，此时的代码可以处理括号嵌套的表达式。预处理包括：去除多余的正负号仅保留必要的符号、去除空白符和制表符、将**替换为^；词法语法解析的整体思路参考了练习作业提供的代码；化简在计算的过程中进行，Mono的标准形式为 Mono = ax^i^y^j^z^k^，在单项式计算的时候采用深克隆

第二次作业

     第二次迭代增加了括号嵌套、自定义函数、三角函数因子。递归下降已经解决括号嵌套；对于自定义函数将其放到预处理中，也用递归下降先对自定义函数进行表达式化简，之后替换；在Mono中添加两个HashMap<String, index>分别记录三角函数的参数与指数，Mono的标准形式变为：$Mono = ax^i^y^j^z^k^ \prod^{i=0} sin \prod^{i=0} cos$。判断同列项（除了常数）去掉常数项后的字符串比较，为了保证sin（x+y）和sin（y+x）能够化简，在Poly的getPrint方法中，需要先对mono实现comparable接口重写比较方法。

第三次作业

     第三次迭代增加了自定义函数的递归调用、求导因子。自定义函数只需要在预处理的过程中像处理第二次表达式的方式处理即可；求导因子我们就当做新加因子，在表达式getPoly的时候处理，利用求导法则分别写出Expr、Term、其他因子的求导方法即可。

    由于第二次优化没有做多少，所以第三次最主要是两个优化，sin（y-x）+sin（x-y）和sin^2^+cos^2^。第一个比较好做，只需要在打印三角函数参数的时候依据正负号的数量和字符串比较来实现；第二个优化类似同列项判断，在Mono相加的时候遍历两个三角函数HashMap，判断另一个Mono中去掉相应的项之后的是否为同类项。此时便会出现新情况，例如：sin(x)*cos(x)+sin(x)^3^*cos(x)+cos(x)^3^*sin(x) 化简时出现新的同类项，对此我的做法是递归化简（乱起的名），以上述为例，先将后两项相加得到Mono：sin(x)*cos(x)，之后在Poly中删除刚刚化简得到的Mono，再将该Mono加入Poly中，发现同类项合并得到2*sin(x)*cos(x), 重复上述过程，删除2*sin(x)*cos(x)，再加到Poly中发现没有同类项，到此合并完成。

5.架构的优缺点

  • 优点

    • 求导因子，在求导因子生成多项式的时候再处理，可以复用之前的Poly相乘和相加的方法，且不会涉及深浅克隆问题
    • 三角函数存储方式为String，这样优点很明显，比如仅需要调用一次内层因子的打印函数
    • 边计算边化简，递归化简会比单独写一个化简函数方便，也更符合程序的流程
    • 可以处理求导因子的嵌套

  • 缺点

    • 对于自定义函数应该也当做因子处理，在解析的过程中替换，而不是在预处理中替换
    • 由于父类Factor拥有属性sign，但是在解析中真正有正负的只有Num和Term，其他的都默认为符号为1。在我的架构中埋下了隐患，这会在下面谈到

三、Bug

  • 第一次
    • 互测竟然没有挨刀，在系数为1的时候，特判条件太多，造成漏洞，1 * y * z输出yz
    • 0-x+x没有输出，这是因为-x+x合并完之后产生新的同类项，但是这个在互测和强测都没有测出来，自己也没注意到
  • 第二次
    • 1-x+x，哎，第一次作业埋的雷
    • sin(0) ** 0=0 在判断的时候先判断了sin参数是否为0
    • x**21 输出为x* * x1 直接对Mono输出的字符串直接进行替换
  • 第三次
    • dx(sin((-x))) 输出cos(x) 承接上文我的架构，由于我的sin因子里有Factor属性，Poly属性（Factor生成），在提负号到外面的时候只改变了Poly的符号（将所有Mono变号），但是没有把Factor变号。就算变号，由于（-x）是表达式因子，而在我的架构中表达式默认符号为正
  • 总结出现的bug
    • if特判条件，能否把所有的情况都考虑到，是否会漏到一些情况，应该优点判断那些情况
    • 直接对字符串处理是一件愚蠢至极的方法
    • 迭代产生的bug，大多数都是复用之前的方法导致错误

四、Hack策略

列举一些hack成功的例子

  • 边界条件

    • sin((-x)) --> sin(-x)

    • 1
f(x)=cos(cos(cos(cos(x))))
sin(sin(cos(cos(cos(cos(cos(cos(dx(f(x)))))))))) --> TLE                 利用cost条件实现TLE

      1
      2
      3
      4
      5
      6
      7

      *  求导因子出现的位置，对特殊的因子求导

        * ```
          1
          f(x,y) = ((+x))**2+y
          -dx(f(y,0))+y
      


    • 2
f(x,y,z)=x-(y+z)
g(x,z,y)=-dz((y-z)**2)
-(f(0,-1,+1)-g(x**+0,x**+2,x**01))

      1
      2
      3
      4
      5
      6

      * ```
        2
        f(x) = sin(cos(x))
        g(y ) = dy(f(y))
        g(y)

    五、心得体会

      在第一次和第二次我几乎都没怎么做测试，第三次测试也只是把第二次数据改了改添加了求导因子，然后和室友python对拍，结果就是三次作业都有bug，下周说什么也得把评测机写出来。在写代码的时候尽量保证程序正义性，再结合随机测试数据和评测机才是正道！！

   复用之前的方法很容易出bug，接口的实现尤为重要，对于每个方法都需要清楚知道输入限制及方法的作用，迭代之后是否还能接着用。慢工出细活，写OO还是得抽出连续大量的时间，且要长时间专注。递归下降确实好用，但就是感觉缺少了一点面向对象的思想，第一单元感觉就像是数据结构哈哈哈哈。感觉评测没有上学期的OOpre覆盖性强，一个点就好几千上万条数据，bug还得靠互测。

    ​

OO
#OO #总结 #递归下降
OO第一单元总结
https://etherialize.github.io/2023/03/18/OO第一单元总结/
作者
HZY
发布于
2023年3月18日
许可协议