Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Sultik_Zaka
0 / 0 / 0
Регистрация: 21.09.2016
Сообщений: 58
29.10.2016, 14:20     Правильное арифметическое выражение со скобками #1
Всем привет, зачастил я тут
В общем стояла такая задача:
Input
N - кол-во скобок (1 <= N <= 100000)
N скобок (сами скобки)
Output
cout << "Yes";, если с данными скобками можно получить правильное арифм. выражение или cout << "No";, если нет.

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

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

Я набросал такое:
C++
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
#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
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,343
29.10.2016, 14:28     Правильное арифметическое выражение со скобками #2
Sultik_Zaka, предположу, что твоя программа в основном занимается выделением и освобождением данных в std::stack. Попробуй заменить std::stack на std::vector.
Sultik_Zaka
0 / 0 / 0
Регистрация: 21.09.2016
Сообщений: 58
29.10.2016, 14:48  [ТС]     Правильное арифметическое выражение со скобками #3
К сожалению, пока вектора не проходили
Если поможете с заменой - буду неизменно благодарен
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,343
29.10.2016, 14:53     Правильное арифметическое выражение со скобками #4
Не уверен на счет работоспособности:
C++
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
#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
0 / 0 / 0
Регистрация: 21.09.2016
Сообщений: 58
29.10.2016, 14:55  [ТС]     Правильное арифметическое выражение со скобками #5
Цитата Сообщение от nonedark2008 Посмотреть сообщение
for (char c : str) {
Ошиблись циклом?
range-based 'for' loops are not allowed in C++98 mode
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,343
29.10.2016, 15:01     Правильное арифметическое выражение со скобками #6
Цитата Сообщение от Sultik_Zaka Посмотреть сообщение
Ошиблись циклом?
Я не ошибался.
Это твой стандарт просто слишком стар для этого

Замени на:
C++
1
2
3
char c;
for (string::iterator it = str.begin(); it != str.end(); ++it) {
    c = *it;
Sultik_Zaka
0 / 0 / 0
Регистрация: 21.09.2016
Сообщений: 58
29.10.2016, 15:04  [ТС]     Правильное арифметическое выражение со скобками #7
Спасибо, вот только что поправил
Но все равно, Time Limit :/
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,343
29.10.2016, 15:32     Правильное арифметическое выражение со скобками #8
А вот так?
C++
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
#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
0 / 0 / 0
Регистрация: 21.09.2016
Сообщений: 58
29.10.2016, 15:43  [ТС]     Правильное арифметическое выражение со скобками #9
Аналогично, Time Limit
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,343
29.10.2016, 15:54     Правильное арифметическое выражение со скобками #10
Еще можно выкинуть строчки 24-26 и написать просто:
C++
1
char id = (c >= '[') + (c >= '{');
Тогда кол-во блокировок будет меньше.

Добавлено через 3 минуты
А вообще странно,
может ты неправильно указал входные данные, и программа просто зависает на ожидании ввода?
Sultik_Zaka
0 / 0 / 0
Регистрация: 21.09.2016
Сообщений: 58
29.10.2016, 17:31  [ТС]     Правильное арифметическое выражение со скобками #11
Да нет, все правильно
Просто Time Limit 97 ms - это пздц)
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,343
29.10.2016, 17:49     Правильное арифметическое выражение со скобками #12
Sultik_Zaka, ну теперь даже не знаю.
Попробуй добавить еще ios::sync_with_stdio(false); в начало программы.
C++
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
#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++
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
#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
0 / 0 / 0
Регистрация: 21.09.2016
Сообщений: 58
29.10.2016, 17:53  [ТС]     Правильное арифметическое выражение со скобками #13
Вот и я думаю, что багнулся контестер...
C++
1
2
3
4
5
6
7
8
9
10
#include <iostream>
using namespace std;
int main()
{
    int a, b, s;
    cin >> a >> b;
    s = a+b;
    cout << s << endl;
    return 0;
}
Даже на это TimeLimit выдаёт...
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,343
29.10.2016, 17:57     Правильное арифметическое выражение со скобками #14
Sultik_Zaka,
Предлагаю забить, пока не починят.
Кстати, платформа с задачей какая-то общеизвестная, или локальная школьная/институтская?
Sultik_Zaka
0 / 0 / 0
Регистрация: 21.09.2016
Сообщений: 58
29.10.2016, 18:02  [ТС]     Правильное арифметическое выражение со скобками #15
Университетская (IITU contester)
Нашел аналогичное задание в другом разделе контестера, ток там Time Limit в два раза меньше и у всех стоит "+" (Accepted) o_O
Значит все-таки решение есть
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,343
29.10.2016, 18:11     Правильное арифметическое выражение со скобками #16
Цитата Сообщение от Sultik_Zaka Посмотреть сообщение
Значит все-таки решение есть
Ну, все может сломаться в самый неподходящий момент...

Sultik_Zaka, попробуй поиграться с вводом.
Если там допускается считывание из файла, то попробуй с ним.
Sultik_Zaka
0 / 0 / 0
Регистрация: 21.09.2016
Сообщений: 58
29.10.2016, 18:14  [ТС]     Правильное арифметическое выражение со скобками #17
С вводом игрался как мог
Считывание с файла (fstream) делал...
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,343
29.10.2016, 18:26     Правильное арифметическое выражение со скобками #18
Sultik_Zaka, тогда я больше ничем помочь не могу.
Советую обратиться в поддержку контестера, либо напрямую к преподавателю.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.10.2016, 18:35     Правильное арифметическое выражение со скобками
Еще ссылки по теме:

C++ Регулярное выражение, выдернуть весь текст между фигурными скобками
Правильное скобочное выражение C++
C++ Дано математическое выражение с числами и скобками

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

Или воспользуйтесь поиском по форуму:
Sultik_Zaka
0 / 0 / 0
Регистрация: 21.09.2016
Сообщений: 58
29.10.2016, 18:35  [ТС]     Правильное арифметическое выражение со скобками #19
Благодарю!)
Так и сделаю
Yandex
Объявления
29.10.2016, 18:35     Правильное арифметическое выражение со скобками
Ответ Создать тему
Опции темы

Текущее время: 12:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru