Java查找循环结构的方法

Question

S.No   Entry
1      jack
2      dummy
3      Jones 
4      jack
5      jack
6      dummy
7      jones
8      Jones 

上表可以这样理解，

Jack{
  Dummy
}Jones

Jack{
    Jack{
     Dummy
   }Jones 
}Jones 

我试图找出每个插孔是否都可以使用琼斯。 (即)对于每个开括号( jack )，应该有一个闭括号(琼斯)。

如果 Jones 不在，则应返回 S.No，如下所示，

Jack{
  Dummy
}Jones

Jack{
  Jack{
    Dummy
  }here Jones is missing 
}Jones 

输出应该是S.No5..它没有琼斯。

实现这个逻辑的最佳方法是什么？我尝试计数和操作它，但找不到 S.no。

Answer 1

您可以使用堆栈数据结构递归或迭代地执行此操作。

对于迭代方法，创建一个堆栈来存储 jack 条目的位置。

堆栈将发生如下变化(顶部在左侧)

Entry    Stack  Result
jack     [1]    empty
dummy    [1]    empty
Jones    []     1
jack     [4]    1
jack     [5, 4] 1
dummy    [5, 4] 1
Jones    [4]    5
Jones    []     4

当您看到 jack 时，您会将其位置存储在堆栈顶部。当您看到 Jones 时，您会弹出堆栈，并将数字分配给结果。

如果最后一个 Jones 丢失，堆栈更改将如下所示:

Entry    Stack  Result
jack     [1]    empty
dummy    [1]    empty
Jones    []     1
jack     [4]    1
jack     [5, 4] 1
dummy    [5, 4] 1
Jones    [4]    5

现在结果是 5，因为在我们用完列表条目后，4 仍然留在堆栈上。