用于计算括号平衡的分布式算法

Question

这是一个采访问题:"如何构建分布式算法来计算括号的平衡？"

通常他的平衡算法从左到右扫描一个字符串形式,并使用一个堆栈来确保开括号的数量总是> =闭括号的数量,最后是开括号的数量==近括号的数量.

你会如何分发它？

Answer 1

您可以将字符串分成块并单独处理,假设您可以并行读取并发送到其他计算机.每个字符串需要两个数字.

1. 相对于字符串的开头实现的最小嵌套深度.

2. 整个字符串中嵌套深度的总增益或损失.

使用这些值,您可以计算多个块的串联值,如下所示:

minNest = 0
totGain = 0
for p in chunkResults
  minNest = min(minNest, totGain + p.minNest)
  totGain += p.totGain
return new ChunkResult(minNest, totGain)

如果最终值括号匹配totGain和minNest为零.