小诚进了中学之后,学到了代数表达式,但是表达式中总是会出现很多让人烦恼的括号,而实际上,有很多括号是可以去除掉的。
比如说 a+(b+c)−d 就可以把括号去除,变为 a+b+c−d。
而 a+(b+c)−d 可以去除括号后变为 a+b+c−d。
小诚对计算机编程很感兴趣,所以她想是不是可以用计算机来解决这个问题。
你能帮助她完成这个任务吗?
第一行有一个整数 n。表示总共有 n 个表达式需要处理。
接下来 n 行,每一行一个待处理的表达式,长度不超过 255,并且不含空格字符。
表达式中的所有变量都是单个小写的英文字母,运算符只有加 + 减 - 乘 * 除 /。
也就是说,在表达式中可能出现的字符为:a~z,+,−,∗,/,(,)。
数据保证表达式合法。
另外不考虑 用作正负号的情况,即输入表达式中不会出现 (+a) 或 (−a) 的情形。
对于每个表达式输出去除括号后的表达式。
9
(a-a)
a+(b+c)-d
a-(b+a)+d
(a+b)*(c+d)
(a*b)+c/d
((a+b)*f)-(i/j)
a*(b/c)
a-(b+c+(d*a))
a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*(p-q)+r*(s*t)*(u-(v+(w*x))*y)+z
a-a
a+b+c-d
a-b-a+d
(a+b)*(c+d)
a*b+c/d
(a+b)*f-i/j
a*b/c
a-b-c-d*a
a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*(p-q)+r*s*t*(u-(v+w*x)*y)+z
1≤n≤10
不需要对表达式进行化简:如果表达式为 ,答案同表达式。
不需要为了消去括号进行展开:如果表达式为 (a+b)∗(c+d),答案同表达式。
更具体的,若表达式原先出现了 m 次变量,则输出时仍应保持 m 次变量,且不应改变这些变量的顺序。
另外,保证不会出现空串的情形,即不会出现 ()。
保证表达式均合法。
以下是本蒟蒻的代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,l,yx,ls,wz[266],bj[266],len=0;
string s;
signed main(){
// freopen("bracket.in","r",stdin);
// freopen("bracket.out","w",stdout);
scanf("%lld",&n);
while(n--){
cin>>s;
memset(bj,0,sizeof(bj));
for(int i=0;i<s.size();i++){
if(s[i]=='('){
l=1;
ls=s.size();
yx=0;
len=0;
for(int j=i+1;j<s.size();j++){
if(l==0){
ls=j;
break;
}
if(s[j]=='('){
l++;
}
if(s[j]==')'){
l--;
}
if((s[j]=='+'||s[j]=='-')&&l==1){
wz[++len]=j;
yx=1;
}
if((s[j]=='*'||s[j]=='/')&&l==1&&yx==0){
yx=2;
}
}
if(yx==1&&(i-1<0||s[i-1]=='+'||s[i-1]=='-'||s[i-1]=='(')&&(ls==s.size()||s[ls]=='+'||s[ls]=='-'||s[ls]==')')){
if(s[i-1]=='-'){
for(int j=1;j<=len;j++){
bj[wz[j]]=2;
}
}
bj[i]=1;
bj[ls-1]=1;
}
if(yx==2){
if(s[i-1]=='/'){
for(int j=1;j<=len;j++){
bj[wz[j]]=2;
}
}
bj[i]=1;
bj[ls-1]=1;
}
}
}
for(int i=0;i<s.size();i++){
if(bj[i]==1){
continue;
}
if(bj[i]==2){
if(s[i]=='+'){
cout<<'-';
}
if(s[i]=='-'){
cout<<'+';
}
if(s[i]=='*'){
cout<<'/';
}
if(s[i]=='/'){
cout<<'*';
}
continue;
}
cout<<s[i];
}
cout<<endl;
}
return 0;
}