Advertisement
Guest User

Untitled

a guest
Sep 25th, 2017
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.44 KB | None | 0 0
  1. #include <iostream>
  2. #include <assert.h>
  3. #include <stdio.h>
  4. #include <string.h>
  5.  
  6. using namespace std;
  7.  
  8. ///стэк целых чисел, реализованный с помощью массива
  9. class CStack {
  10. public:
  11. CStack (int _bufferSize); ///конструктор
  12. ~CStack(); ///деструктор
  13.  
  14. ///добавленние и извлечение элемента из стека
  15. void Push ( char a );
  16. char Pop();
  17.  
  18. ///проверка на пустоту
  19. bool IsEmpty() const { return top == -1;}
  20.  
  21. private:
  22. char* buffer;
  23. int bufferSize;
  24. int top; ///индекс верхнего элемента
  25. };
  26.  
  27. CStack::CStack( int _bufferSize) : bufferSize (_bufferSize ), top ( -1 )
  28. {
  29. buffer = new char[bufferSize]; ///создаём буффер
  30. }
  31.  
  32. CStack::~CStack()
  33. {
  34. delete[] buffer; ///удаляем буффер
  35. }
  36.  
  37. ///добавление элемента
  38. void CStack::Push( char a )
  39. {
  40. assert( top + 1 < bufferSize );
  41. buffer[++top] = a;
  42. }
  43. ///извлечение элемента
  44. char CStack::Pop()
  45. {
  46. assert( top!= -1);
  47. return buffer[top--];
  48. }
  49. char* solve(char *a);
  50. int main()
  51. {
  52. char a[800005];
  53. gets(a);
  54. cout << solve(a);
  55. return 0;
  56. }
  57. char* solve(char *a){
  58. char q;
  59. CStack f(strlen(a));
  60. int razm = 0;
  61. int y = strlen(a);
  62. char *t = new char[800005];
  63. for (int i = 0; i < y; i++)
  64. if (a[i] == '(' || a[i] == '[' || a[i] == '{')
  65. {
  66. f.Push(a[i]);
  67. razm++;
  68. }
  69. else
  70. {
  71. bool pr = 0;
  72. if (razm==0)
  73. {
  74. f.Push(a[i]);
  75. razm++;
  76. pr = 1;
  77. }
  78. else
  79. {
  80. q=f.Pop();
  81. razm--;
  82. if(q == ')' || q == ']' || q == '}')
  83. {
  84. f.Push(q);
  85. f.Push(a[i]);
  86. razm+=2;
  87. pr = 1;
  88. }
  89. else
  90. {
  91. if (a[i]==')' && q=='(')
  92. pr = 1;
  93. if (a[i]==']' && q=='[')
  94. pr = 1;
  95. if (a[i]=='}' && q=='{')
  96. pr = 1;
  97. }
  98. if (pr == 0)
  99. {
  100. return "IMPOSSIBLE";
  101. return 0;
  102. }
  103.  
  104. }
  105. }
  106. if (razm == 0)
  107. {
  108.  
  109. for (int i = 0; i < y; i++)
  110. return a;
  111. }
  112.  
  113. char b[80005];
  114. int b1 = 0;
  115. char w = f.Pop();
  116. razm--;
  117. while (w == '(' || w == '[' || w == '{')
  118. {
  119. if (w == '(')
  120. {b[b1] = ')';b1++;}
  121. if (w == '[')
  122. {b[b1] = ']';b1++;}
  123. if (w == '{')
  124. {b[b1] = '}';b1++;}
  125. if (razm == 0) break;
  126. else w = f.Pop();
  127. razm--;
  128. }
  129. razm++;
  130.  
  131. int t1 = 0;
  132. while (razm > 0){
  133. if (w == ')')
  134. {t[t1] = '(';t1++;}
  135. if (w == ']')
  136. {t[t1] = '[';t1++;}
  137. if (w == '}')
  138. {t[t1] = '{';t1++;}
  139. razm--;
  140. if (razm == 0) break;
  141. else w = f.Pop();
  142. }
  143. t = strcat(t,a);
  144. t = strcat(t,b);
  145. return t;
  146.  
  147. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement