Один из способов сделать это - это запустить первый поток в начале строки и использовать стек для обработки первой половины строки. Второй поток начинается в конце строки и обрабатывает вторую половину строки в обратном порядке.
Если оба потока завершили эту первую фазу, то первая нить рассматривает стек второго потока как продолжение строки.
Так, к примеру, у вас есть:
[({(())}[])]
нить 1 получает [({(()
, и поток 2 получает )}[])]
каждый из них обработку тир отделки, в результате чего в этих двух стеков (левая вершина стека):
`({([` `)})]`
Затем нить 1 может превратить поток 2 в стек в строку (или рассматривать стек в виде строки, выскакивает один символ за один раз), а также со ntinue его обработки.
Подумайте об этом, когда две нити обработаны своей половиной строки, два стека должны быть одинаковой длины, и они являются зеркалами друг друга. Стек первого потока будет содержать только открывающие разделители (например, '(', '[' или '{'), а стек второго потока будет содержать только закрывающие разделители. Таким образом, после того как оба потока завершатся с половиной обработки, заключительная часть просто:
while (stack1.Count > 0 && stack2.Count > 0)
{
left = stack1.Pop();
right = stack2.Pop();
if (!delimiters_match(left, right))
{
// error!
}
}
Обратите внимание, что в любое время обработки, это возможно либо нить для обнаружения ошибки, например, при:.
([){})[)
Первая нить знает, что ошибка произошел в третьем символе, потому что у вас не может быть )
сразу последовать за [
. Аналогичным образом второй ead знает, что есть ошибка с [
(рядом с последним символом), потому что вы не можете иметь [
непосредственно перед )
.
Но некоторые ошибки могут быть обнаружены только во время второй фазы. Например:
({[}])
Подлинности слева и справа действительны, но в сочетании они не являются.