Java 中的 Shunting Yard 算法

Shunting-yard 算法是计算机科学中一种常用的算法，用于将中缀表达式转换为后缀或前缀表达式。在后缀表示法（也称为逆波兰表示法，RPN）中，运算符位于操作数之后；而在前缀表示法（也称为波兰表示法）中，运算符位于操作数之前。Shunting-yard 算法由 Edsger Dijkstra 于 1961 年发明。Shunting-yard 算法的工作原理如下：

• 创建两个栈，一个用于存放运算符，一个用于存放输出。
• 从左到右读取中缀表达式中的每个标记。
• 如果标记是数字，则将其添加到输出栈。
• 如果标记是运算符，则：
• 当运算符栈中有运算符，且栈顶运算符的优先级大于或等于当前运算符的优先级时，将栈顶运算符弹出并添加到输出栈。
• 将当前运算符压入运算符栈。
• 如果标记是左括号，则将其压入运算符栈。
• 如果标记是右括号，则从运算符栈中弹出运算符并添加到输出栈，直到找到左括号。丢弃左括号。
• 读取完所有标记后，将运算符栈中剩余的所有运算符弹出并添加到输出栈。

让我们用 Java 实现 Shunting-yard 算法。

ShuntingYard.java

输出

Infix expression: 3+4*2/(1-5)^2
Postfix expression: 342*15-2^/+

注意：在此示例中，我们实现了 Shunting-yard 算法，将中缀表达式 "3+4*2/(1-5)^2" 转换为后缀表示法。

• 该算法之所以命名为“Shunting Yard”（调车场），是因为它最初是使用铁路调车场实现的，调车场是用于在铁路枢纽中对火车进行分类和重新组织的系统。
• Shunting-yard 算法是栈式算法的一个经典示例，我们使用栈来跟踪表达式中的运算符和操作数。
• 该算法效率很高，时间复杂度为 O(n)，其中 n 是输入表达式的长度。
• Shunting-yard 算法可用于将中缀表达式转换为后缀或前缀表示法，具体取决于运算符和操作数的排列顺序。
• 后缀表示法对于高效评估表达式非常有用，因为它消除了对括号和运算符优先级规则的需求。
• 前缀表示法在某些情况下也很有用，尤其是在函数式编程中，它用于将表达式定义为一系列嵌套的函数调用。
• Shunting-yard 算法可以处理多个相同优先级的运算符，并确保它们根据其结合性（从左到右或从右到左）以正确的顺序进行评估。
• 该算法还可以处理一元运算符，即作用于单个操作数的运算符，例如取反 (-) 运算符。
• Shunting-yard 算法可以扩展以处理更复杂的表达式，例如带有函数、变量和数组的表达式。
• Shunting-yard 算法的一个关键优点是它可以处理任意复杂度的表达式，包括带有嵌套括号和多级运算符优先级的表达式。
• Shunting-yard 算法的另一个优点是它可以相对轻松地扩展以支持新的运算符和函数。
• Shunting-yard 算法基于将中缀表达式转换为后缀或前缀表示法的思想，然后可以使用基于栈的方法进行评估。这包括从左到右扫描输入表达式，并使用栈来跟踪遇到的运算符和操作数。
• Shunting-yard 算法的关键步骤之一是根据其优先级和结合性将运算符“调入”栈的过程。这包括将当前运算符与栈顶运算符进行比较，并根据运算符的相对优先级和结合性将当前运算符压入栈或从栈中弹出栈顶运算符。
• Shunting-yard 算法的另一个重要步骤是处理括号的过程。这涉及使用单独的栈来跟踪表达式中的开括号和闭括号，并从运算符栈中弹出运算符，直到遇到相应的开括号。
• 除了用于将中缀表达式转换为后缀或前缀表示法外，Shunting-yard 算法还可以用于其他任务，例如直接评估算术表达式、检查表达式的有效性以及为编程语言中的表达式评估生成代码。
• Shunting-yard 算法提供了一种无需嵌套括号或显式运算符优先级规则即可评估算术表达式的方法。这使得阅读和理解复杂表达式更加容易，并有助于减少出错的可能性。
• Shunting-yard 算法常用于计算机编程，特别是在编程语言的编译器和解释器中。通过将表达式转换为后缀或前缀表示法，可以更轻松地在运行时生成机器代码或解释代码。
• Shunting-yard 算法还可以用于计算机科学和工程的其他领域，例如机器人技术、信号处理和控制系统。在这些应用中，它通常用于评估复杂的数学表达式或为实时系统生成代码。
• Shunting-yard 算法的一个局限性是它不能处理所有类型的表达式。
• Shunting-yard 算法还可以用于将后缀表达式转换回中缀表示法。这涉及使用栈来跟踪遇到的操作数和运算符，并自底向上构建中缀表达式。
• Shunting-yard 算法由 Edsger W. Dijkstra 于 1961 年首次提出，此后成为栈式算法的经典示例。它至今仍在各种应用中广泛使用，并已通过多种方式进行扩展和修改，以支持新型表达式和问题域。
• Shunting-yard 算法可以修改以处理不同类型的运算符和操作数，例如按位运算符或复数。这涉及扩展算法以处理额外的解析和评估步骤，并可能需要修改过程中使用的数据结构和算法。
• Shunting-yard 算法的另一个变体是逆波兰表示法（RPN）算法，它与 Shunting-yard 算法中使用的后缀表示法相似，但解析和评估过程略有不同。在 RPN 中，运算符位于其操作数之后，而不是之前，并且不需要括号或运算符优先级规则。
• Shunting-yard 算法还可以用于解析和评估布尔表达式，方法是使用 AND、OR 和 NOT 等逻辑运算符。这涉及扩展算法以处理布尔操作数和运算符，并可能需要额外的评估规则和数据结构。
• 在某些情况下，Shunting-yard 算法可能不如其他解析和评估方法（如递归下降解析或运算符优先级解析）高效。这是因为它需要更多的栈操作，并且处理括号和运算符优先级规则的开销更高。

总的来说，Shunting-yard 算法是处理数学表达式的强大而灵活的工具，为开发更高级的解析和评估方法提供了坚实的基础。通过理解 Shunting-yard 算法背后的原理和技术，开发人员和工程师可以深入了解表达式解析和评估的本质，并为各种应用开发更有效和高效的算法。