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

Question

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

该函数只需要使用一个堆栈作为辅助数据结构。

例子:

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

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

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

Answer 1

堆栈 实际上非常适合括号匹配。在伪代码中它看起来像

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 是闭括号，检查栈上是否有开括号
• 如果有一个开括号，将它从堆栈中弹出(我们找到了一个匹配项)；如果不是，我们有一个无与伦比的 parent ，记录索引
• 最后，如果堆栈中还有任何括号，则它们不匹配，弹出索引 indexStack

编辑:抱歉，没有处理不匹配的左括号