Найти индексы непревзойденной скобки

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

EDIT: К сожалению, не обработал себе равных open parens

Answer 2

Вы могли бы ...

1. Go слева направо, рассматривая каждый символ
2. Если это открытая paranthesis добавить его в стек. Добавьте этот номер в список.
3. Если это закрытая всплывающая скобка из стека. Если вы не можете добавить, добавьте текущий индекс символов в список.
4. Если вы можете щелкнуть, то удалите последний индекс из открытого списка скобок.
5. Повторите шаги 2 и 3, пока вы не сделали

Вы можете иметь 2 списка один Заботясь о открывающей скобкой и еще один заботиться о закрытой скобкой. Это упростит удаление индексов.