题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1123
方法：和使用堆栈来计算四则混合运算一样，唯一的区别在于计算两个操作数的时候不是计算运算结果，和计算起表达式，这里操作数也是表达式，表达式根据符号计算出新的表达式。
规定：
1.单个操作数是一个表达式，优先级是3，表达式运算符号未知。这种表达命名是E1
2.两个E1（就两个单操作数）可以根据操作符号形成一个行的表达式，优先级由操作符来定（加减为1，乘除为2），表达式运算符就是操作操作符。这种表达命名是E2
3.两个E2可以根据操作符号形成一个行的表达式，优先级由操作符来定（加减为1，乘除为2），表达式运算符就是操作操作符。这种表达命名是E3
所以该题目主要就是一个模拟表达式组合的问题，组合的时候，使用以下规则：
1， 组合两个表达式的符号如果是+或-，
a.是+,则左右两个表达式直接由+组合起来
b.是-，如果右表达式的优先级是1，加括号，否则不加，而左表达式，是什么样就什么样。然后左右两个表达式由-组合起来
2， 组合两个表达式的符号如果是*或/，
a.是*,则左右两个表达式里只有优先级1级才用括号括起来，其余（单个操作数和2级运算）情况都直接组合。最后左右两个表达式由*组合起来
b.是/，左表达式只有优先级1级的情况才用括号括起来，右表达式只有优先级3级的情况（单个操作数）才不会用括号括起来。最后左右两个表达式由/组合起来
初始时候，由两个E1开始组合，最后一步一步组合出结果。
代码：
#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]=' ';
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]=' ';
operands.push(exp);
i--;
}
}
cout<<operands.top().exp<<endl;
tc--;
}
return 0;
}