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

这是一个采访问题：“如何构建分布式算法来计算括号的平衡？” 通常他的平衡算法从左到右扫描一个字符串形式，并使用一个堆栈来确保开括号的数量总是> =闭括号的数量，最后是开括号的数量==近括号的数量。 你会如何分发它？     
2019-08-17 3 条评论
分享

没有找到相关结果

    已邀请:

    恋裂

    您可以将字符串分成块并单独处理，假设您可以并行读取并发送到其他计算机。每个字符串需要两个数字。 相对于字符串的开头实现的最小嵌套深度。 整个字符串中嵌套深度的总增益或损失。 使用这些值，您可以计算多个块的串联值，如下所示： 
    minNest = 0
totGain = 0
for p in chunkResults
  minNest = min(minNest, totGain + p.minNest)
  totGain += p.totGain
return new ChunkResult(minNest, totGain)
    如果
    totGain
    和
    minNest
    的最终值为零，则匹配括号。     
    2019-08-17 0 0
    分享

    掀辟髓观粟

    我将应用map-reduce算法，其中map函数将计算字符串的一部分，如果括号是平衡的，则返回空字符串，或者保留剩余最后一个括号的字符串。 然后reduce函数将通过map函数连接两个返回的字符串的结果，并再次计算它返回与map相同的结果。在所有计算结束时，您将获得一个空字符串或包含非平衡括号的字符串。     
    2019-08-17 0 0
    分享
    为什么被折叠? 0 个回复被折叠

    要回复问题请先登录或注册

    或代码 OrCode.com 备案号：粤ICP备15020848号-1
    Escape time: 0.03308892250061