将中缀表达式转换为前缀表达式

什么是中缀表达式？

中缀表达式是一种以通常或正常格式书写的表达式。在这种表示法中，运算符位于操作数之间。中缀表达式的示例有 A+B、A*B、A/B 等。

正如我们在上面的示例中看到的，所有运算符都存在于操作数之间，因此它们是中缀表达式。因此，中缀表达式的语法可以写为

<操作数> <运算符> <操作数>

解析中缀表达式

为了解析任何表达式，我们需要注意两件事，即运算符优先级和结合性。运算符优先级是指任何运算符相对于另一个运算符的优先级。例如

A + B * C → A + (B * C)

由于乘法运算符的优先级高于加法运算符，因此 B * C 表达式将首先计算。B * C 的乘法结果将加到 A 上。

优先级顺序

结合性是指当表达式中存在相同优先级的运算符时。例如，在表达式 A + B - C 中，'+' 和 '-' 运算符具有相同的优先级，因此它们借助结合性进行评估。由于 '+' 和 '-' 都是左结合的，它们将被评估为 (A + B) - C。

结合性顺序

让我们通过一个例子来理解结合性。

1 + 2*3 + 30/5

由于在上述表达式中，* 和 / 具有相同的优先级，因此我们将应用结合性规则。正如我们在上表中观察到的，* 和 / 运算符具有从左到右的结合性，因此我们将从最左边的运算符开始扫描。先出现的运算符将首先被评估。运算符 * 出现在 / 运算符之前，乘法将首先完成。

1+ (2*3) + (30/5)

1+6+6 = 13

什么是前缀表达式？

前缀表达式是另一种表达式形式，但它不需要优先级和结合性等其他信息，而中缀表达式需要优先级和结合性信息。它也称为波兰表示法。在前缀表达式中，运算符位于操作数之前。前缀表达式的语法如下

<运算符> <操作数> <操作数>

例如，如果中缀表达式是 5+1，则与此中缀表达式对应的前缀表达式是 +51。

如果中缀表达式是

a * b + c

↓

*ab+c

↓

+*abc（前缀表达式）

考虑另一个例子

A + B * C

第一次扫描：在上述表达式中，乘法运算符的优先级高于加法运算符；B*C 的前缀表达式将是 (*BC)。

A + *BC

第二次扫描：在第二次扫描中，前缀将是

+A *BC

在上述表达式中，我们使用两次扫描将中缀表达式转换为前缀表达式。如果表达式复杂，则需要更多的扫描次数。我们需要使用只需要一次扫描并提供所需结果的方法。如果通过一次扫描获得所需输出，则算法将是高效的。这只有通过使用栈才能实现。

使用栈将中缀表达式转换为前缀表达式

K + L - M * N + (O^P) * W/U/V * T + Q

如果我们将表达式从中缀转换为前缀，我们需要首先反转表达式。

反转表达式将是

Q + T * V/U/W * ) P^O(+ N*M - L + K

为了获得前缀表达式，我们创建了一个包含三列的表格，即输入表达式、栈和前缀表达式。当我们遇到任何符号时，我们只需将其添加到前缀表达式中。如果遇到运算符，我们将其压入栈中。

上述表达式，即 QTVUWPO^*//*NM*LK+-++，不是最终表达式。我们需要反转此表达式以获得前缀表达式。

中缀表达式转换为前缀表达式的规则

• 首先，反转问题中给出的中缀表达式。
• 从左到右扫描表达式。
• 当操作数到达时，打印它们。
• 如果运算符到达且栈为空，则只需将运算符压入栈中。
• 如果传入运算符的优先级高于栈顶运算符，则将传入运算符压入栈中。
• 如果传入运算符的优先级与栈顶运算符相同，则将传入运算符压入栈中。
• 如果传入运算符的优先级低于栈顶运算符，则弹出并打印栈顶运算符。再次将传入运算符与栈顶运算符进行比较，并从栈中弹出运算符，直到找到优先级较低或相同优先级的运算符。
• 如果传入运算符的优先级与栈顶运算符相同且传入运算符是 ^，则弹出栈顶运算符，直到条件为真。如果条件不为真，则压入 ^ 运算符。
• 当到达表达式末尾时，弹出并打印栈顶所有运算符。
• 如果运算符是 ')'，则将其压入栈中。
• 如果运算符是 '('，则从栈中弹出所有运算符，直到在栈中找到 ')' 左括号。
• 如果栈顶是 ')'，则将运算符压入栈中。
• 最后，反转输出。

中缀表达式转换为前缀表达式的伪代码