Polynomial

CST PA2

2-2 Polynomial

算法构思

将待计算字符串中的常数对象和变量 x 均视为多项式——常数视为零次多项式, x 视为一次多项式, 那么本题相当于一个中缀多项式表达式求值的过程.

因此基本思路与中缀表达式求值相同. 编写一个栈类 class Stack 存储运算数和运算符, 同时编写一个多项式类 class Poly 并重载 +、-、*、^ 运算符进行计算.

我们遍历读入的表达式, 同时设置一个多项式栈和运算符栈:

• 如果读入数字, 则持续遍历直到不再读到数字, 并将这些数字合并为一个完整的数后转换为零次多项式加入多项式栈.

接下来需要判断表达式中是否省略了 '*' 运算符.

• 如果当前字符为 '(' 或 'x', 此时读取当前字符的上一个字符并进行判断, 如果上一个字符为数字或 'x' 或 ')', 则说明此处省略了乘号. 此时将上一个字符改为乘号并返回处理即可 (因为上一个字符已处理完毕, 对其进行更改不会影响已有结果.)

接下来处理读取 'x' 情况和读取运算符情况即可.

• 如果读入 'x', 将其转换为一次多项式并加入多项式栈.
• 如果读入运算符, 则需比较当前运算符和运算符栈顶符号间的优先级:
  • 如果栈顶运算符优先级更低, 则推迟计算, 将当前运算符入栈;
  • 如果两运算符优先级相等, 那么当前运算符为 ')' 或者尾哨兵 '\0', 直接退栈并接收下一个字符即可;
  • 如果栈顶运算符优先级更高, 则取出多项式栈顶的两个元素执行运算并将结果压入多项式栈中.
• 最后多项式栈仅剩一个多项式对象, 即中缀表达式的最终运算结果. 将其记录的系数信息逐项输出即可.

数据结构

基于数组实现了栈的数据结构:

template <class T>
class Stack {
private:
    T* _a;
    int _size;
    int _capacity;
public:
    Stack(int capacity);
    bool empty();    
    int size();
    T& top();
    void push(const T& x);
    T pop();
};

其中每次基本操作时间复杂度均为 $O(1)$.

实现多项式类:

class Poly {
private:
    int coe[65];
    int deg;
public:
    Poly();
    Poly(long long a);
    Poly operator+(const Poly &x);
    Poly operator-(const Poly &x);
    Poly operator*(const Poly &x);
    Poly operator^(const Poly &x);
    void print();
};

初始化常数多项式, 使用构造函数 Poly(long long a); 初始化一次多项式, 使用构造函数 Poly().

在每次二元运算操作后, 将运算结果更新至第一个操作对象中, 同时更新其记录的最高次数.

问题发现与优化

开始的提交中测例 15 会出现 Time Limit Exceeded 的问题. 通过对代码具体实现进行了若干优化解决了该问题.

// Line 102
...
Poly operator*(const Poly &x) { // 实现 * 运算符.
    bool flag = false;
    long long tmp = 0;
    // 优先考虑被乘数为常数情况.
    if(deg == 0) {
        ...
    }
    // 再考虑乘数为常数情况.
    else if(x.deg == 0) {
        ...
    }
    else {
        ...
        }        
    }
    return *this;
}
...

推测是因为多项式乘法的时间常数过大, 导致实际运算超时. 在多项式乘法中添加了判断两个多项式次数是否为 0 的过程, 使得计算常多项式乘积耗时降低, 解决了测例 15 的 Time Limit Exceeded 问题.

复杂度估计

算法时间复杂度主要来自遍历输入表达式与多项式计算两部分:

在遍历输入表达式时, 每个元素最多入栈和出栈一次, 每次操作均为常数时间, 从而时间复杂度与输入表达式长度成正比, 为 $O(n)$;

在进行多项式计算时, 多项式栈中每两个对象经一次计算后返回一个对象. 若输入表达式能够贡献 k 个表达式, 则需进行 k - 1 次计算得出最终结果. 注意到幂运算所需时间最长, 因此最差情况为 64 次多项式进行幂运算, 所需为常数时间. 从而时间复杂度为 $O(n)$;

综上, 算法总时间复杂度为 $O(n)$, 具有小的时间常数.

算法空间复杂度主要来自读取字符串、转换为多项式并存储数据的过程:

由于输入串的长度上界为 1,000,000, 那么其实际可贡献同时入栈的多项式数和运算符数最坏情况也不会超过 Max = 900,000. 使用 Max 作为容量初始化栈:

...
Stack<Poly> opnd = Stack<Poly>(Max); // 多项式栈.
Stack<char> optr = Stack<char>(Max); // 运算符栈.
...

主要内存被分配给多项式栈与运算符栈, 程序占用的极限内存约为: $4B\times 66\times 9 \times 10^5 + 1B \times 9 \times 10^5 = 238500KB = 233.9MB < 256MB$.

恰好满足题意.