前缀表达式到后缀表达式的转换

什么是后缀表达式？

后缀表达式是指操作符出现在操作数之后的表达式。它可以写成

(操作数) (操作数) (操作符)

例如

如果表达式是

(A+B) * (C+D)

首先，操作符优先级规则将应用于上述表达式。由于括号的优先级高于乘法操作符；因此，'+' 将首先被解析，'+' 操作符将出现在 AB 和 CD 之后，如下所示

(AB+) * (CD+)

现在，乘法操作符将移动到 CD+ 之后，如下所示

AB+ CD+*

什么是前缀表达式？

前缀表达式是指操作符出现在操作数之前的表达式。

例如

如果表达式给出为

(A+B) * (C+D)

首先，操作符优先级规则将应用于上述表达式。由于括号的优先级高于乘法操作符；因此，'+' 操作符将首先被解析，'+' 操作符将移动到操作数 AB 和 CD 之前，如下所示

(+AB) * (+CD)

现在，乘法操作符将移动到 +AB 之前，如下所示

*+AB+CD

前缀表达式到后缀表达式的转换

有两种方法可以将后缀表达式转换为前缀表达式

1. 手动将后缀表达式转换为前缀表达式。
2. 使用堆栈将后缀表达式转换为前缀表达式。

手动将后缀表达式转换为前缀表达式

以下是将后缀表达式转换为前缀表达式所需的步骤

• 从左到右扫描后缀表达式。
• 从表达式中选择前两个操作数，后跟一个操作符。
• 将其转换为前缀格式。
• 用一个临时变量替换前缀子表达式
• 重复此过程，直到整个后缀表达式转换为前缀表达式。

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

a b - c +

首先，我们从左到右扫描表达式。我们将 '-' 操作符移动到操作数 ab 之前。

-abc+

下一个操作符 '+' 被移动到操作数 -abc 之前，如下所示

+-abc

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

以下是将后缀表达式转换为前缀表达式使用的步骤

• 从左到右扫描后缀表达式。
• 如果元素是操作数，则将其压入堆栈。
• 如果元素是操作符，则从堆栈中弹出两个操作数。

通过连接两个操作数并将操作符添加到操作数之前来创建一个表达式。

将结果推回堆栈。

• 重复以上步骤，直到到达后缀表达式的末尾。

后缀转前缀的伪代码

让我们通过堆栈来理解后缀转前缀的转换。

如果后缀表达式是

AB + CD - *

上述后缀表达式的前缀表达式是 *+AB-CD。

C++ 中后缀转前缀的实现

输出