qt中缀表达式转前缀表达式

在Qt中，可以使用QStack来实现中缀表达式转前缀表达式。

具体步骤如下：

1. 从右至左扫描中缀表达式，将操作数压入栈中。

2. 遇到运算符时，判断栈顶元素的优先级，如果栈顶元素的优先级大于当前运算符，则将栈顶元素弹出并加入前缀表达式中，直到栈顶元素的优先级小于等于当前运算符的优先级。

3. 将当前运算符压入栈中。

4. 最后将栈中剩余的运算符依次弹出并加入前缀表达式中。

5. 将前缀表达式翻转即可得到最终的前缀表达式。

下面是一个实现中缀表达式转前缀表达式的示例代码：

QString infixToPrefix(QString infix)
{
    QString prefix;
    QStack<QChar> stack;
    int len = infix.length();

    // 从右至左扫描中缀表达式
    for (int i = len - 1; i >= 0; i--)
    {
        QChar ch = infix[i];

        if (ch.isDigit() || ch.isLetter())
        {
            // 如果是操作数，则直接加入前缀表达式中
            prefix.append(ch);
        }
        else if (ch == ')')
        {
            // 如果是右括号，则直接压入栈中
            stack.push(ch);
        }
        else if (ch == '(')
        {
            // 如果是左括号，则依次弹出栈顶元素并加入前缀表达式中，直到遇到右括号
            while (!stack.isEmpty() && stack.top() != ')')
            {
                prefix.append(stack.pop());
            }
            stack.pop(); // 弹出右括号
        }
        else
        {
            // 如果是运算符，则依次弹出栈顶元素并加入前缀表达式中，直到栈顶元素的优先级小于等于当前运算符的优先级
            while (!stack.isEmpty() && getPriority(stack.top()) > getPriority(ch))
            {
                prefix.append(stack.pop());
            }
            stack.push(ch); // 将当前运算符压入栈中
        }
    }

    // 将栈中剩余的运算符依次弹出并加入前缀表达式中
    while (!stack.isEmpty())
    {
        prefix.append(stack.pop());
    }

    // 将前缀表达式翻转
    std::reverse(prefix.begin(), prefix.end());

    return prefix;
}

其中，getPriority()函数用于获取运算符的优先级，实现如下：

int getPriority(QChar ch)
{
    if (ch == '+' || ch == '-')
    {
        return 1;
    }
    else if (ch == '*' || ch == '/')
    {
        return 2;
    }
    else
    {
        return 0;
    }
}

使用示例：

QString infix = "1+2*3-(4/2)";
QString prefix = infixToPrefix(infix);
qDebug() << prefix; // 输出：-+1*23/42