2013
11-28

# Complicated Expressions

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.

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.

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”.

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)

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)

1.单个操作数是一个表达式，优先级是3，表达式运算符号未知。这种表达命名是E1

2.两个E1（就两个单操作数）可以根据操作符号形成一个行的表达式，优先级由操作符来定（加减为1，乘除为2），表达式运算符就是操作操作符。这种表达命名是E2

3.两个E2可以根据操作符号形成一个行的表达式，优先级由操作符来定（加减为1，乘除为2），表达式运算符就是操作操作符。这种表达命名是E3

1， 组合两个表达式的符号如果是+或-，

a.是+,则左右两个表达式直接由+组合起来

b.是-，如果右表达式的优先级是1，加括号，否则不加，而左表达式，是什么样就什么样。然后左右两个表达式由-组合起来

2， 组合两个表达式的符号如果是*或/，

a.是*,则左右两个表达式里只有优先级1级才用括号括起来，其余（单个操作数和2级运算）情况都直接组合。最后左右两个表达式由*组合起来

b.是/，左表达式只有优先级1级的情况才用括号括起来，右表达式只有优先级3级的情况（单个操作数）才不会用括号括起来。最后左右两个表达式由/组合起来

#include <iostream>
#include <stack>
#include <iomanip>
using namespace std;
struct Expression
{
char*  exp;
int type;
char op;
};
int main()
{
int tc =0;
int table[130][130];
table['+']['+']= 1; table['+']['-']= 1; table['+']['*']=-1; table['+']['/']=-1; table['+']['(']=-1;     table['+'][')']=1;      table['+']['#']=1;
table['-']['+']= 1; table['-']['-']= 1; table['-']['*']=-1; table['-']['/']=-1; table['-']['(']=-1;     table['-'][')']=1;      table['-']['#']=1;
table['*']['+']= 1; table['*']['-']= 1; table['*']['*']= 1; table['*']['/']= 1; table['*']['(']=-1;     table['*'][')']=1;      table['*']['#']=1;
table['/']['+']= 1; table['/']['-']= 1; table['/']['*']= 1; table['/']['/']= 1; table['/']['(']=-1;     table['/'][')']=1;      table['/']['#']=1;
table['(']['+']=-1; table['(']['-']=-1; table['(']['*']=-1; table['(']['/']=-1; table['(']['(']=-1;     table['('][')']=0;      table['(']['#']=-10000;
table[')']['+']= 1; table[')']['-']= 1; table[')']['*']= 1; table[')']['/']= 1; table[')']['(']=-10000; table[')'][')']=1;      table[')']['#']=1;
table['#']['+']=-1; table['#']['-']=-1; table['#']['*']=-1; table['#']['/']=-1; table['#']['(']=-1;     table['#'][')']=-10000; table['#']['#']=0;
scanf("%d",&tc);
while(tc>0)
{
char input[255];
scanf("%s",input);
stack<char> operators;
operators.push('#');
stack<Expression>  operands;
::strcat(input,"#");
for(int i=0;i<::strlen(input);i++)
{
if(input[i] == '#'||input[i] == '+'||input[i] == '-'||input[i] == '*'||input[i] == '/'||input[i] == '('||input[i] == ')')
{
char topOp = operators.top();
if(table[topOp][input[i]]<0)
operators.push(input[i]);
else if(table[topOp][input[i]]==0)
operators.pop();
else
{
i--;
operators.pop();
Expression exp2 = operands.top();
operands.pop();
Expression exp1 = operands.top();
operands.pop();
char* expA = exp1.exp;
char* expB = exp2.exp;
Expression n_exp;
n_exp.op = topOp;
n_exp.exp=new char[300];
n_exp.exp[0]='\0';
if(topOp == '+'||topOp == '-')
{
::strcat(n_exp.exp,expA);
::strcat(n_exp.exp,topOp=='+'?"+":"-");
if(topOp == '-' && exp2.type==1)
{
::strcat(n_exp.exp,"(");
::strcat(n_exp.exp,expB);
::strcat(n_exp.exp,")");
}
else
::strcat(n_exp.exp,expB);
n_exp.type=1;
operands.push(n_exp);
}
if(topOp == '*'||topOp == '/')
{
if(exp1.type==1)
{
::strcat(n_exp.exp,"(");
::strcat(n_exp.exp,expA);
::strcat(n_exp.exp,")");
}
else
::strcat(n_exp.exp,expA);
::strcat(n_exp.exp,topOp=='*'?"*":"/");
if(exp2.type==1 || (topOp=='/'&&exp2.type==2))
{
::strcat(n_exp.exp,"(");
::strcat(n_exp.exp,expB);
::strcat(n_exp.exp,")");
}
else
::strcat(n_exp.exp,expB);
n_exp.type=2;
operands.push(n_exp);
}
delete[] expA;
delete[] expB;
}
}
else
{
int j=i;
while(!(input[i] == '#'||input[i] == '+'||input[i] == '-'||input[i] == '*'||input[i] == '/'||input[i] == '('||input[i] == ')') && i<::strlen(input))
i++;
Expression exp;
exp.type=3;
exp.op='?';
exp.exp = new char[i-j+1];
for(int k=0;k<i-j+0;k++)
exp.exp[k] = input[j+k];
exp.exp[i-j+0]='\0';
operands.push(exp);
i--;
}
}
cout<<operands.top().exp<<endl;
tc--;
}
return 0;
}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮