找到不匹配的括号的索引

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是紧密的,请检查堆栈上是否有任何打开的parens
• 如果有一个打开的paren,从堆栈弹出它(我们找到了匹配); 如果没有,我们有一个无与伦比的paren,记录索引
• 最后,如果堆栈中还有任何parens,它们是不匹配的,pop指数关闭 indexStack

编辑:对不起,没有处理无与伦比的开放parens