查找不匹配括号的下标

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是一个打开父级，将其压入堆栈
• 如果char是关闭父级，检查堆栈上是否有打开父级
• 如果有一个打开父级，把它从堆栈中弹出(我们已经找到了一个匹配);如果没有，我们有一个不匹配的父级，记录索引
• 最后，如果堆栈中有任何父节点，它们是不匹配的，将索引从indexStack
弹出。

编辑:对不起，没有处理不匹配的父字符

Answer 2

你可以…

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

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