SHARE
TWEET

Untitled

bbescos Jan 21st, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <queue>
  3. #include <stack>
  4.  
  5. using namespace std;
  6.  
  7. // Cases:
  8. // )()
  9. // ()(
  10. // )()(
  11.  
  12. // Run-time complexity O(n)
  13. // Memory complexity O(1)
  14. bool isCorrect(const string& sChars){
  15.     int sum = 0;
  16.     for (char c : sChars){
  17.         if (c == '(')
  18.             ++sum;
  19.         if  (c == ')')
  20.             --sum;
  21.         if (sum < 0)
  22.             return false;
  23.     }
  24.    
  25.     if (sum != 0)
  26.         return false;
  27.     else
  28.         return true;
  29. }
  30.  
  31. // Run-time complexity O(n)
  32. // Memory complexity O(n)
  33. bool isCorrect(const string& sChars){
  34.    
  35.     stack<char> stackChars;
  36.    
  37.     for (char c : sChars){
  38.         if (c == '(')
  39.             stackChars.push(c);
  40.         if (c == ')')
  41.             if (!stackChars.empty())
  42.                 stackChars.pop();
  43.             else
  44.                 return false;
  45.     }
  46.    
  47.     if (stackChars.empty())
  48.         return true;
  49.     else
  50.         return false;
  51.    
  52. }
  53.  
  54. // Now there are not only parenthesis. There are also brackets [] and curly braces {}
  55. // Cases
  56. // )()
  57. // ()(
  58. // )()(
  59. // The same as before for all (), [] and {}
  60. // ({)}
  61. // Run-time complexity O(n)
  62. // Memory complexity O(n)
  63. bool isCorrect(const string& sChars){
  64.    
  65.     stack<char> stackChars;
  66.    
  67.     for (char c : sChars){
  68.         if (c == '(' || c == '[' || c == '{')
  69.             stackChars.push(c);
  70.         if (c == ')' || c == ']' || c == '}'){
  71.             if (!stackChars.empty()){
  72.                 if (c == ')'){
  73.                     if (stackChars.top() == '(')
  74.                         stackChars.pop();
  75.                     else
  76.                         return false;
  77.                 }
  78.                 if (c == ']'){
  79.                     if (stackChars.top() == '[')
  80.                         stackChars.pop();
  81.                     else
  82.                         return false;
  83.                 }
  84.                 if (c == '}'){
  85.                     if (stackChars.top() == '{')
  86.                         stackChars.pop();
  87.                     else
  88.                         return false;
  89.                 }
  90.             }
  91.             else
  92.                 return false;
  93.         }
  94.     }
  95.    
  96.     if (stackChars.empty())
  97.         return true;
  98.     else
  99.         return false;
  100.    
  101. }
  102.  
  103. int main()
  104. {
  105.     string ex1 = "(())()()())()";
  106.     bool sol1 = false;
  107.     bool est1 = isCorrect(ex1);
  108.    
  109.     string ex2 = "(())()()(())()";
  110.     bool sol2 = true;
  111.     bool est2 = isCorrect(ex2);
  112.    
  113.     string ex3 = "(())()()(())(()";
  114.     bool sol3 = false;
  115.     bool est3 = isCorrect(ex1);
  116.    
  117.     string ex4 = "([])({})(){(())}()";
  118.     bool sol4 = true;
  119.     bool est4 = isCorrect(ex4);
  120.    
  121.     string ex5 = "([])({)}(){(())}()";
  122.     bool sol5 = false;
  123.     bool est5 = isCorrect(ex5);
  124.  
  125.     std::cout << "Solution Ex1: " << sol1 << std::endl;
  126.     std::cout << "Estimation Ex1: " << est1 << std::endl;
  127.     std::cout << "-----------------" << std::endl;
  128.     std::cout << "Solution Ex2: " << sol2 << std::endl;
  129.     std::cout << "Estimation Ex2: " << est2 << std::endl;
  130.     std::cout << "-----------------" << std::endl;
  131.     std::cout << "Solution Ex3: " << sol3 << std::endl;
  132.     std::cout << "Estimation Ex3: " << est3 << std::endl;
  133.     std::cout << "-----------------" << std::endl;
  134.     std::cout << "Solution Ex4: " << sol4 << std::endl;
  135.     std::cout << "Estimation Ex4: " << est4 << std::endl;
  136.     std::cout << "-----------------" << std::endl;
  137.     std::cout << "Solution Ex5: " << sol5 << std::endl;
  138.     std::cout << "Estimation Ex5: " << est5 << std::endl;
  139.  
  140.     return 0;
  141. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top