波兰语和逆波兰语表示法

引言

在开始讨论波兰表示法和逆波兰表示法之前，我们必须了解为什么需要编写这两种表达式。

表示法类型

数据结构中存在三种类型的波兰表示法

• 中缀表示法
• 前缀表示法
• 后缀表示法

数学中常用的表达式是中缀表示法，它在计算机进行求值时会遇到困难。

• 在中缀表示法中，每个运算符都写在操作数之间。例如：P * Q + R * S 是以中缀表示法编写的算术表达式，其中 * 表示乘法。在这个表达式中，P 和 Q 是两个操作数，* 是一个运算符，类似地，R 和 S 是两个操作数，* 是一个运算符。

不同运算符的优先级顺序如下

1. 指数的优先级为一。
2. 乘法和除法的优先级为二。
3. 加法和减法的优先级为三。

从这个例子中我们看到，在求值中缀表示法中的算术表达式时，需要从两端扫描表达式。这对于计算机来说是评估中缀表示法编写的表达式的困难任务。因此，为了克服这个问题，波兰数学家“Lukasiewicz”建议算术表达式可以用前缀表示法编写，这种表示法被称为波兰表示法。

波兰表示法

波兰表示法也称为前缀表示法，它是一种以不同算术表达式形式表示表达式的方法。前缀表示法意味着运算符写在操作数之前。

这种表示法由波兰数学家 Lukasiewicz 设计。算术表达式主要由两部分组成，即操作数和运算符。

• 操作数是数字或变量，可以用数字代替以求值表达式。
• 运算符是表示要在表达式中存在的操作数之间执行的操作的符号。

通常，人类发现中缀波兰表示法比后缀或逆波兰表示法更容易理解。将每个表达式从中缀转换为后缀。每个运算符都有其在表达式中的优先级。例如，如果我们取一些运算符，即+、-、*、/，那么它们将按优先级排列。

• 高优先级运算符 *, /, %
• 低优先级运算符+, -
• 运算符顺序：+、-、*、/、^

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

算法

1. 在给定表达式的中缀波兰表示法的末尾添加“)”并将“(”压入栈中。
2. 将整个表达式从后向前按顺序反转。
3. 然后按照下面给出的步骤进行操作
   1. 如果找到“(”，则将元素压入栈中。每当我们遇到操作数（即变量或数字）时，我们都会将其添加到前缀或波兰表示法中。
   2. 如果遇到“)”，我们通过从栈中弹出元素直到“(”是弹出的元素，将这些元素添加到前缀表达式中。随后，从栈中移除“(”并避免将其添加到前缀表达式中。
   3. 如果找到运算符“*”，则重复从栈中移除它，并将所有优先级与运算符“*”相同或更高​​的运算符添加到前缀表达式中。
4. 然后将栈中创建的最终表达式反转，以撤消第二步以获得最终答案。

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

算法

1. 在给定表达式的中缀波兰表示法的末尾添加“)”并将“(”压入栈中。
2. 对于中缀波兰表示法中包含的每个元素，请再次遵循下面列出的步骤。
   1. 如果找到“(”，则将元素压入栈中。每当我们遇到操作数（即变量或数字）时，我们都会将其添加到后缀或逆波兰表示法中。
   2. 如果遇到“)”，我们通过从栈中弹出元素直到“(”是弹出的元素，将这些元素添加到后缀表达式中。随后，从栈中移除“(”并避免将其添加到后缀表达式中。
   3. 如果找到运算符“x”，则重复从栈中移除它，并将所有优先级与运算符“x”相同或更高​​的运算符添加到后缀表达式中。
3. 在对每个元素完成步骤 2 后，所有元素将从栈中移除并添加到后缀表达式中。

这是给定表示法的最终表达式，这些算法进一步用于解决数值问题。