Правильное арифметическое выражение со скобками

@Sultik_Zaka · Регистрация: 21.09.2016

Author24 — интернет-сервис помощи студентам

Всем привет, зачастил я тут

В общем стояла такая задача:
Input
N - кол-во скобок (1 <= N <= 100000)
N скобок (сами скобки)
Output
cout << "Yes";, если с данными скобками можно получить правильное арифм. выражение или cout << "No";, если нет.

Пример:
Input:
6
([())]
Output:
No

Input:
24
{[()([]{})[]]({}{{}})}[]
Output:
No

Я набросал такое:

C++

#include <iostream>
#include <string>
#include <stack>
#include <cstring>
using namespace std;
 
int main()
{
    int n, j, s;
    bool x = true;
    stack<char> sta;
    char arr[100001];
    cin >> n;
    if (n >= 1 && n <= 100000)
    {
        for (j = 0; j < n; j++)
        {
            cin >> arr[j];
        }
        s = strlen(arr);
        for(int i = 0; i < s; ++i)
        {
            if ((arr[i] =='(') || (arr[i] =='{') || (arr[i] =='['))
            {
                sta.push(arr[i]);
            }
            else
            {
                if (sta.size() == 0)
                {
                    x = false;
                }
                char c = sta.top();
                sta.pop();
                if ((c == '(' && arr[i] != ')') || (c == '{' && arr[i] != '}') || (c == '[' && arr[i] != ']'))
                {
                    x = false;
                }
            }
        }
        if(sta.size() != 0)
        {
            x = false;
        }
        if(x == true)
        {
            cout << "Yes";
        }
        else
        {
            cout << "No";
        }
    }
    return 0;
}

Но, так как в задании Time Limit 93/4000/4000/4000 ms, то он вечно на первом же тесте ругается на Time Limit.
Не могли бы вы помочь оптимизировать?

Добавлено через 31 минуту

Сообщение от Sultik_Zaka

24
{[()([]{})[]]({}{{}})}[]
Output:
No

Извиняюсь, опечатка

Input:
24
{[()([]{})[]]({}{{}})}[]
Output:
Yes

@nonedark2008 · 29.10.2016, 14:28

Sultik_Zaka, предположу, что твоя программа в основном занимается выделением и освобождением данных в std::stack. Попробуй заменить std::stack на std::vector.

@Sultik_Zaka · 29.10.2016, 14:48 **[ТС]**

К сожалению, пока вектора не проходили
Если поможете с заменой - буду неизменно благодарен

@nonedark2008 · 29.10.2016, 14:53

Не уверен на счет работоспособности:

C++

#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
int main() {
    size_t n;
    cin >> n;
    cin.ignore(1, '\n');
    string str;
    cin >> str;
    vector<char> s; s.reserve(n);
 
    for (char c : str) {
        char id;
        bool isOp = c == '[' || c == '{' || c == '(';
        if (c == '[' || c == ']') id = 0;
        else if (c == '(' || c == ')') id = 1;
        else if (c == '{' || c == '}') id = 2;
 
        if (isOp)
            s.push_back(id);
        else {
            if (s.size() == 0 || s.back() != id) {
                cout << "No" << endl;
                return 0;
            }
            s.pop_back();
        }
    }
 
    if (s.size())
        cout << "No" << endl;
    else
        cout << "Yes" << endl;
 
    return 0;
}

@Sultik_Zaka · 29.10.2016, 14:55 **[ТС]**

Сообщение от nonedark2008

for (char c : str) {

Ошиблись циклом?

range-based 'for' loops are not allowed in C++98 mode

@nonedark2008 · 29.10.2016, 15:01

Сообщение от Sultik_Zaka

Ошиблись циклом?

Я не ошибался.
Это твой стандарт просто слишком стар для этого

Замени на:

C++

1
2
3

char c;
for (string::iterator it = str.begin(); it != str.end(); ++it) {
    c = *it;

@Sultik_Zaka · 29.10.2016, 15:04 **[ТС]**

Спасибо, вот только что поправил

Но все равно, Time Limit :/

@nonedark2008 · 29.10.2016, 15:32

А вот так?

C++

#include <iostream>
 
using namespace std;
 
int main() {
    size_t n;
    cin >> n;
    //n = 100000;
    cin.ignore(1, '\n');
    char str[100000 + 1];
    char *str_cur = str;
    char *str_end = str + n;
 
    cin.getline(str, n + 1);
    size_t st_last = ~size_t(0);
    char s[100000];
 
    char c;
    for (char *str_cur = str; str_cur != str_end; ++str_cur) {
        c = *str_cur;
 
        char id;
        bool isOp = c == '[' || c == '{' || c == '(';
        if (c == '[' || c == ']') id = 0;
        else if (c == '(' || c == ')') id = 1;
        else if (c == '{' || c == '}') id = 2;
 
        if (isOp)
            s[++st_last] = id;
        else {
            if (st_last == ~size_t(0) || s[st_last] != id) {
                cout << "No" << endl;
                return 0;
            }
            st_last -= 1;
        }
    }
 
    if (st_last != ~size_t(0))
        cout << "No" << endl;
    else
        cout << "Yes" << endl;
 
    return 0;
}

@Sultik_Zaka · 29.10.2016, 15:43 **[ТС]**

Аналогично, Time Limit

@nonedark2008 · 29.10.2016, 15:54

Еще можно выкинуть строчки 24-26 и написать просто:

C++

1	char id = (c >= '[') + (c >= '{');

Тогда кол-во блокировок будет меньше.

Добавлено через 3 минуты
А вообще странно,
может ты неправильно указал входные данные, и программа просто зависает на ожидании ввода?

@Sultik_Zaka · 29.10.2016, 17:31 **[ТС]**

Да нет, все правильно

Просто Time Limit 97 ms - это пздц)

@nonedark2008 · 29.10.2016, 17:49

Sultik_Zaka, ну теперь даже не знаю.
Попробуй добавить еще ios::sync_with_stdio(false); в начало программы.

C++

#include <iostream>
 
using namespace std;
 
size_t n;
char str[100000 + 1];
 
size_t st_last = ~size_t(0);
char s[100000];
 
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    cin.ignore(1, '\n');
    cin.getline(str, n + 1);
 
    const char *str_cur = str;
    const char *str_end = str + n;
 
    char c;
    for (const char *str_cur = str; str_cur != str_end; ++str_cur) {
        c = *str_cur;
 
        char id = (c >= '[') + (c >= '{');
        bool isOp = c == '[' || c == '{' || c == '(';
 
        if (isOp)
            s[++st_last] = id;
        else {
            if (st_last == ~size_t(0) || s[st_last] != id) {
                cout << "No" << endl;
                return 0;
            }
            st_last -= 1;
        }
    }
 
    if (st_last != ~size_t(0))
        cout << "No" << endl;
    else
        cout << "Yes" << endl;
 
    return 0;
}

Оптимизировать там уже особо нечего. Пожалуйся тому, кто прописал такое ограничение =)

Добавлено через 3 минуты
Хотя, еще можно стек пихнуть прямо в строку:

Кликните здесь для просмотра всего текста

C++

#include <iostream>
 
using namespace std;
 
size_t n;
char str[100000 + 1];
size_t st_last = ~size_t(0);
 
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    cin.ignore(1, '\n');
    cin.getline(str, n + 1);
 
    const char *str_cur = str;
    const char *str_end = str + n;
 
    char c;
    for (const char *str_cur = str; str_cur != str_end; ++str_cur) {
        c = *str_cur;
 
        char id = (c >= '[') + (c >= '{');
        bool isOp = c == '[' || c == '{' || c == '(';
 
        if (isOp)
            str[++st_last] = id;
        else {
            if (st_last == ~size_t(0) || str[st_last] != id) {
                cout << "No" << endl;
                return 0;
            }
            st_last -= 1;
        }
    }
 
    if (st_last != ~size_t(0))
        cout << "No" << endl;
    else
        cout << "Yes" << endl;
 
    return 0;
}

@Sultik_Zaka · 29.10.2016, 17:53 **[ТС]**

Вот и я думаю, что багнулся контестер...

C++

#include <iostream>
using namespace std;
int main()
{
    int a, b, s;
    cin >> a >> b;
    s = a+b;
    cout << s << endl;
    return 0;
}

Даже на это TimeLimit выдаёт...

@nonedark2008 · 29.10.2016, 17:57

Sultik_Zaka,

Предлагаю забить, пока не починят.
Кстати, платформа с задачей какая-то общеизвестная, или локальная школьная/институтская?

@Sultik_Zaka · 29.10.2016, 18:02 **[ТС]**

Университетская (IITU contester)
Нашел аналогичное задание в другом разделе контестера, ток там Time Limit в два раза меньше и у всех стоит "+" (Accepted) o_O
Значит все-таки решение есть

@nonedark2008 · 29.10.2016, 18:11

Сообщение от Sultik_Zaka

Значит все-таки решение есть

Ну, все может сломаться в самый неподходящий момент...

Sultik_Zaka, попробуй поиграться с вводом.
Если там допускается считывание из файла, то попробуй с ним.

@Sultik_Zaka · 29.10.2016, 18:14 **[ТС]**

С вводом игрался как мог
Считывание с файла (fstream) делал...

@nonedark2008 · 29.10.2016, 18:26

Sultik_Zaka, тогда я больше ничем помочь не могу.
Советую обратиться в поддержку контестера, либо напрямую к преподавателю.

@Sultik_Zaka · 29.10.2016, 18:35 **[ТС]**

Благодарю!)
Так и сделаю

@Sultik_Zaka 0 / 0 / 0 Регистрация: 21.09.2016 Сообщений: 59
	29.10.2016, 18:35 [ТС]	19
	Благодарю!) Так и сделаю 0

@nonedark2008 1394 / 1023 / 325 Регистрация: 28.07.2012 Сообщений: 2,813
	29.10.2016, 14:28	2
	Sultik_Zaka, предположу, что твоя программа в основном занимается выделением и освобождением данных в std::stack. Попробуй заменить std::stack на std::vector. 0

@Sultik_Zaka 0 / 0 / 0 Регистрация: 21.09.2016 Сообщений: 59
	29.10.2016, 14:48 [ТС]	3
	К сожалению, пока вектора не проходили Если поможете с заменой - буду неизменно благодарен 0

@Sultik_Zaka 0 / 0 / 0 Регистрация: 21.09.2016 Сообщений: 59
	29.10.2016, 14:55 [ТС]	5
	Сообщение от nonedark2008 for (char c : str) { Ошиблись циклом? range-based 'for' loops are not allowed in C++98 mode 0

@Sultik_Zaka 0 / 0 / 0 Регистрация: 21.09.2016 Сообщений: 59
	29.10.2016, 15:04 [ТС]	7
	Спасибо, вот только что поправил Но все равно, Time Limit :/ 0

@Sultik_Zaka 0 / 0 / 0 Регистрация: 21.09.2016 Сообщений: 59
	29.10.2016, 15:43 [ТС]	9
	Аналогично, Time Limit 0

@Sultik_Zaka 0 / 0 / 0 Регистрация: 21.09.2016 Сообщений: 59
	29.10.2016, 17:31 [ТС]	11
	Да нет, все правильно Просто Time Limit 97 ms - это пздц) 0

@nonedark2008 1394 / 1023 / 325 Регистрация: 28.07.2012 Сообщений: 2,813
	29.10.2016, 17:57	14
	Sultik_Zaka, Предлагаю забить, пока не починят. Кстати, платформа с задачей какая-то общеизвестная, или локальная школьная/институтская? 0

@Sultik_Zaka 0 / 0 / 0 Регистрация: 21.09.2016 Сообщений: 59
	29.10.2016, 18:02 [ТС]	15
	Университетская (IITU contester) Нашел аналогичное задание в другом разделе контестера, ток там Time Limit в два раза меньше и у всех стоит "+" (Accepted) o_O Значит все-таки решение есть 0

@nonedark2008 1394 / 1023 / 325 Регистрация: 28.07.2012 Сообщений: 2,813
	29.10.2016, 18:11	16
	Сообщение от Sultik_Zaka Значит все-таки решение есть Ну, все может сломаться в самый неподходящий момент... Sultik_Zaka, попробуй поиграться с вводом. Если там допускается считывание из файла, то попробуй с ним. 0

@Sultik_Zaka 0 / 0 / 0 Регистрация: 21.09.2016 Сообщений: 59
	29.10.2016, 18:14 [ТС]	17
	С вводом игрался как мог Считывание с файла (fstream) делал... 0

@nonedark2008 1394 / 1023 / 325 Регистрация: 28.07.2012 Сообщений: 2,813
	29.10.2016, 18:26	18
	Sultik_Zaka, тогда я больше ничем помочь не могу. Советую обратиться в поддержку контестера, либо напрямую к преподавателю. 0