java - 使用堆栈获取逻辑子表达式

Question

我现在没有任何代码，但我只是在尝试处理我将如何执行这个算法，我只需要一些想法。

例如，假设我有字符串:

((A+B)*(C+B)) * (A+C)

我根本不想为此使用正则表达式，但我正在尝试弄清楚如何使用严格的 Stack 操作来做到这一点。我在考虑也许计算括号，但后来我必须考虑双内括号。我完全失去了其他想法。

所以对于这个字符串，我只想导出以下内容:

A+B
C+B
(A+B)*(C+B)
A+C
((A+B)*(C+B)) * (A+C)      // The original String

有什么想法吗？

Answer 1

此解决方案基于这样一个假设，即每个子表达式都被括号括起来(可能除了整个表达式)。调车场算法的简化，可以解析任意算术表达式:

让我们保留一堆标记(表示为字符串)。堆栈最初是空的。我们遍历字符串并为每个字符执行以下操作:

1. 如果它是一个右括号，则继续弹出堆栈的标记，直到找到一个左括号。连接所有弹出的标记(包括括号)，打印结果并将其推回堆栈。
2. 否则只需将 token 压入堆栈即可。

如果栈中的token个数不是一个，我们需要在算法结束后打印出栈中的内容(对应整个表达式没有括号的情况)。

这是它如何工作的一个例子:

设字符串为((A+B)*(C+D)) .

我们一直将 token 压入堆栈，直到遇到第一个右括号。那时，堆栈看起来像 [(, (, A, +, B ].我们不断弹出 token ，直到我们达到 ( .连接它们后，我们得到 (A+B)并将其推回堆栈。栈的状态是[(, (A+B)]现在。之后，我们推送 token 直到到达下一个 )。 .堆栈是 [(, (A+B), *, (, C, +, D] .弹出后，新表达式为(C+D)堆栈变为 [(, (A+B), *, (C+D)] .最后，我们到达最后一个 )然后弹出所有内容并获得整个表达式。

注意:此解决方案假定在处理输入之前从字符串中删除了空格。

顺便说一句，你不能用正则表达式解决这个问题，因为我们在这个问题中处理的语言不是正则的。