fork download 
  1. #include <stack>
  2. #include <string>
  3. #include <iostream>
  4. #include <array>
  5. #include <iomanip>
  6. #include <utility>
  7.  
  8. std::string quote(std::string s)
  9. {
  10.     return '"' + s + '"';
  11. }
  12.  
  13. template <typename T>
  14. T pop_top(std::stack<T>& stack)
  15. {
  16.     T result = stack.top();
  17.     stack.pop();
  18.     return result;
  19. }
  20.  
  21. // returns a bool/index pair.  If .first is true, then the parens balance, and .second
  22. // should be ignored.  If .first is false, then the parens don't balance, and .second
  23. // is the "index" where the offending paren was found, or if more parens were required
  24. // it is one past the end.
  25. std::pair<bool, std::size_t> parens_balance(const std::string& s)
  26. {
  27.     unsigned left_paren_count = 0;
  28.     unsigned right_paren_count = 0;
  29.     // char expression = 'a' ;
  30.  
  31.     std::stack<char> stack;
  32.  
  33.     auto ss = s.begin();
  34.     while (ss != s.end())
  35.     {
  36.         char ch = *ss++;
  37.  
  38.         if (ch == '(')
  39.         {
  40.             stack.push(ch);
  41.             // stack.push(expression++);
  42.  
  43.             ++left_paren_count;
  44.         }
  45.         else if (ch == ')')
  46.         {
  47.             if (++right_paren_count > left_paren_count || stack.empty())
  48.                 return std::make_pair(false, ss - s.begin() - 1);
  49.  
  50.             // auto indent_level = left_paren_count - right_paren_count;
  51.  
  52.             while (!stack.empty() && (ch = pop_top(stack)) != '(')
  53.                 /*std::cout << std::string(indent_level, ' ') << ch << '\n'*/;
  54.         }
  55.     }
  56.  
  57.     std::size_t index = s.size();
  58.     if (stack.empty() && left_paren_count < right_paren_count)
  59.         --index;
  60.  
  61.     return std::make_pair(stack.empty() && left_paren_count == right_paren_count, index);
  62. }
  63.  
  64. void report_unbalanced_parens(const std::string& expr, std::size_t index)
  65. {
  66.     std::cout << "Unbalanced parentheses detected in " << quote(expr) << ":\n\t";
  67.     std::cout << expr << "\n\t";
  68.     std::cout << std::string(index, ' ') << "^\n";
  69. }
  70.  
  71. int main()
  72. {
  73.     std::array<std::string, 10> expressions = 
  74.     { 
  75.         "(()(()))()(()",        // invalid
  76.         "(()(()))()(())",       // valid
  77.         "()",                   // valid
  78.         ")",                    // invalid
  79.         "(",                    // invalid
  80.         "()()()",               // valid
  81.         "(((()))((())))",       // valid
  82.         "))((",                 // invalid
  83.         "())(",                 // invalid
  84.         "(()(",                 // invalid
  85.     };
  86.  
  87.     for (auto& expression : expressions)
  88.     {
  89.         auto ret = parens_balance(expression);
  90.         if (ret.first)
  91.             std::cout << quote(expression) << " has balanced parentheses.\n";
  92.         else
  93.             report_unbalanced_parens(expression, ret.second);
  94.  
  95.         std::cout << '\n';
  96.     }
  97. }
Success #stdin #stdout 0s 3432KB
comments (?)
stdin 
Standard input is empty
stdout 
Unbalanced parentheses detected in "(()(()))()(()":
	(()(()))()(()
	             ^

"(()(()))()(())" has balanced parentheses.

"()" has balanced parentheses.

Unbalanced parentheses detected in ")":
	)
	^

Unbalanced parentheses detected in "(":
	(
	 ^

"()()()" has balanced parentheses.

"(((()))((())))" has balanced parentheses.

Unbalanced parentheses detected in "))((":
	))((
	^

Unbalanced parentheses detected in "())(":
	())(
	  ^

Unbalanced parentheses detected in "(()(":
	(()(
	    ^
https://ideone.com/urWb1n
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!