Всем привет!
Кто может помочь решить задачку, я долго думал - аут полный

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


Римскими цифрами показан порядок выполнения действий.

Задание таково:
1)выведите на экран "Yes",если скобки в выражении расставлены правильно и "NO" если нет.

2)Если правильно расставлены скобки вывести на экран в порядке их выполнения в отдельном ряду через пропуск для каждой пары скобок позиции их расположения в заданном выражении.

Пример:

а+(2-с)-[21-8*b +(-2)]+[3]
Результат
YES
17 20
9 21
23 25
3 7


Как я вижу решение:
итак первое - правильно ли расставлены скобки, я предлагаю каждую скобку обозначить цифрой (или буквой и т.д.)
например круглые - 1 а квадратные - 2 и получится
1221 2112 и т.д. однако если у нас 1212 то есть ([)] - выдает ошибку. ну или 123 321 - и только так, хотя все равно реализация что-то смутно представляется

По поводу второго - позицию строки найти легко:
for i:=0 to length(stroki) do
if s[i]='[' then $a[i]:=i;

в массиве a[i] будут позиции скобок, вот только как их разбить на главные а подчиненные?? (

Скобки определяются через константы: вот код:

Код

[code=delphi] program Project18; {$APPTYPE CONSOLE} uses   SysUtils;      const       t1='['; t2=']';   var   r:integer; // длинна строки     stroc:string;  // строка      st:boolean; // правильная или нет begin   { TODO -oUser -cConsole Main : Insert code here }      // а потом в программе       r:= length(stroc);      if (pos(t1,stroc)=r) and (pos(t2,stroc)=r) then st:=true; // строка правильная      else st:=false // строка неправильная   end.

P.S Хотя незнаю верно или нет код непроверял.

Это сообщение отредактировал(а) Denic - 20.11.2005, 09:00

Цитата(Denic @ 20.11.2005, 07:59)

Код if (pos(t1,stroc)=r) and (pos(t2,stroc)=r) then st:=true; // строка правильная      else st:=false // строка неправильная

Ты вообще подумал, что ты написал? Как последний символ строки может содержать одновременно и '[' и ']'? А по твоему коду только в этом случае строка является правильной...

Цитата

Вот пример: Римскими цифрами показан порядок выполнения действий.

Я забыл сам пример Вот смотрите:

Задача решается элементарно: строим дерево скобочных пар, а затем обходим его. В каждом узле хранятся позиции открывающей и закрывающей скобок и два списка потомков: для круглых и квадратных скобок. При обходе дерева первым выводится второй список. Код я накидал, но он на C++, и переводить его мне было в ломы, уж извините Алгоритм, думаю, понятен.

Код

#include <iostream> #include <string> #include <stack> #include <vector> #include <algorithm> using namespace std; struct bracket_pair {     int begin, end;     vector<bracket_pair> round, square;     bracket_pair *parent;     bracket_pair(int begin_, int end_, bracket_pair *parent_) :         begin(begin_), end(end_), parent(parent_) { } }; void print_tree(const bracket_pair &root) {     for_each(root.square.begin(), root.square.end(), print_tree);     for_each(root.round.begin(), root.round.end(), print_tree);     if (root.begin != -1)         cout << root.begin << ' ' << root.end << endl; } int main() {     string s;     stack<char> stk;     bracket_pair root(-1, -1, NULL), *curr = &root;     getline(cin, s);     for (string::iterator i = s.begin(); i != s.end(); ++i) {         int pos = i - s.begin();         switch (*i) {             case '(':                 curr->round.push_back(bracket_pair(pos, -1, curr));                 curr = &curr->round.back();                 stk.push(*i);                 break;             case '[':                 curr->square.push_back(bracket_pair(pos, -1, curr));                 curr = &curr->square.back();                 stk.push(*i);                 break;             case ')':                 if (stk.top() == '(') {                     curr = curr->parent;                     curr->round.back().end = pos;                     stk.pop();                 } else {                     cout << "NO";                     return 0;                 }                 break;             case ']':                 if (stk.top() == '[') {                     curr = curr->parent;                     curr->square.back().end = pos;                     stk.pop();                 } else {                     cout << "NO";                     return 0;                 }                 break;         }     }     cout << "YES\n";     print_tree(root); }

Это сообщение отредактировал(а) Void - 20.11.2005, 15:59

Void
Это олимпиадная задачка, в олимпиадах нет ограничений в языках, к сожалению когда мы пришли нам четко сказали - что будем писать или на Паскале или на Бейсике.
С++ не пройдет , хотя алгоритм сейчас попробую разобрать.......

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

Цитата

С++ не пройдет  , хотя алгоритм сейчас попробую разобрать...

А Void, он маньяк по С++... Я три недели назад, после каждого его ответа, почти сразу решал, свои трудности...
Конечно, я могу, показать пример, реализации, но я думаю алгоритм с использованием стека и так понятен. Или тот который воид написал...

Zero
На олимпиаде я решал подобным путем:
я напишу не поностью т.к. не помню точно как я писал тогда.

Код

var  s:string; beg,en,i:integer; begin s:='a+(2-c)-[21-8*b+(-2)]+3'; for i:=0 to length(s) do if s[i]='[' then  begin   beg:=i;   for j:=i to length(s) do    if s[j]=']' then en:=j;    break;  end;

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

Модератор: Название темы должно отражать ее суть!