1 / 1 / 2
Регистрация: 27.09.2011
Сообщений: 78
1

Проверить,правильно ли в заданом тексте...

27.09.2011, 18:36. Показов 1000. Ответов 6
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Проверить правильно ли в заданом тексте расположены круглые скобки.Если да, то вывести значение ''true'', если нет - "false"
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
27.09.2011, 18:36
Ответы с готовыми решениями:

Проверить, правильно ли в тексте расставлены круглые скобки
Дан файл, содержащий произвольный текст. Проверить, правильно ли в нем расставлены круглые скобки...

Проверить, правильно ли в тексте данного файла расставлены круглые скобки
дан файл, содержащий произвольный текст. проверить, правильно ли в нём расставлены круглые...

Программа для подсчета кол-ва совпадений символов в заданом тексте
Создать програму для подсчета кол-ва совпадений символов в заданом тексте. По типу: 1)аб 2)абв...

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

6
Злой няш
2136 / 1505 / 565
Регистрация: 05.04.2010
Сообщений: 2,881
27.09.2011, 19:16 2
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
var s : string; i, len, k : integer;
begin
   readln(s);
   len := length(s);
   k := 0;
   for i := 1 to len do begin
      if s[i] = '(' then k := k + 1;
      if s[i] = ')' then k := k - 1;
      if k < 0 then break
   end;
   writeln(k = 0);
end.
1
13104 / 5885 / 1706
Регистрация: 19.09.2009
Сообщений: 8,808
27.09.2011, 20:53 3
Blood-Angel, это проверка баланса скобок. Если требуется проверить правильность - здесь надо проверять согласованность.
---
Проверка правильности с применением стека.
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
program Project1;
 
const
  //Глубина стека. Т. е. максимальное количество элементов,
  //которое может поместиться в стек.
  N = 100;
  //Множество открывающих скобок.
  D1 = ['(', '[', '{'];
  //Множество закрывающих скобок.
  D2 = [')', ']', '}'];
 
type
  //Тип, описывающий стек.
  TStack = record
    //Указатель вершины стека. Это индекс последнего добавленного элемента.
    Pnt : Integer;
    //Контейнер данных стека.
    Data : array[1..N] of Char;
  end;
 
//Добавить в стек элемент.
function StackPush(var aStack : TStack; const aCh : Char) : Boolean;
begin
  StackPush := False;
  with aStack do begin
    if Pnt < High(Data) then begin
      //Индекс добавляемого элемента.
      Inc(Pnt);
      //Добавляем элемент в массив (т. е. в стек).
      Data[Pnt] := aCh;
      StackPush := True;
    end;
  end;
end;
 
//Взять из стека элемент.
function StackPop(var aStack : TStack; var aCh : Char) : Boolean;
begin
  StackPop := False;
  with aStack do begin
    if Pnt >= Low(Data) then begin
      aCh := Data[Pnt];
      Dec(Pnt);
      StackPop := True;
    end;
  end;
end;
 
//Для закрывающей скобки возвращает соответствующую открывающую скобку.
function GetOpen(const aCh : Char) : Char;
begin
  GetOpen := #0;
  case aCh of
    ')' : GetOpen := '(';
    ']' : GetOpen := '[';
    '}' : GetOpen := '{';
  else
    //Ошибка.
    Writeln('function GetOpen. Ошибка! Незарегистрированное значение.');
  end;
end;
 
//Исследование строки на предмет согласованности скобок.
function ParsePh(const aStr : String) : Integer;
var
  Stack : TStack;
  i, Res : Integer;
  Ch : Char;
begin
  //Инициализируем стек.
  Stack.Pnt := 0;
 
  //0 - успешно.
  Res := 0;
  for i := 1 to Length(aStr) do begin
    if aStr[i] in D1 then begin
      //Нашли открывающую скобку - добавляем её в стек.
      if not StackPush(Stack, aStr[i]) then begin
        //-2 - переполнение стека.
        Res := -2;
        Break;
      end;
    end else if aStr[i] in D2 then begin;
      //Нашли закрывающу скобку - берём элемент из вершины стека.
      if StackPop(Stack, Ch) then begin
        //Стек не пуст.
        if Ch <> GetOpen(aStr[i]) then begin
          //Взятая из вершины стека скобка не соответствует текущей закрывающей скобке.
          //Согласованность нарушена.
          //(Res > 0) - нарушение целостности, Res равен индексу символа (скобки) на котором
          //произошло нарушение согласованности скобок.
          Res := i;
          Break;
        end;
      end else begin
        //Стек пуст. Значит нет соответствия для текущей закрывающей скобки.
        //Согласованность нарушена.
        //(Res > 0) - нарушение целостности, Res равен индексу символа (скобки) на котором
        //произошло нарушение согласованности скобок.
        Res := i;
        Break;
      end;
    end;
  end;
 
  if Res = 0 then begin
    //Если стек пуст - скобки согласованы. Иначе - не согласованы.
    //-1 - не хватает закрывающих скобок.
    if StackPop(Stack, Ch) then Res := -1;
  end;
 
  ParsePh := Res;
end;
 
var
  S : String;
  Res : Integer;
begin
  repeat
    Writeln('Введите строку:');
    Readln(S);
 
    Res := ParsePh(S);
    case Res of
      -2 : Writeln('Ошибка! Переполнение стека. Res = ', Res);
      -1 : Writeln('Не хватает закрывающих скобок. Res = ', Res);
      0  : Writeln('Скобки согласованы. Res = ', Res);
      else
        Writeln('Скобки не согласованы. Позиция первой ошибочной скобки: ', Res, '.');
    end;
 
    Writeln('Повторить - Enter, выход - любой символ + Enter.');
    Readln(S);
  until S <> '';
end.
Проверка правильности без применения стека.
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
program Project1;
 
const
  D  = ['(', ')', '[', ']', '{', '}'];
var
  S, S2 : String;
  i, Len, P1, P2, P3 : Integer;
begin
  repeat
    Writeln('Введите строку:');
    Readln(S);
 
    //Формируем строку, которая содержит только скобки из
    //исходной строки в том же порядке, в каком они расположены
    //в исходной строке.
    Len := Length(S);
    S2 := '';
    for i := 1 to Len do
      if S[i] in D then S2 := S2 + S[i]
    ;
 
    //Удаляем из строки все правильные пары.
    repeat
      P1 := Pos('()', S2);
      if P1 > 0 then Delete(S2, P1, 2);
      P2 := Pos('[]', S2);
      if P2 > 0 then Delete(S2, P2, 2);
      P3 := Pos('{}', S2);
      if P3 > 0 then Delete(S2, P3, 2);
    until (P1 + P2 + P3) = 0;
 
    //Если строка оказалась не пуста, значит остались неправильно расставленные
    //скобки.
    case S2 = '' of
      True : Writeln('Скобки согласованы.');
      else Writeln('Скобки не согласованы.');
    end;
 
    Writeln('Повторить - Enter, выход - любой символ + Enter.');
    Readln(S);
  until S <> '';
end.
0
Злой няш
2136 / 1505 / 565
Регистрация: 05.04.2010
Сообщений: 2,881
27.09.2011, 21:11 4
Цитата Сообщение от Mawrat Посмотреть сообщение
Blood-Angel, это проверка баланса скобок. Если требуется проверить правильность - здесь надо проверять согласованность.
А что вы понимаете под словом "согласованность"? В моем случае, если ввести к примеру ")(" или ")()(", то программа выдаст "FALSE". Да и автор вроде просил только для круглых скобок. Мой алгоритм - база для написания конечного автомата проверки правильности скобок. С тем же успехом, благодаря конечному автомату, я могу написать проверку и для скобок "(", "{", "[", без строки, без массива, без стека, без функций над строкой типа Pos, со сколько угодно длинной входной строкой, где сложность алгоритма O(n) = n. Если хотите, могу написать реализацию.
1
13104 / 5885 / 1706
Регистрация: 19.09.2009
Сообщений: 8,808
27.09.2011, 21:43 5
Цитата Сообщение от Blood-Angel Посмотреть сообщение
В моем случае, если ввести к примеру ")(" или ")()(", то программа выдаст "FALSE". Да и автор вроде просил только для круглых скобок.
Да, точно, всё правильно работает.
Цитата Сообщение от Blood-Angel Посмотреть сообщение
С тем же успехом, благодаря конечному автомату, я могу написать проверку и для скобок "(", "{", "[", без строки, без массива, без стека, без функций над строкой типа Pos, со сколько угодно длинной входной строкой, где сложность алгоритма O(n) = n. Если хотите, могу написать реализацию.
Реализацию на конечном автомате было бы интересно посмотреть... Если не особо затруднит, можешь написать? Если решение трудозатратное - то хотябы в укрупнённом виде (вроде псевдокода с пропуском деталей).
0
Злой няш
2136 / 1505 / 565
Регистрация: 05.04.2010
Сообщений: 2,881
28.09.2011, 09:23 6
Mawrat, мдя, печально, я переоценил свои силы. Регулярные выражения испортили меня. Пытался найти алгоритм паренька, который это сделал на олимпиаде по программированию, но так и не получилось. Суть же была в том, что помимо состояний, отслеживающих открытые и закрытые скобки (по типу того, что как сделано выше для одной скобки), были еще случаи неверной вложенности (к примерку "({)}" - очередность), которые он отслеживал аккумулированием целочисленных переменных для разных комбинаций вложенности (в общей сложности было всего пару десятков целочисленных типов и довольно объемный алгоритм). Программа довольно сложная и, увы, у меня не получилось ее воспроизвести по памяти за ночь.
1
13104 / 5885 / 1706
Регистрация: 19.09.2009
Сообщений: 8,808
28.09.2011, 11:10 7
Blood-Angel, спасибо.
Цитата Сообщение от Blood-Angel Посмотреть сообщение
Программа довольно сложная и, увы, у меня не получилось ее воспроизвести по памяти за ночь.
Эх, ну вот - всю ночь на это убил. У меня почему-то сразу возникло подозрение, что возможно, решение потребует достаточных усилий и затрат времени. Поэтому я и дописал в конце фразу:
Цитата Сообщение от Mawrat Посмотреть сообщение
Если решение трудозатратное - то хотябы в укрупнённом виде (вроде псевдокода с пропуском деталей).
Чтобы не очень уж над этой задачей крапеть.
---
В общем стек это и есть, по сути, конечный автомат с памятью. И решение на стеке считается классическим подходом к решению такой задачи. - По крайней мере, для случая разных видов скобок.
Для одного вида скобок твоё решение, Blood-Angel лучше всего подходит - код оптимальный получился.
---
Blood-Angel, спасибо, ещё раз.
0
28.09.2011, 11:10
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.09.2011, 11:10
Помогаю со студенческими работами здесь

Проверить, правильно ли расставлены скобки в тексте
Скобочная последовательность Проверить, правильно ли расставлены скобки в тексте. Входные...

Проверить, правильно ли в тексте расставлены круглые скобки
Проверить, правильно ли в тексте расставлены круглые скобки (т.е. находится ли правее...

Проверить, правильно ли в заданном тексте расставлены круглые скобки
Проверить, правильно ли в заданном тексте расставлены круглые скобки.(stack)стек. консоль апликейшен

В заданом тексте поменять одну букву на другую
Создайте программу,которая в заданом тексте меняет одну букву на другую.Какие именно буквы...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru