algorithm - 未加括号的算术表达式

Question

一个算术表达式可以有很多可能的值

有人可以帮助我吗？

Answer 1

有一个动态规划解决方案。

对于表达式，您可以将其“最外层分割点”定义为第一个不在任何括号内的运算符。现在这个拆分之后，如果是在一个+上，那么你需要最大化左子表达式和右子表达式；如果是 -，则最大化左侧，最小化右侧。

您可以使用动态规划或内存来实现此算法。内存很简单:搜索每个分割点，并将答案保存在另一个数据结构中(两个二维矩阵，M[x][y] 字符串表达式的最大/最小值从 x 并以 y 结束)；当数据在矩阵中时，使用它而不是重新计算。

使用动态规划有点棘手，但你可以这样想:

1. 首先，您循环遍历表达式，找到每个连续的 2 个值的最大值/最小值以及它们之间的运算符(好吧，这是一种奇特的说法，只是计算它)；
2. 遍历表达式，为每个连续的 3 个值找到最大值/最小值，它们之间有运算符(对于 a ? b ? c，这是通过假设分割点在 a和b，假设分割点在b和c上，存储最大/最小值这两个)；
3. 一旦知道所有 k 长度序列的最大/最小值，使用与步骤 2 中相同的方法计算 k + 1 长度序列，直到 k是数组的长度，返回长度k的最大值。

这与Matrix Chain Multiplication 几乎相同算法，具有 O(N^3) 复杂度。复杂度可以通过推理粗略地证明:需要循环N - 1次，每次最多N - 1个子序列，最多需要尝试N - 1 个分割点。所以，N ^ 3 时间复杂度。