后缀表达式求值

后缀表达式

表示代数表达式的一般数学方法是将运算符写在操作数之间：示例：a + b。这种表示称为中缀表示法。如果我们把运算符写在操作数之后，示例：a b +，则称为后缀表示法。它也称为“逆波兰表示法”。

为什么使用后缀表达式？

用后缀表达式表示代数表达式可以消除括号并避免考虑优先级。求值变得简单。它是计算机使用堆栈求值复杂代数表达式的理想表示法。有许多算法用于将中缀表示法转换为后缀表示法。本文将解释 Dijkstra 算法，然后我们还将学习如何用 Python 代码对转换和求值这两种情况进行后缀表达式求值。

将中缀表达式转换为后缀表达式的步骤

1. 从左到右读取给定的表达式。如果扫描到的元素是操作数，则直接将其追加到结果后缀表达式中。
2. 如果扫描到的元素是运算符且堆栈为空，则将运算符推入堆栈。
3. 如果扫描到的元素是运算符，且该运算符的优先级大于或等于堆栈顶部的运算符的优先级，则将其推入堆栈。
4. 如果扫描到的元素是运算符，且该运算符的优先级小于堆栈顶部的运算符的优先级，则弹出堆栈顶部的运算符并将其添加到后缀表达式中，直到堆栈为空或堆栈顶部的运算符的优先级小于扫描到的运算符的优先级。现在，将扫描到的运算符推入堆栈。

例如: 3 + 8 - 9 / 8

• 请注意，操作数的顺序将保持不变，只有运算符的顺序从中缀表示法变为后缀表示法。

Python 代码

输出

Enter the infix notation separated by space: 3 + 8 - 9 / 8
38+98/-

说明

1. 系统提示用户输入一个以空格分隔的中缀表达式。
2. 定义了 precedence() 函数，用于为每个运算符分配优先级级别。优先级级别较高的运算符首先进行求值。
3. 使用 split() 函数将输入表达式拆分为一个标记列表。
4. 初始化一个空字符串 postfix 和一个列表 opstack。
5. 程序遍历输入列表中的每个标记。
6. 如果标记是运算符，则程序检查该运算符的优先级级别。
   1. 如果运算符的优先级级别高于 opstack 列表中的前一个运算符，则将其添加到 opstack 列表。
   2. 否则，将前一个运算符从 opstack 列表中移除并添加到 postfix 字符串。此过程继续进行，直到该运算符可以添加到 opstack 列表中。
7. 如果标记是空格，则忽略它。
8. 如果标记不是运算符或空格，则将其添加到 postfix 字符串。
9. 处理完所有标记后，opstack 列表中剩余的运算符将添加到 postfix 字符串中。
10. 最终的后缀表达式将打印到控制台。

后缀表达式求值

让我们通过一个例子来理解这个概念，以便清晰地了解堆栈操作。

示例

以上面转换的后缀表达式为例。首先让我们从中缀表达式中得到结果

3 + 8 - 9 / 8

= 3 + 8 - 1.125

= 11 - 1.125

= 9.875

• 求值顺序：科学计算器 (BODMAS)

现在，让我们以前面转换得到的后缀表达式为例

3 8 + 9 8 / -

1. 从左到右读取表达式，初始化一个与表达式长度相同的堆栈。
2. 如果遇到的元素是操作数，则将其推入堆栈。
3. 如果遇到的元素是运算符，则从堆栈中弹出两个操作数 a 和 b，应用运算符 (b 运算符 a)，并将结果推回堆栈。
4. 在上面的例子中：3 8 + 9 8 / -

3 8
+
9 8
/
-

Python 程序

输出

Enter the postfix expression: 3 8 + 9 8 / -
The result of the expression:  9.875        

说明

1. 使用 split() 函数将输入表达式拆分为一个标记列表。
2. 初始化一个空列表 stack。程序遍历输入列表中的每个标记。
3. 如果标记是运算符，则程序从堆栈中弹出顶部两个值，执行相应的算术运算，并将结果推回堆栈。
4. 如果标记是空格，则忽略它。
5. 如果标记不是运算符或空格，则将其转换为整数并推入堆栈。
6. 处理完所有标记后，最终结果是堆栈中唯一剩余的元素。这将被打印到控制台。