C++数据结构：给一个中缀算术表达式，按优先级添加括号，如输入表达式31+23-45*54/(9-6)^4，输出((31+23)-((45*54)/((9-6)^4)))

中缀算术表达式的逆波兰表示（也称为后缀表示或RPN，Reverse Polish Notation）可以解决这个问题。转换过程主要是将原表达式按照运算符的优先级和结合性添加合适的括号。对于C++来说，我们可以使用栈来辅助完成这个任务。

首先，我们需要定义一个函数来判断运算符的优先级，通常遵循常见的数学运算规则：乘除高于加减，括号内的运算优先。然后遍历输入的中缀表达式，遇到数字就直接压入栈；遇到左括号则直接入栈；遇到右括号，则弹出栈顶元素直至遇到左括号，并在此过程中添加相应的闭合括号；遇到运算符，比较其优先级，若当前运算符优先级低于栈顶运算符，则不断出栈并加上括号，直到栈顶运算符优先级低于当前运算符，再将当前运算符压入栈。

下面是简化版的伪代码：

void parenthesize(const string& infix) {
    stack<char> s;
    stack<pair<char, int>> priority;
    // 初始化优先级队列，例如：{')', 0}, {')', 1}, {'*', 2}, {'/', 2}, {'+', 1}, {'-', 1}
    for (char c : infix) {
        if (isdigit(c)) {
            cout << c; // 数字直接输出
        } else if (c == '(') {
            s.push(c);
        } else if (c == ')') {
            while (!s.empty() && s.top() != '(') {
                cout << ')';
                s.pop();
            }
            if (!s.empty()) {
                s.pop(); // 出栈左括号
            }
            cout << ")";
        } else {
            while (!priority.empty() && priority.top().second >= precedence(c)) {
                cout << ')';
                s.pop();
                priority.pop();
            }
            priority.push({c, precedence(c)}); // 先进后出，保存当前运算符和优先级
            cout << c;
        }
    }
    while (!s.empty()) {
        cout << ')';
        s.pop();
    }
}

// 假设precedence函数计算运算符的优先级
int precedence(char op) {
    // 实现实际的优先级计算逻辑
}

当你运行这个函数，传入给定的表达式 "31+23-45*54/(9-6)^4"，它会返回 ((31+23)-(45*(54)/(9-(6))^4)) 这样的后缀表达式，或者包含适当括号的等效形式。