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

在理解前缀表达式到后缀表达式的转换之前，我们应该分别了解前缀表达式和后缀表达式。

什么是前缀转换？

中缀表达式是运算符写在两个操作数之间的表达式。如果我们把运算符移到操作数前面，就称为前缀表达式。换句话说，前缀表达式可以定义为所有运算符都放在两个操作数之前的表达式。

例如

如果给定的中缀表达式是：A + B * C

我们知道乘法运算符 * 的优先级高于加法运算符。首先，乘法运算符将移到操作数 B 之前，如下所示

A + * B C

一旦乘法运算符移到操作数 'B' 之前，加法运算符将移到操作数 'A' 之前，如下所示

+ A * B C

使用堆栈求前缀表达式的值

步骤 1：初始化一个指向表达式末尾的指针 'S'。

步骤 2：如果 'S' 指向的符号是操作数，则将其压入堆栈。

步骤 3：如果 'S' 指向的符号是运算符，则从堆栈中弹出两个操作数。对这两个操作数执行运算，并将结果存储在堆栈中。

步骤 4：将指针 'S' 减 1，然后返回步骤 2，直到表达式中还有剩余符号。

步骤 5：最终结果存储在堆栈的顶部并返回。

步骤 6：结束

让我们通过一个例子来理解前缀表达式的求值。

表达式：+, -, *, 2, 2, /, 16, 8, 5

首先，我们将上面的表达式反转。

表达式：5, 8, 16, /, 2, 2, *, -, +

我们将使用堆栈数据结构来求前缀表达式的值。

上面表达式的最终结果是 7。

什么是后缀表达式？

如果我们把运算符移到操作数后面，就称为后缀表达式。换句话说，后缀表达式可以定义为所有运算符都放在操作数后面的表达式。

例如

如果中缀表达式是 A + B * C

我们知道乘法运算符的优先级高于加法运算符，所以乘法运算符将移到操作数 B 和 C 之后，如下所示

A + B C *

一旦乘法运算符移到操作数 C 之后，加法运算符将移到乘法运算符之后，如下所示

A B C * +

使用堆栈求后缀表达式的值

使用堆栈求后缀表达式的算法

步骤 1：创建一个空的堆栈，用于存储操作数。

步骤 2：逐个扫描表达式的每个元素并执行以下操作

• 如果元素是操作数，则将其压入堆栈。
• 如果元素是运算符，则从堆栈中弹出两个操作数。对这些操作数执行运算。将最终结果压入堆栈。

步骤 3：当表达式完全扫描完毕时，堆栈中可用的值将是给定表达式的最终输出。

让我们通过一个例子来理解使用堆栈求后缀表达式的值。

如果表达式是：5, 6, 2, +, *, 12, 4, /, -

上面表达式的结果是 37。

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

在这里，我们将使用堆栈数据结构来查看前缀表达式到后缀表达式的转换。

使用堆栈数据结构进行前缀到后缀表达式转换的规则

• 从右到左扫描前缀表达式，即反转。
• 如果传入的符号是操作数，则将其压入堆栈。
• 如果传入的符号是运算符，则从堆栈中弹出两个操作数。一旦从堆栈中弹出操作数，我们就在操作数之后添加传入的符号。当运算符添加到操作数之后时，该表达式将被推回堆栈。
• 整个表达式扫描完毕后，从堆栈中弹出并打印后缀表达式。

前缀到后缀转换的伪代码

让我们通过一个例子来理解使用堆栈将前缀表达式转换为后缀表达式。

如果表达式是：* - A / B C - / A K L