fork(4) download
copy 
  1. /**
  2.  
  3. AUTHOR:Rahul Shah
  4. LINK:http://w...content-available-to-author-only...j.com/problems/CMEXPR
  5. PROBLEM:Complicated Expression
  6.  
  7. **/
  8.  
  9. #include <iostream>
  10. #include <cstdio>
  11. using namespace std;
  12. int pre[256];
  13. int main() 
  14. {
  15. 	int t;
  16.  
  17. 	scanf("%d",&t);
  18. 	while(t--)
  19. 	{
  20. 		string s,ans="";
  21. 		//setting precedence for the operators
  22. 		pre['*']=2;
  23. 		pre['/']=2;
  24. 		pre['+']=1;
  25. 		pre['-']=1;
  26. 		cin>>s;
  27. 		int n=s.length();
  28. 		int cnt=0;
  29. 		int mn=1000; //minimum precedence level of an expression
  30. 		/*
  31. 		rem-whether the ith character has to be removed or not
  32. 		prel-precedence level of the expression under consideration
  33. 		lb-position of the left paranthesis(brackets)
  34. 		*/
  35. 		int prel[251],lb[251],rem[251];
  36. 		for(int i=0;i<n;i++)
  37. 			rem[i]=-1;			
  38. 		int k=0,m=0;	//used as stack top for lb,prel
  39. 		for(int i=0;i<n;i++)
  40. 		{
  41. 			if(s[i]=='(')
  42. 			{
  43. 				prel[k++]=mn;
  44. 				lb[m++]=i;
  45. 				mn=1000;
  46. 				cnt++;
  47. 			}
  48. 			//for(in)
  49. 			else if(s[i]==')')
  50. 			{
  51. 				int st=lb[--m],en=i;
  52.  
  53. 				bool remove=true;
  54. 				//if the operator before the left paranthesis is +,-,*,/
  55. 				if(st>=0&&pre[s[st-1]]>=1)	
  56. 				{
  57. 					/*if mn is greater than precedence level then the
  58. 					paranthesis are redundant and hence can be omitted*/	
  59. 					if(mn<=pre[s[st-1]])	
  60. 					{
  61. 						remove=false;
  62. 						//if they are equal then left association is checked
  63. 						if(mn==pre[s[st-1]]&&(s[st-1]=='*'||s[st-1]=='+'))	
  64.  
  65. 						{
  66. 							remove=true;
  67. 						}
  68. 					}
  69. 				}
  70. 				//Similarly, the operator after the paranthesis is checked
  71. 				if(remove&&en<n-1&&pre[s[en+1]]>=1)
  72. 				{
  73. 					if(mn<=pre[s[en+1]])
  74. 					{
  75. 						remove=false;
  76. 						if(mn==pre[s[en+1]])
  77. 						{
  78. 							remove=true;
  79. 						}
  80. 					}
  81. 				}
  82. 				//cout<<st<<" "<<en<<" "<<mn<<" "<<pre[s[st-1]]<<" "<<pre[s[en+1]]<<" "<<remove<<"\n";
  83. 				rem[st]=rem[en]=remove;
  84. 				mn=min(mn,prel[--k]);
  85. 				cnt--;
  86. 			}
  87. 			else if(cnt!=0)
  88. 			{
  89. 				if(pre[s[i]]>=1)
  90. 				{
  91. 					mn=min(mn,pre[s[i]]);//e.g. (a+b-c*d) min preced is 1 of +.
  92. 				}
  93. 			}
  94. 			else
  95. 				rem[i]=-1;
  96. 		}
  97. 		for(int i=0;i<n;i++)
  98. 		{
  99. 			if(rem[i]<=0)
  100. 				ans+=s[i];
  101.  
  102. 		}
  103. 		cout<<ans<<"\n";
  104. 	}
  105. 	return 0;
  106. }
Success #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
1
a+((a+c+x))*((x+y))
stdout
copy 
a+(a+c+x)*(x+y)
https://ideone.com/PNo6Dh
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
secret

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!