Всеукраїнська олімпіада
Limits: 2 sec., 256 MiB
Діти! Вітаємо вас із тим, що ви успішно потрапили в команду Львівської області, що поїде на Всеукраїнську олімпіаду з інформатики 2016 року. Зичимо вам великого успіху на змаганні і людських умов проживання в Хмельницькому.
На шляху до перемоги на Всеукраїнській олімпіаді у вас стоять не лише два тури змагань, а й багато інших, на перший погляд, нікчемних завдань. Перед олімпіадою вам треба щоранку прокидатися, чистити зуби, снідати, охайно вдягатися, причісуватися, ... Всього і не перелічити!
Одним із таких завдань є наступне: маючи деякий математичний вираз із дужками, вам необхідно вказати порядок, у якому будуть обчислюватися значення виразу в дужках.
Допоможіть же собі, напишіть для цього програму.
Input
Єдиний рядок містить математичний вираз \(s\), що складається з цифр (0
,
1
, ..., 9
), математичних операцій
(+
, -
, /
, *
) та
дужок ((
, )
). Не гарантується, що математичний
вираз буде коректно побудований, або матиме зміст, проте гарантується,
що дужки в виразі будуть коректно розставлені (для кожної відкриваючої
дужки буде відповідна їй закриваюча, і навпаки).
Output
Перший рядок повинен містити єдине натуральне число \(n\) — кількість пар дужок, що присутні в виразі. Наступні \(n\) рядків повинні містити пари натуральних чисел — позиції відкриваючої та відповідної їй закриваючої дужки (індексація починається з 1) в такому порядку, в якому вони будуть обчислені.
Constraints
\(40\%\) тестів: \(2 \le |s| \le 10^3\),
\(60\%\) тестів: \(2 \le |s| \le 10^5\).
Samples
Input (stdin) | Output (stdout) |
---|---|
4+((7-4)+(4+4))*(7-4) | 4 4 8 10 14 3 15 17 21 |
Notes
Дужки обчислюються зліва направо. Якщо якась пара дужок містить в собі інші дужки, то спочатку повинні бути обчислені всі внутрішні дужки, і тільки тоді обчислюються зовнішні.
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|