2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2, 3  След.
 
 проверить расстановку скобок в тексте
Сообщение04.10.2009, 00:55 
возникла необходимость проверки правильности расстановки скобок в тексте, т.е. текст должен быть написан таким образом, чтобы не было лишних скобок(я имею ввиду, что открывающих скобок должно быть столько же, сколько и открывающих), и чтобы они были расставлены в правильном порядке.

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

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

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

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

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

 
 
 
 Re: проверить расстановку скобок в тексте
Сообщение04.10.2009, 01:39 
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;
}

 
 
 
 Re: проверить расстановку скобок в тексте
Сообщение04.10.2009, 19:08 
Цитата:
И ещё вы, C'шники обвиняете нас, C++'ников в нерациональном усложнении кода?

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

 
 
 
 Re: проверить расстановку скобок в тексте
Сообщение04.10.2009, 21:13 
воспользуйтесь стеком

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

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

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

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

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

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

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

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

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

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

 
 
 
 Re: проверить расстановку скобок в тексте
Сообщение07.10.2009, 12:16 
Господа, а в чем принципиальное отличие в данном случае стека от счетчика, кроме бесполезного расхода памяти стека?

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

 
 
 
 Re: проверить расстановку скобок в тексте
Сообщение07.10.2009, 12:28 
e2e4 в сообщении #249734 писал(а):
Господа, а в чем принципиальное отличие в данном случае стека от счетчика, кроме бесполезного расхода памяти стека?
Принципиальное отличие, на мой взгляд, заключается в том, что простой счетчик в данном случае выглядит вполне естественно, а стек, который может содержать только открывающие скобки, слегка притянут за уши :)

 
 
 
 Re: проверить расстановку скобок в тексте
Сообщение07.10.2009, 15:24 
p51x в сообщении #249724 писал(а):
В чем проблема? Если скобка закрывающая и (стек пуст или извлеченная скобка не соотв.) - ошибка
В том, что по Вашему предложению поставлено условие: "этого не может быть".

p51x в сообщении #249724 писал(а):
PapaKarlo в сообщении #249673 писал(а):
во-вторых, и при выполнении этого условия возможна ситуация, эквивалентная его невыполнению: закрывающихся скобок больше, чем открывающихся.
не возможна. см. проверку выше.
Программную проверку? Никакая программная проверка не может повлиять на данность - проверяемый текст. :mrgreen:

p51x в сообщении #249724 писал(а):
PapaKarlo в сообщении #249673 писал(а):
И самая главная ошибка в подходе - ограничение (может быть, неявное) рассмотрением ситуации "если... то все в порядке".
А какой же правильный подход?
Правильный подход - предполагающий, что в тексте может быть любая последовательность скобок. В общем случае правильный подход заключается в том, что входные данные могут отличаться от спецификации, ограничивающей применительно к конкретной задаче формат/содержимое входного потока.

p51x в сообщении #249724 писал(а):
Вот и стоит задача "проверить правильность".
Тогда почему предлагается
Gendolf в сообщении #249652 писал(а):
поставить условие, что первый элемент не может быть закрывающейся скобкой
Возможно, я просто не понял, в каком смысле Вы предлагали поставить данное условие.

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

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

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

 
 
 
 Re: проверить расстановку скобок в тексте
Сообщение07.10.2009, 17:01 
worm2 в сообщении #249834 писал(а):
В такой вариант естественно вписываются и кавычки
Я, вообще-то, немного о другом говорил - о том, что скобки внутри строки, заключенной в кавычки, анализировать не надо.
Ну а в удобстве стека при реализации полноценного синтаксического анализа, наверное, вряд ли кто-нибудь сомневается. Хотя вручную такие вещи сейчас практически не пишутся - есть достаточное количество всяких яков, бизонов и других средств синтаксического анализа / компиляции.

 
 
 
 Re: проверить расстановку скобок в тексте
Сообщение08.10.2009, 09:57 
worm2 в сообщении #249834 писал(а):
И для такой задачи, разумеется, стек нужен.

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

 
 
 [ Сообщений: 34 ]  На страницу 1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group