SHARE
TWEET

Untitled

bbescos Jan 27th, 2019 55 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.  
  104. // Run-time complexity O(n)
  105. // Memory complexity O(n)
  106. // Much cleaner like this
  107. bool isOpener(char c) {
  108.         return c=='(' || c=='[' || c=='{';
  109.     }
  110.     bool isCloser(char c) {
  111.         return c==')' || c==']' || c=='}';
  112.     }
  113.    
  114.     unordered_map<char, char> opposites = {
  115.         {'(', ')'},
  116.         {'[', ']'},
  117.         {'{', '}'}
  118.     };
  119.    
  120.     bool isValid(const string& s) {
  121.         stack<char> stk;
  122.        
  123.         for (char c : s) {
  124.             if (isOpener(c)) {
  125.                 stk.push(opposites[c]);
  126.             }
  127.             else if (isCloser(c)) {
  128.                 if (stk.empty() || stk.top() != c)
  129.                     return false;
  130.                 stk.pop();
  131.             }
  132.         }
  133.        
  134.         return stk.empty();
  135.        
  136.     }
  137.  
  138.  
  139. int main()
  140. {
  141.     string ex1 = "(())()()())()";
  142.     bool sol1 = false;
  143.     bool est1 = isCorrect(ex1);
  144.    
  145.     string ex2 = "(())()()(())()";
  146.     bool sol2 = true;
  147.     bool est2 = isCorrect(ex2);
  148.    
  149.     string ex3 = "(())()()(())(()";
  150.     bool sol3 = false;
  151.     bool est3 = isCorrect(ex1);
  152.    
  153.     string ex4 = "([])({})(){(())}()";
  154.     bool sol4 = true;
  155.     bool est4 = isCorrect(ex4);
  156.    
  157.     string ex5 = "([])({)}(){(())}()";
  158.     bool sol5 = false;
  159.     bool est5 = isCorrect(ex5);
  160.  
  161.     std::cout << "Solution Ex1: " << sol1 << std::endl;
  162.     std::cout << "Estimation Ex1: " << est1 << std::endl;
  163.     std::cout << "-----------------" << std::endl;
  164.     std::cout << "Solution Ex2: " << sol2 << std::endl;
  165.     std::cout << "Estimation Ex2: " << est2 << std::endl;
  166.     std::cout << "-----------------" << std::endl;
  167.     std::cout << "Solution Ex3: " << sol3 << std::endl;
  168.     std::cout << "Estimation Ex3: " << est3 << std::endl;
  169.     std::cout << "-----------------" << std::endl;
  170.     std::cout << "Solution Ex4: " << sol4 << std::endl;
  171.     std::cout << "Estimation Ex4: " << est4 << std::endl;
  172.     std::cout << "-----------------" << std::endl;
  173.     std::cout << "Solution Ex5: " << sol5 << std::endl;
  174.     std::cout << "Estimation Ex5: " << est5 << std::endl;
  175.  
  176.     return 0;
  177. }
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