### 使用栈或队列实现一元多项式加减乘除 在一元多项式的运算中，可以利用栈或队列作为辅助数据结构来处理表达式的解析和计算。下面详细介绍如何使用这些数据结构完成加法、减法、乘法以及除法的操作。 #### 1. 多项式表示 为了便于操作，可以用列表的形式存储多项式中的每一项。例如，对于多项式 `P(x) = 3x^2 + 2x + 1` 和 `Q(x) = -x^2 + 4x - 5`，可以通过如下方式表示： ```python P = [(3, 2), (2, 1), (1, 0)] # 表示系数和幂次 Q = [(-1, 2), (4, 1), (-5, 0)] ``` 其中 `(a, b)` 表示一项，`a` 是该项的系数，`b` 是对应的幂次。 --- #### 2. 加法与减法 加法和减法的核心在于按幂次合并同类项。以下是具体实现方法： ##### **加法** 通过遍历两个多项式并按照相同的幂次累加系数即可完成加法。 ```python def polynomial_addition(P, Q): result = [] i, j = 0, 0 while i < len(P) and j < len(Q): if P[i][1] > Q[j][1]: result.append(P[i]) i += 1 elif P[i][1] < Q[j][1]: result.append(Q[j]) j += 1 else: coeff_sum = P[i][0] + Q[j][0] if coeff_sum != 0: # 去掉零系数项 result.append((coeff_sum, P[i][1])) i += 1 j += 1 # 添加剩余部分 result.extend(P[i:]) result.extend(Q[j:]) return result ``` ##### **减法** 减法类似于加法，只需将第二个多项式的系数取反后再执行加法逻辑。 ```python def polynomial_subtraction(P, Q): Q_negated = [(-q[0], q[1]) for q in Q] # 取反第二个多项式 return polynomial_addition(P, Q_negated) ``` --- #### 3. 乘法 乘法涉及两层嵌套循环，每一对项相乘后需将其结果加入最终的结果集中，并按幂次整理。 ```python def polynomial_multiplication(P, Q): result_dict = {} for p_coeff, p_exp in P: for q_coeff, q_exp in Q: new_coeff = p_coeff * q_coeff new_exp = p_exp + q_exp if new_exp not in result_dict: result_dict[new_exp] = 0 result_dict[new_exp] += new_coeff # 转换回有序形式 result = sorted([(v, k) for k, v in result_dict.items() if v != 0], key=lambda x: x[1], reverse=True) return result ``` --- #### 4. 除法 多项式除法较为复杂，通常采用长除法的方式逐步分解商和余数。这里提供一种基于迭代的方法。 ```python def polynomial_division(P, Q): quotient = [] # 商 remainder = list(P) # 初始被除数即为余数 while remainder and remainder[0][1] >= Q[0][1]: # 当前最高次大于等于除数最高次 leading_term_quotient = (remainder[0][0] // Q[0][0], remainder[0][1] - Q[0][1]) quotient.append(leading_term_quotient) temp_poly = [(leading_term_quotient[0] * q[0], leading_term_quotient[1] + q[1]) for q in Q] remainder = polynomial_subtraction(remainder, temp_poly) return quotient, remainder ``` --- ### 完整代码示例 以下是一个完整的程序演示上述功能： ```python def display_polynomial(poly): terms = ["{}x^{}".format(a, b) if b != 0 else "{}".format(a) for a, b in poly] return " + ".join(terms) # 测试多项式 P = [(3, 2), (2, 1), (1, 0)] Q = [(-1, 2), (4, 1), (-5, 0)] print("P:", display_polynomial(P)) print("Q:", display_polynomial(Q)) add_result = polynomial_addition(P, Q) sub_result = polynomial_subtraction(P, Q) mul_result = polynomial_multiplication(P, Q) div_result, rem_result = polynomial_division(P, Q) print("\nP + Q =", display_polynomial(add_result)) # 输出加法结果 print("P - Q =", display_polynomial(sub_result)) # 输出减法结果 print("P * Q =", display_polynomial(mul_result)) # 输出乘法结果 print("P / Q =", display_polynomial(div_result), "(Remainder:", display_polynomial(rem_result), ")") # 输出除法结果 ``` --- ### 数据结构的选择 在以上实现中，主要依赖于列表（List），其本质是动态数组[^1]。然而，在某些场景下也可以考虑使用栈或队列来优化特定步骤： - 如果需要逐项读取输入，则可借助队列先进先出的特点。 - 对于逆序操作或者临时缓存中间结果，栈可能更为合适。 尽管如此，本案例并未强制绑定到某种单一的数据结构上，而是灵活运用多种工具达成目标。 ---