解题思路

这道题的目标是去除算术表达式中不必要的括号，同时保证运算顺序不变。关键在于：

1. 构建表达式树（或操作符树），记录每个运算符的优先级和子表达式。
2. 递归解析表达式，按照运算符优先级和结合性分解表达式。
3. 在输出时判断是否需要括号：
   • 如果子表达式的优先级低于当前运算符，则需要加括号。
   • 如果子表达式的优先级等于当前运算符，且当前运算符是 - 或 /，则需要反转子表达式的运算符（+ ↔ -，* ↔ /）。
   • 否则，直接输出子表达式。

#include<cstdio>
#define MAXN 1010
using namespace std;

struct ops
{
    int l,r,pr;
    char op;
};

ops o[MAXN];
char s[MAXN];
int k,p;
int expr();

int createOps(int l,int r,char op,int pr)
{
    k++;
    o[k].l=l;
    o[k].r=r;
    o[k].pr=pr;
    o[k].op=op;
    return k;
}

int factor()
{
    if(s[p]>='a'&&s[p]<='z')
        return createOps(0,0,s[p++],3);
    else
    {
        p++;
        int ret = expr();
        p++;
        return ret;
    }
}

int term()
{
    int l,r;
    char op;
    l=factor();
    while(s[p]=='*'||s[p]=='/')
    {
        op=s[p++];
        r=factor();
        l=createOps(l,r,op,2);
    }
    return l;
}

int expr()
{
    int l,r;
    char op;
    l=term();
    while(s[p]=='+'||s[p]=='-')
    {
        op=s[p++];
        r=term();
        l=createOps(l,r,op,1);
    }
    return l;
}

void Print(int n,bool inverse)
{
    int l,r;
    if(o[n].op>='a'&&o[n].op<='z')
    {
        putchar(o[n].op);
        return;
    }
    l=o[n].l;
    r=o[n].r;
    if(o[l].pr>o[n].pr)
        Print(l,false);
    else if(o[l].pr<o[n].pr)
    {
        putchar('(');
        Print(l,false);
        putchar(')');
    }
    else
        Print(l,inverse);
        
    if(!inverse)
        putchar(o[n].op);
    else if(o[n].op=='+')
        putchar('-');
    else if(o[n].op=='-')
        putchar('+');
    else if(o[n].op=='*')
        putchar('/');
    else
        putchar('*');
    
    if(o[r].pr>o[n].pr)
        Print(r,false);
    else if(o[r].pr<o[n].pr)
    {
        putchar('(');
        Print(r,false);
        putchar(')');
    }
    else
    {
        if(o[n].op=='-'||o[n].op=='/')
            inverse=!inverse;
        Print(r,inverse);
    }
}

int main()
{
    fgets(s, MAXN, stdin);
    // 移除fgets可能读取的换行符
    for(int i = 0; s[i]; i++) {
        if(s[i] == '\n') {
            s[i] = '\0';
            break;
        }
    }
    k=p=0;
    int n=expr();
    Print(n,false);
    return 0;    
}