1

问题1 给
你一个只包含字符的字符串'(', ')', '{', '}', '[' and ']'，例如，"[{()}]"你需要编写一个函数来检查这样一个输入字符串的有效性。

我可以使用堆栈来做到这一点。

Ques2
同时使用多个处理器。

如何做呢 ？

据我说，它不能完成，因为：
让我们假设我们有 3 个处理器，输入字符串是：([{([])}])并将 3 个处理器划分为：
1st：([{
2nd：([]
3rd：)}])
现在应用程序，我们从所有 3 个中得到 FALSE处理器，因此它不能通过并行处理来解决。
Is it right or parallel processing means something else ?

4

2 回答 2

3

一种方法是让第一个线程从字符串的开头开始，并使用堆栈来处理字符串的前半部分。第二个线程从字符串的末尾开始，反向处理字符串的后半部分。

当两个线程都完成了第一个阶段时，第一个线程将第二个线程的堆栈视为字符串的延续。

因此，例如，您有：

[({(())}[])]

线程 1 得到[({(()，线程 2 得到)}[])]

他们每个人都完成了他们的处理，产生了这两个堆栈（左边是堆栈的顶部）：

`({([`  `)})]`

然后线程 1 可以将线程 2 的堆栈变成一个字符串（或将堆栈视为一个字符串，一次弹出一个字符），并继续其处理。

想想看，当两个线程处理完它们的一半字符串时，两个堆栈必须是相同的长度，并且它们是彼此的镜像。第一个线程的堆栈将只包含开始分隔符（即'（'、'['或'{'），而第二个线程的堆栈将只包含关闭分隔符。所以在两个线程完成了它们的一半处理后，最后一部分很简单：

while (stack1.Count > 0 && stack2.Count > 0)
{
    left = stack1.Pop();
    right = stack2.Pop();
    if (!delimiters_match(left, right))
    {
        // error!
    }
}

请注意，在处理过程中的任何时候，任何一个线程都可能检测到错误。例如，给定：

([){})[)

第一个线程知道第三个字符发生了错误，因为您不能)立即 follow [。同样，第二个线程知道[(next to last character) 有错误，因为您不能[立即使用 before )。

但是有些错误只能在第二阶段检测到。例如：

({[}])

左右子串是有效的，但组合起来却不是。

于 2013-11-11T15:21:01.710 回答
2

好吧，您选择的示例无法以您设置的方式并行解决。

请考虑一个测试表达式，例如 200000 个字符。拆分超过 2 个处理器（让我们保持简单）。每个处理器：

  1. 扫描其子字符串中出现的[],{}或(), 即构成有效字符串的两个连续符号。当它发现这种情况时，它只是将其删除。
  2. 重复步骤 1，直到不再对子字符串进行更改。
  3. 重新组合子字符串并让 1 个处理器重复步骤 1，直到没有更多变化。

我希望比我现在有更多时间的人可以构建如此长的示例，以至于在 2、4、8、... 处理器或 3、6、9、... 之间进行递归拆分是值得的。我希望也可以构建显示没有加速的示例，实际上相反，如果在处理器之间拆分。

于 2013-11-11T15:10:37.900 回答