проверить расстановку скобок в тексте

[malin]

возникла необходимость проверки правильности расстановки скобок в тексте, т.е. текст должен быть написан таким образом, чтобы не было лишних скобок(я имею ввиду, что открывающих скобок должно быть столько же, сколько и открывающих), и чтобы они были расставлены в правильном порядке.

Мне интересен только алгоритм, реализация не важна. Помнится, несколько лет назад я уже сталкивался с такой задачей, но вот сейчас вдруг забыл опять.

Хочу предложить свой алгоритм, который, возможно, можно улучшить.

int counter = 0;
if (первая встреченная скобка закрывающая)
{
cout<<"неправильно"<<endl;
getch();
exit(1);
}
else
{
ищем скобку дальше, если открывающая, инкрементируем counter, если нет, декрементируем.
как только счётчик обнуляется, начинаем всё сначала, т.е. ищем первую встретившуюся скобку и если она закрывающая, то неправильно, .... и т. д.
если в конце counter = 0, то всё правильно, если нет, то неправильно.
}

P.S.: прошу прощенья за ПСЕВДО псевдокод, если потребуется, немедленно напишу на чистом С++.

[e2e4]

По-моему, именно так (т.е. с использованием counter'а) эта задача и решается.
Вообще-то Вам бы поискать в гугле псевдокод реализации перевода инфиксной формы записи в обратную польскую нотацию (придуман Эдскером Дейкстрой) - возможно, это то, что Вам нужно.

[Circiter]

2malin
Все у вас вроде-бы правильно, в чем проблема? Разве-что можно словесный алгоритм записать немного короче: Обнуляем счетчик, затем последовательно считываем символы из входного потока и для каждого символа инкрементируем значение счетчика если попалась ( и декрементируем -- если ). Правильной расстановке скобок будет соответствовать неотрицательность значения счетчика в любой момент времени (т.е. нужна проверка на каждой итерации), а правильной балансировке -- равенство значения счетчика нулю по достижении конца потока.

2e2e4
И ещё вы, C'шники обвиняете нас, C++'ников в нерациональном усложнении кода?

-- Вс окт 04, 2009 06:06:47 --

Вот краткий набросок, вроде работает (возвращает 0 только в случае правильной расстановки скобок), хотя, возможно, я что-то и упустил:

#include <stdio.h>

int main(void)
{
    signed int p=0;
    char c;

    while(((c=getchar())!='\n')&&p>=0)
        if(c=='(') p++; else if(c==')') p--;

    return p;
}

[e2e4]

Цитата:

И ещё вы, C'шники обвиняете нас, C++'ников в нерациональном усложнении кода?

Я нигде не говорил, что предпочитаю Си Си++'у . А изучение алгоритма Декстры, может быть, натолкнет топикстартера на какие-нибудь более интересные мысли, чем простой подсчет скобок для своей задачи.

[p51x]

воспользуйтесь стеком

[Gendolf]

да, стек решение разумное.
поставить условие, что первый элемент не может быть закрывающейся скобкой, как только к нам пришла открывающаяся скобка, записываем её в стек, как только закрывающаяся - вытаскиваем открывающуюся из стека. если стек пуст, расстановка верна.

[PapaKarlo]

Gendolf в сообщении #249652 писал(а):

поставить условие, что первый элемент не может быть закрывающейся скобкой

Такое ограничение искусственно: во-первых, в реальной ситуации первый элемент может быть закрывающейся скобкой (ошибка, которую нельзя игнорировать); во-вторых, и при выполнении этого условия возможна ситуация, эквивалентная его невыполнению: закрывающихся скобок больше, чем открывающихся. Чем underflow в начале разбираемой конструкции хуже underflow не в начале? В общем, не задачу нужно подстраивать под алгоритм, а алгоритм под задачу. И самая главная ошибка в подходе - ограничение (может быть, неявное) рассмотрением ситуации "если... то все в порядке". В жизни не бывает все в порядке.

[p51x]

Цитата:

в реальной ситуации первый элемент может быть закрывающейся скобкой (ошибка, которую нельзя игнорировать)

В чем проблема? Если скобка закрывающая и (стек пуст или извлеченная скобка не соотв.) - ошибка

Цитата:

во-вторых, и при выполнении этого условия возможна ситуация, эквивалентная его невыполнению: закрывающихся скобок больше, чем открывающихся

не возможна. см. проверку выше.

Цитата:

И самая главная ошибка в подходе - ограничение (может быть, неявное) рассмотрением ситуации "если... то все в порядке".

А какой же правильный подход?

Цитата:

В жизни не бывает все в порядке.

Вот и стоит задача "проверить правильность".

[e2e4]

Господа, а в чем принципиальное отличие в данном случае стека от счетчика, кроме бесполезного расхода памяти стека?

P.S. Конечно, понимаю, что сам предложил автору посмотреть алгоритм Декстры, но необходимо понимать, что он оправдан в более общих случаях, при наличии нескольких разных операторов в одном выражении.

[Maslov]

e2e4 в сообщении #249734 писал(а):

Господа, а в чем принципиальное отличие в данном случае стека от счетчика, кроме бесполезного расхода памяти стека?

Принципиальное отличие, на мой взгляд, заключается в том, что простой счетчик в данном случае выглядит вполне естественно, а стек, который может содержать только открывающие скобки, слегка притянут за уши

[PapaKarlo]

p51x в сообщении #249724 писал(а):

В чем проблема? Если скобка закрывающая и (стек пуст или извлеченная скобка не соотв.) - ошибка

В том, что по Вашему предложению поставлено условие: "этого не может быть".

p51x в сообщении #249724 писал(а):

PapaKarlo в сообщении #249673 писал(а):

во-вторых, и при выполнении этого условия возможна ситуация, эквивалентная его невыполнению: закрывающихся скобок больше, чем открывающихся.

не возможна. см. проверку выше.

Программную проверку? Никакая программная проверка не может повлиять на данность - проверяемый текст.

p51x в сообщении #249724 писал(а):

PapaKarlo в сообщении #249673 писал(а):

И самая главная ошибка в подходе - ограничение (может быть, неявное) рассмотрением ситуации "если... то все в порядке".

А какой же правильный подход?

Правильный подход - предполагающий, что в тексте может быть любая последовательность скобок. В общем случае правильный подход заключается в том, что входные данные могут отличаться от спецификации, ограничивающей применительно к конкретной задаче формат/содержимое входного потока.

p51x в сообщении #249724 писал(а):

Вот и стоит задача "проверить правильность".

Тогда почему предлагается

Gendolf в сообщении #249652 писал(а):

поставить условие, что первый элемент не может быть закрывающейся скобкой

Возможно, я просто не понял, в каком смысле Вы предлагали поставить данное условие.

e2e4 в сообщении #249734 писал(а):

Господа, а в чем принципиальное отличие в данном случае стека от счетчика, кроме бесполезного расхода памяти стека?

В данном случае - никакого. В более общем случае синтаксического разбора отличие может возникнуть: стек не обязан содержать однородные элементы. Кроме того, стек является лишь абстрагированием доступа к данным (LIFO), а реализация может быть произвольной.

[Maslov]

Тут, кстати, есть еще один интересный вопрос: что из себя представляет текст, в котором надо проверять правильность расстановки скобок? И не может ли этот текст содержать правильных несбалансированных скобок внутри, например, закавыченных строк?

[worm2]

Я слышал "задачу о расстановке скобок" в варианте, который подразумевает несколько типов скобок (круглые, квадратные, фигурные, ...). В такой вариант естественно вписываются и кавычки (если приравнять их к скобкам, т.е. допустить их вложенность и потребовать, чтобы открывающая кавычка отличалась от закрывающей). И для такой задачи, разумеется, стек нужен.

[Maslov]

worm2 в сообщении #249834 писал(а):

В такой вариант естественно вписываются и кавычки

Я, вообще-то, немного о другом говорил - о том, что скобки внутри строки, заключенной в кавычки, анализировать не надо.
Ну а в удобстве стека при реализации полноценного синтаксического анализа, наверное, вряд ли кто-нибудь сомневается. Хотя вручную такие вещи сейчас практически не пишутся - есть достаточное количество всяких яков, бизонов и других средств синтаксического анализа / компиляции.

[ewert]

worm2 в сообщении #249834 писал(а):

И для такой задачи, разумеется, стек нужен.

Если речь только о кавычках -- то не нужен. Достаточно поставить флажок "мы внутри строки".