fork(5) download
copy 
  1. // C++ program to find minimum number of
  2. // reversals required to balance an expression
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6.  
  7. // Returns count of minimum reversals for making
  8. // expr balanced. Returns -1 if expr cannot be
  9. // balanced.
  10. int countMinReversals(string expr)
  11. {
  12. 	int len = expr.length();
  13.  
  14. 	// length of expression must be even to make
  15. 	// it balanced by using reversals.
  16. 	if (len%2)
  17. 	return -1;
  18.  
  19. 	int  open=0,close=0,toReverse=0;
  20. 	stack<char> s;
  21. 	for (int i=0; i<len; i++)
  22. 	{
  23. 		if (expr[i]=='{')
  24. 		   open++;
  25. 		else
  26. 		{
  27. 		    if (open>0)
  28. 		    open--;
  29. 		    else
  30. 	      {	toReverse++;
  31. 	      open++;
  32. 	      }
  33. 		}
  34. 	}
  35.      toReverse +=open/2;
  36.  
  37.  
  38.  
  39. 	return  toReverse;
  40. }
  41.  
  42. // Driver program to test above function
  43. int main()
  44. {
  45. string expr = "}}{{";
  46. cout << countMinReversals(expr);
  47. return 0;
  48. }
  49.  
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
https://ideone.com/sACjO3
language:
C++14 (gcc 8.3)
created:
9 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!