java - 查找不匹配括号的索引

Question

我必须（在 Java 中，但语言并不重要）编写一个函数，该函数将带括号的表达式（作为字符串）作为输入并返回所有不匹配括号的索引的集合。

该函数必须仅使用堆栈作为辅助数据结构。

例子：

Input: ”d(f(b)())o”
Return:[]

Input: ”**)**(d(f(b)())) **)** o **(**”
Return:[0, 12, 14]

解决这个问题的正确算法是什么？

Answer 1

Stacks括号匹配实际上是光荣的。在伪代码中，它看起来像

indices = []

for i->0, i<length(string), i++ do

    if string[i] == "(" then
        stack.push("(")
        indexStack.push(i)

    else if string[i] == ")" then
        if stack.size() < 1 then
            indices.append(i)
        else
            stack.pop()
            indexStack.pop()

while indexStack.size() > 0 do
     indices.append(indexStack.pop())

至于这是如何工作的解释。

• 遍历字符串
• 如果char是一个开放的paren，则将其压入堆栈
• 如果char是关闭的括号，请检查堆栈上是否有任何打开的括号
• 如果有一个开放的括号，则将其从堆栈中弹出（我们找到了匹配项）；如果没有，我们有一个不匹配的括号，记录索引
• 最后，如果堆栈中还有任何括号，它们是不匹配的，弹出索引关闭indexStack

编辑：对不起，没有处理无与伦比的开放括号

Answer 2

你可以...

1. 从左到右，检查每个字符
2. 如果它是一个开括号，则将其添加到堆栈中。将此号码添加到列表中。
3. 如果它是一个右括号，则从堆栈中弹出。如果无法弹出，则将当前字符索引添加到列表中。
4. 如果可以弹出，则从打开的括号列表中删除最后一个索引。
5. 重复步骤 2 和 3，直到完成

您可以有 2 个列表，一个负责开括号，另一个负责闭括号。这将使删除索引时更容易。