Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Tolyas
0 / 0 / 0
Регистрация: 18.10.2011
Сообщений: 16
#1

оптимизация кода - C++

20.04.2013, 22:29. Просмотров 575. Ответов 10
Метки нет (Все метки)

Задача: определить, является ли последовательность скобок действительной. Длинна строки не превышает 100000.
Например:
№ Input Output
1 ()(()) VALID
2 )( INVALID
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
#include <iostream>
#include <string>
 
using namespace std;
 
int main()
{
    int sum=0;
    char *c = new char[100001];
    cin>>c;
    for(int i = 0 ;i<strlen(c);i++)
    {
        if (c[i]=='(')
            sum++;
        if (c[i]==')')
            sum--;
        if (sum<0 || sum>strlen(c)-i-1)
            break;
    }
    if(sum == 0)
        cout<<"VALID";
    else
        cout<<"INVALID";
    return 0;
}
Код не проходит по времени. Заранее спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.04.2013, 22:29
Здравствуйте! Я подобрал для вас темы с ответами на вопрос оптимизация кода (C++):

Оптимизация кода - C++
Есть вот такой кусочек кода integer h (integer k,n) {return k–n*3 ;} . . . . . z = h (k1, n2) ; Подскажите - как его можно...

оптимизация кода - C++
Добрый вечер всем. У меня такая проблема: написал прогу, необходимо продемонстрировать ее работу. Т.е. есть L2 список, дек и массив деков,...

Оптимизация кода - C++
Пожалуйста форумчане как можно сократить этот код Особенно от 27 до 90 строки #include &lt;iostream&gt; using namespace std; int main() ...

Оптимизация кода - C++
Как сравнить 2 строки. Вот как их задавал в ходе программы string h,b; ... char * text = NULL; if ( OpenClipboard(0) ) { ...

Оптимизация кода - C++
В С++ я совсем недавно, вот задали задачку: Перемножить 2 матрицы MxМ, элементами которых являются матрицы NxN. Код я вроде написал,...

Оптимизация кода - C++
main: #include &lt;iostream&gt; #include &lt;conio.h&gt; #include &quot;keyBuffer.h&quot; #include &quot;pause.h&quot; #include &lt;windows.h&gt; const char...

10
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
20.04.2013, 22:33 #2
Цитата Сообщение от Tolyas Посмотреть сообщение
i<strlen(c)
заменить на
C++
1
c[i]
А то у вас сложность квадратичная :)

Добавлено через 1 минуту
Цитата Сообщение от Tolyas Посмотреть сообщение
sum>strlen(c)-i-1
и вот это вот убрать лучше
1
Tolyas
0 / 0 / 0
Регистрация: 18.10.2011
Сообщений: 16
20.04.2013, 22:40  [ТС] #3
Спасибо, все прошло, буду знать, что так можно писать в условии. Спасибо.
0
UnsKneD
алкокодер
155 / 151 / 12
Регистрация: 27.12.2012
Сообщений: 550
20.04.2013, 23:09 #4
Можно так
C++
1
2
3
4
5
6
7
8
9
10
    char str[] = "((123))(";
    int count = 0;
    for(int i = 0; str[i]!='\0'; i++){
        if( str[i] == '(' || str[i] == ')' ){ ++count; };
    }
    if( count%2 == 0 ) { 
        printf("1\n"); 
    } else {
        printf("0\n"); 
    };
Добавлено через 10 минут
Хотя, не всегда корректно.
0
Tulosba
:)
Эксперт С++
4397 / 3233 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
21.04.2013, 00:05 #5
Цитата Сообщение от UnsKneD Посмотреть сообщение
Добавлено через 10 минут
Хотя, не всегда корректно.
Конечно, что тут может быть корректно если просто считать кол-во разных скобок одним счетчиком. "))"
0
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 832
21.04.2013, 00:28 #6
или можно через стек (для трёх видов скобок)
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
#include <iostream>
#include <stack>
#include <string>
 
using namespace std;
 
bool ChkBrackets(const string &Str)
{
    stack<char>Brackets;
 
    for (string::size_type i = 0; i != Str.size(); i++) {
        if ( (Str[i]=='(') || (Str[i]=='{') ||(Str[i]=='[') ) {
            Brackets.push(Str[i]);
        }
        else {
            switch (Str[i]) {
            case ')':
                if (!(Brackets.empty()) && (Brackets.top()=='('))
                    Brackets.pop();
                else return false;
                break;
            case '}':
                if (!(Brackets.empty()) && (Brackets.top()=='{'))
                    Brackets.pop();
                else return false;
                break;
            case ']':
                if (!(Brackets.empty()) && (Brackets.top()=='['))
                    Brackets.pop();
                else return false;
                break;
            }
        }
    }
    return Brackets.empty();
}
 
int main()
{
    string str;
    getline(cin,str);
 
    if (ChkBrackets(str))
        cout<<"OK";
    else
        cout<<"BAD";
    return 0;
}
0
Tolyas
0 / 0 / 0
Регистрация: 18.10.2011
Сообщений: 16
21.04.2013, 02:33  [ТС] #7
Olivеr, Этот код не проходит по времени, но я решил эту задачу немного другим способом:
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
 
using namespace std;
 
int main()
{
  int s1=0,s2=0,s3=0;
  int i1=0,i2=0,i3=0;
  int *j1,*j2,*j3;
  int n;
  cin>>n;
  char *c = new char[n];
  j1 = new int[n+1];
  j2 = new int[n+1];
  j3 = new int[n+1];
  j1[0]=-1;
  j2[0]=-1;
  j3[0]=-1;
  cin>>c;
  for(int i = 0 ;c[i]!='\0';i++)
  {
    if (c[i]=='(')
    {
      s1++;
      j1[++i1]=i;
    }
    if (c[i]==')')
    {
      s1--;
      if(j1[i1]<j2[i2]||j1[i1]<j3[i3])
      {
        s1=-1;
      }
      i1--;
 
    }
    if (c[i]=='[')
    {
      s2++;
      j2[++i2]=i;
    }
    if (c[i]==']')
    {
      s2--;
      if(j2[i2]<j1[i1]||j2[i2]<j3[i3])
      {
        s2=-1;
      }
      i2--;
    }
    if (c[i]=='{')
    {
      s3++;
      j3[++i3]=i;
    }
    if (c[i]=='}')
    {
      s3--;
      if(j3[i3]<j2[i2]||j3[i3]<j1[i1])
      {
        s3=-1;
      }
      i3--;
    }
    if ((s1<0)||(s2<0)||(s3<0))
      break;
  }
  if((s1 == 0)&&(s2 == 0)&&(s3 == 0))
    cout<<"Yes";
  else
    cout<<"No";
  return 0;
}
0
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 832
21.04.2013, 09:28 #8
Tolyas,
()))))
Yes
(())
No
()
Yes
так должно быть?
0
myxasa
14 / 14 / 1
Регистрация: 31.05.2012
Сообщений: 210
Записей в блоге: 2
21.04.2013, 10:07 #9
Olivеr, условия лучше так писать

C++
1
if( !s1 && !s2 && !s3)
на будущее)
0
Tolyas
0 / 0 / 0
Регистрация: 18.10.2011
Сообщений: 16
21.04.2013, 10:53  [ТС] #10
Цитата Сообщение от Olivеr Посмотреть сообщение
Tolyas,
так должно быть?
Нет, так не должно быть. Так и не происходит.
0
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 832
21.04.2013, 11:09 #11
myxasa, это Вы, наверное, хотели сказать Tolyas
0
21.04.2013, 11:09
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.04.2013, 11:09
Привет! Вот еще темы с ответами:

Оптимизация кода (C++) - C++
Добрый вечер. У меня есть две функции. Вопрос:&quot;Как оптимизировать этот код, пользуясь тем, что тела отличаются лишь несколькими строчками?&quot;...

Оптимизация кода - C++
В общем дело такое, мне нужно 2 одинаковые программы(небольшие), только одна программа должна быть неоптимизированная, а другая, точно...

Оптимизация кода - C++
Положение дел таково: написана программа, которая работает и вроде все замечательно, но, вспоминая программирование, которому обучался в...

Оптимизация кода - C++
Программа ищет одинаковые файлы в папке где сама находится(по маске или расширению), по хэшу, и перемещает все копии в отдельную папку. ...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.