我必须编写一个函数（在Java中，但语言并不重要），该函数以带圆括号的表达式（作为字符串）作为输入，并返回所有不匹配圆括号的索引的集合。
该函数必须只使用一个堆栈作为辅助数据结构。
例子：
Input: ”d(f(b)())o”
Return:[]
Input: ”**)**(d(f(b)())) **)** o **(**”
Return:[0, 12, 14]
解决这个问题的正确算法是什么？
最佳答案
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是一个关闭paren，检查堆栈上是否有任何打开paren如果有一个打开的paren，从堆栈中弹出它（我们找到了一个匹配项）；如果没有，我们有一个不匹配的paren，记录索引
最后，如果堆栈中还有任何paren，则它们是不匹配的，弹出索引
indexStack编辑：对不起，没有处理不匹配的打开paren