括号优化表达式处理问题解析

这个问题要求我们处理数学表达式，删除所有不必要的括号，同时保持表达式语义不变。关键在于正确处理运算符优先级和结合性，以及特殊的运算规则。

问题核心要点

1. 运算符优先级：$*$和$/$优先级高于$+$和$-$
2. 结合性：同优先级运算符左结合
3. 特殊规则：
   • 加法与减法、乘法与除法在特定情况下可结合
   • 不能交换操作数位置，不能改写运算顺序

代码实现

下面是完整的代码实现，包含中缀转后缀和后缀转优化中缀两个核心过程：

#include <bits/stdc++.h>
using namespace std;

// 判断字符是否为操作数（字母）
bool isOperand(char c) {
    return (c >= 'a' && c <= 'z');
}

map<char, int> priorityInfix;  // 中缀表达式运算符优先级
map<char, int> prioritySuffix; // 后缀表达式运算符优先级

// 中缀表达式转后缀表达式
void infixToSuffix(const string& infix, string& suffix) {
    suffix.clear();
    stack<char> st;
    int len = infix.length();
    
    for (int i = 0; i < len; ++i) {
        char c = infix[i];
        
        if (isOperand(c)) {
            // 操作数直接加入后缀表达式
            suffix += c;
        } 
        else if (c == ')') {
            // 遇到右括号，弹出栈中元素直到左括号
            while (st.top() != '(') {
                suffix += st.top();
                st.pop();
            }
            st.pop(); // 弹出左括号
        } 
        else if (c == '(') {
            // 左括号直接入栈
            st.push(c);
        } 
        else {
            // 处理运算符
            while (!st.empty() && st.top() != '(' && 
                   priorityInfix[st.top()] >= priorityInfix[c]) {
                suffix += st.top();
                st.pop();
            }
            st.push(c);
        }
    }
    
    // 处理栈中剩余运算符
    while (!st.empty()) {
        suffix += st.top();
        st.pop();
    }
}

// 表达式结构体，存储表达式和运算符优先级
struct Expression {
    string expr;    // 表达式字符串
    int priority;   // 运算符优先级
    
    Expression(string e) : expr(e), priority(0x7fffffff) {}  // 操作数优先级设为极大值
    Expression(string e, int p) : expr(e), priority(p) {}
};

// 后缀表达式转优化中缀表达式
void suffixToInfix(const string& suffix, string& infix) {
    stack<Expression> st;
    int len = suffix.length();
    
    for (int i = 0; i < len; ++i) {
        char c = suffix[i];
        
        if (isOperand(c)) {
            // 操作数直接入栈
            st.push(Expression(string(1, c)));
        } 
        else {
            // 处理运算符，先取出右操作数
            Expression right = st.top();
            st.pop();
            string tmp2;
            
            // 判断右操作数是否需要加括号
            if (right.priority < prioritySuffix[c] || 
                (right.priority == prioritySuffix[c] && (c == '-' || c == '/'))) {
                tmp2 = "(" + right.expr + ")";
            } else {
                tmp2 = right.expr;
            }
            
            // 取出左操作数
            Expression left = st.top();
            st.pop();
            string tmp1;
            
            // 判断左操作数是否需要加括号
            if (left.priority < prioritySuffix[c]) {
                tmp1 = "(" + left.expr + ")";
            } else {
                tmp1 = left.expr;
            }
            
            // 组合左右操作数和运算符
            tmp1 += c;
            tmp1 += tmp2;
            
            // 将新表达式入栈，记录运算符优先级
            st.push(Expression(tmp1, prioritySuffix[c]));
        }
    }
    
    // 最终结果即为优化后的中缀表达式
    infix = st.top().expr;
}

int main() {
    // 初始化运算符优先级
    priorityInfix['+'] = 1;
    priorityInfix['-'] = 1;
    priorityInfix['*'] = 2;
    priorityInfix['/'] = 2;
    
    prioritySuffix['+'] = 1;
    prioritySuffix['-'] = 1;
    prioritySuffix['*'] = 2;
    prioritySuffix['/'] = 2;
    
    int t;
    cin >> t;
    string infix, suffix, result;
    
    while (t--) {
        cin >> infix;
        // 中缀转后缀
        infixToSuffix(infix, suffix);
        // 后缀转优化中缀
        suffixToInfix(suffix, result);
        // 输出结果
        cout << result << endl;
    }
    
    return 0;
}

算法解析

1. 中缀转后缀表达式：

   • 按照运算符优先级和括号规则，将中缀表达式转换为后缀表达式
   • 操作数直接加入结果，运算符根据优先级入栈或弹出

2. 后缀转优化中缀表达式：

   • 使用自定义的Expression结构体存储表达式和运算符优先级
   • 处理每个运算符时，判断左右操作数是否需要添加括号：
     • 右操作数：当优先级低于当前运算符，或优先级相同且为-/`时需要括号
     • 左操作数：当优先级低于当前运算符时需要括号
   • 操作数的优先级设为极大值，确保其外不会被添加括号

复杂度分析

• 时间复杂度：O(n)，其中n为表达式长度，两次扫描表达式完成转换
• 空间复杂度：O(n)，主要用于存储栈结构和中间表达式