删除多余括号

【问题描述】输入一个表示算式的字符串（含四则运算、乘方、括号），要求去掉可能含有的多余括号，结果要保持原表达式中变量和运算符的相对位置不变，且与原表达式等价。注意，题目只是要求你去括号，并没有要求你化简表达式！此外，“+”和“-”不会用作正负号。

【分析】符合“多余括号”的情况：

① 括号内没有运算符；

② 括号左侧是加法运算符，右侧是加法或减法运算符； ③ 括号左侧是乘法运算符，右侧是乘法或除法运算符。

对于表达式求值的问题，我们常采用这样的思路处理：找出式中最后运算的运算符 A，先递归地求出其左右两边的值，再将得到的值进行 A 运算。当然这次没有必要进行运算，只需分析括号内的运算符情况就可以了。

#include <iostream> #include <cstring> using namespace std; int a[1024]; char s[1024]; int cal(int st, int stp, int prev) { int t, min=4, min_i;  for (int i=st; i<=stp; i++) {   switch (s)   {   case '^':    if (min>3) min=3, min_i=i;    break;   case '*': case '/':    if (min>2) min=2, min_i=i;    break;   case '+': case '-':    if (min>1) min=1, min_i=i;    break;   case '(':    i++;    for (t=1;t!=0;i++)    {

if (s=='(') t++;     if (s==')') t--;    }    i--;    break;   }; }   if (min==4) {   if (s[st]=='(' && s[stp]==')')   {    t=cal(st+1,stp-1,0);    if (t>=prev)    {     a[st]=a[stp]=1;     return t;    }   }   return 4; }   cal(st,min_i-1,min);  if (s[min_i]=='+' || s[min_i]=='*')   cal(min_i+1,stp,min);  else   cal(min_i+1,stp,min+1);   return min; } int main() {  cin>>s;  int sc=strlen(s);  cal(0,sc-1,0); for (int i=0;i<sc;i++) if (!a) cout<<s;  cout<<endl;  return 0; }