这是DSA 2023 Spring PA 2的Polynomial的解题报告，内容涉及使用栈实现中缀表达式求值。
A.所使用数据结构与算法的构思、原理和实现要点
所使用的数据结构：
为实现中缀表达式求值，使用了两个栈。每个栈是用数组实现的。
算法构思：
1、仿照中缀表达式求值，对输入的多项式中的元素进行逐个处理。
2、考虑到是对多项式进行计算，需要重新实现一个多项式类，替代普通中缀表达式求值中的数字。这里的数字，会以一个0次多项式的身份被处理。
3、多项式的加减乘除计算，使用OOP的运算符重载实现。
实现要点：
1、对于需要补充符号的情况要考虑全面。
2、多项式类显然需要维护一个储存当前多项式最高次的量，不然会运算超时。
3、考虑到每次次幂最高四次，应该把它的运算直接展开，确保每个次幂运算使用最多两次乘法进行替代。
4、考虑到题目没有对每一项的系数大小范围作出限制，必须在读入数据时就对系数不断取模，否则可能超出 longlong 上限。
5、用int存储数据，计算时把int转化为long long计算，算后转回int。
B.完成过程中遇到的问题，排除问题的主要过程、使用的方法和技巧，以及参考资料
问题1：第七测试点 Wrong Answer
发现自己的程序没有考虑结果为0的情况，修正后得以通过。
问题2：部分测试点超时
使用了以下办法进行时间节省：
1、把原先使用列表实现的栈改为用数组实现，避免反复new和delete耗时。
2、多项式加法使用“判断大于1000000007时减去1000000007”来替代对1000000007取模。但是效果并不明显，后来取消。
3、多项式乘法在系数相乘时，只对不为0的系数进行相乘。
4、多项式乘法在系数相乘时，并不是每一次都直接取模，而是计算6-7次之后再取模。但是效果并不明显，后来取消。
参考资料
除了习题课PPT，没有参考其他资料。
C.时间和空间复杂度的估算
时间复杂度
这个程序整体上对于输入多项式进行了从头到尾的一次遍历，复杂度为O(n)。
栈的末尾元素读取、删除、加入等操作，复杂度为O(1)。
多项式计算的复杂度，加法和减法为O(n)，乘法为O(n^2)，n代表多项式最高次项次数。
空间复杂度
输入的字符串长度上限为n，则需要的两个栈空间长度应该均为n/2；其中运算符栈每个元素是一个char，多项式栈每个元素是一个含有65位数组的自定义量，所以空间复杂度为O(n)。