Python 中的前缀转中缀转换

中缀表达式：中缀表达式中的运算符位于两个操作数之间。操作数本身也可以包含运算符。但相对于中间运算符，表达式就是中缀表达式。

中缀表达式的形式为

示例： (X + Y) * (X1 + Y1)

前缀表达式：前缀表达式中的运算符位于两个操作数之前。操作数本身也可以包含运算符。但相对于开头的运算符，表达式就是前缀表达式。

前缀表达式的形式为

示例： *+ XY - X1Y1 （中缀：(X + Y) * (X1 + Y1)）

任务是：如果我们给定一个前缀表达式，我们需要将其转换为中缀表达式。

计算机被设计为最常以后缀或有时以前缀形式计算表达式。然而，对于我们来说，理解和计算前缀表达式并不容易。我们被训练来解决中缀表达式。因此，我们需要将前缀表达式转换为中缀表达式。

以下是一些示例输入和输出，以便更好地理解当前问题。

示例

输入前缀： *+ XY - X1Y1

输出中缀： ((X + Y) * (X1 + Y1))

输入前缀： *+ P / QR -/ STU

输出中缀： ((P - (Q / R)) * ((P / T) - U))

前缀转中缀转换算法

1. 首先，我们将以反向顺序读取给定的前缀表达式，即从右到左。
2. 我们将使用一个栈来存储操作数。因此，如果我们遇到一个符号，我们将将其压入栈中。
3. 如果我们遇到一个运算符，那么我们将从栈中弹出两个操作数。
4. 最后，我们将创建两个操作数和运算符的 Python 字符串连接，并将运算符放在它们之间。
5. infix = (operand_1 + operator + operand_2)
6. 然后我们将转换后的中缀字符串推回栈中。
7. 我们将重复上述步骤，直到到达给定前缀表达式的末尾。
8. 执行结束时，我们将只剩下一个中缀表达式字符串。

代码

输出

The infix string is: ((P+(Q/R))*((S/T)-U))

时间复杂度：此算法的时间复杂度为 O(n)，其中 n 是给定前缀字符串的长度。

辅助空间：由于我们将字符串的符号存储在栈中，因此该程序占用 O(n) 的内存空间。