| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 911 | Accepted: 329 |
Description
The most important activity of ACM is the GSM network. As the mobile phone operator, ACM must build its own transmitting stations. It is very important to compute the exact behaviour of electro-magnetic waves. Unfortunately, prediction of electro-magnetic fields is a very complex task and the formulas describing them are very long and hard-to-read. For example, below are the Maxwell's Equations describing the basic laws of electrical engineering.
ACM has designed its own computer system that can make some field computations and produce results in the form of mathematic expressions. Unfortunately, by generating the expression in several steps, there are always some unneeded parentheses inside the expression. Your task is to take these partial results and make them "nice" by removing all unnecessary parentheses.
Input
There is a single positive integer T on the first line of input. It stands for the number of expressions to follow. Each expression consists of a single line containing only lowercase letters, operators (+, -, *, /) and parentheses (( and )). The letters are variables that can have any value, operators and parentheses have their usual meaning. Multiplication and division have higher priority then subtraction and addition. All operations with the same priority are computed from left to right (operators are left-associative). There are no spaces inside the expressions. No input line contains more than 250 characters.Output
Print a single line for every expression. The line must contain the same expression with unneeded parentheses removed. You must remove as many parentheses as possible without changing the semantics of the expression. The semantics of the expression is considered the same if and only if any of the following conditions hold:- The ordering of operations remains the same. That means "(a+b)+c" is the same as "a+b+c", and "a+(b/c)" is the same as "a+b/c".
- The order of some operations is swapped but the result remains unchanged with respect to the addition and multiplication associativity. That means "a+(b+c)" and "(a+b)+c" are the same. We can also combine addition with subtraction and multiplication with division, if the subtraction or division is the second operation. For example, "a+(b-c)" is the same as "a+b-c".
You cannot use any other laws, namely you cannot swap left and right operands and you cannot replace "a-(b-c)" with "a-b+c".
Sample Input
8
(a+(b*c))
((a+b)*c)
(a*(b*c))
(a*(b/c)*d)
((a/(b/c))/d)
((x))
(a+b)-(c-d)-(e/f)
(a+b)+(c-d)-(e+f)
Sample Output
a+b*c
(a+b)*c
a*b*c
a*b/c*d
a/(b/c)/d
x
a+b-(c-d)-e/f
a+b+c-d-(e+f)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cctype>
#include<algorithm>
using namespace std;
const int N=1000;
void _change(string &str,string &res)//中缀转后缀,后缀由空格隔开
{
char _stack[N];//操作符栈
int top=-1;
int len=str.size();
for(int i=0;i<len;i++)
{
switch(str[i])
{
case '(':_stack[++top]='(';break;
case '+':
case '-':
while(top>=0&&_stack[top]!='(')
res+=_stack[top--];
_stack[++top]=' ';//important
_stack[++top]=str[i];
break;
case '*':
case '/':
while(top>=0&&_stack[top]!='('&&_stack[top]!='+'&&_stack[top]!='-')
res+=_stack[top--];
_stack[++top]=' ';
_stack[++top]=str[i];
break;
case ')':while(top>=0&&_stack[top]!='(')
res+=_stack[top--];
top--;
break;
default:
res+=str[i];
if(i==len-1) res+=' ';
else if(!isalpha(str[i+1])) res+=' ';
}
}
while(top>=0) res+=_stack[top--];
}
void change_(string &res,string &cnt)//后缀转中缀,res中由空格隔开,str中无空格和多余的括号
{
string _stack[N];//中缀表达式栈
int priority[N];//优先级,操作数 0,+ - 1,* / 2;
int top=-1;
int len=res.size();
int k,c;//k 优先级,c 是否添加括号
string tmp1,tmp2;
for(int i=0;i<len;i++)
{
switch(res[i])
{
case ' ': break;
//遇到操作符，此处操作符假定都是双目的(+ - * /)
case '+':
case '-':
case '*':
case '/':
//如果最后一个进栈(即当前栈顶元素)的是操作符，
//且1/它的优先级低于当前输入字符；
if(res[i]=='*'||res[i]=='/') k=2;
else k=1;
//或者2/当优先级相同，且当前输入字符是’/’或’-’时
//将栈顶元素弹出并在两边添加圆括号之后，存入临时变量tmp2中；
//否则直接将栈顶元素存入临时变量tmp2中。
if(res[i]=='/'||res[i]=='-') c=1;//可能加括号
else c=0;
//弹出第一个栈顶元素
if(priority[top]&&//是操作符
(priority[top]<k)||(priority[top]==k&&c))//优先级低或者相同且为/或-
{
//加括号
tmp2.clear();
tmp2+='(';
tmp2+=_stack[top];
tmp2+=')';
}
else
{
//不加括号
tmp2.clear();
tmp2=_stack[top];
}
//弹出栈顶元素
--top;
if(priority[top]&&priority[top]<k)//是操作符,且优先级小于当前字符
{
//加括号
tmp1.clear();
tmp1+='(';
tmp1+=_stack[top];
tmp1+=')';
}
else
{
//不加括号
tmp1.clear();
tmp1=_stack[top];
}
_stack[top]=tmp1+res[i]+tmp2;
priority[top]=k;
break;
default:
//遇到操作数，直接进堆栈；
_stack[++top]=res[i];
priority[top]=0;i++;
while(isalpha(res[i])) _stack[top]+=res[i],i++;i--;
break;
}
}
cnt=_stack[0];
}
int main()
{
char s[400];
int ci;scanf("%d",&ci);
while(ci--&&scanf("%s",s)==1)
{
string str=s,res,cnt;
_change(str,res);//中缀转后缀
change_(res,cnt);//后缀转中缀
printf("%s/n",cnt.c_str());//用cout就超时 真极限
}
return 0;
}