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

Question

我没有任何代码的权利，但我只是试图处理我要如何执行这个算法，我只是需要一些想法。

说我有例如字符串：

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

我不希望在所有使用正则表达式这一点，但我试图找出如何使用严格栈操作来做到这一点。我正在考虑可能包括括号，但是我必须考虑双重内部括号。我完全失去了其他想法。

因此，对于这个字符串，我只是想得到如下：

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

任何想法？

Answer 1

该解决方案是基于每个子表达式由括号包围（除，也许，对于整个表达式）的假设。这是调度场算法，它可以解析任意算术表达式的简化：

让我们继续令牌的栈（表示为字符串）。堆栈最初是空的。我们遍历字符串和每个字符，执行以下操作：

1. 如果是右括号，请继续弹出栈的标记，直到找到左括号。连接所有弹出的令牌（包括括号），打印结果并将其推回到堆栈。
2. 否则，只需将令牌推入堆栈。

如果堆栈上的标记数量不是一个，我们需要在算法结束后打印堆栈的内容（它对应于整个表达式没有加上括号的情况）。

这里是它如何工作的例子：

让字符串((A+B)*(C+D))。

我们不断遇到第一个右括号直到令牌推到堆栈。此时，堆栈看起来像[(, (, A, +, B]。我们不断弹出令牌，直到我们点击(。在连接它们之后，我们得到(A+B)并将它推回栈中。现在堆栈的状态是[(, (A+B)]。之后，我们推动令牌直到我们到达下一个)。该堆栈是[(, (A+B), *, (, C, +, D]。弹出后，新表达式为(C+D)，堆栈变为[(, (A+B), *, (C+D)]。最后，我们到达最后的)，并将所有内容都删除并获得整个表达式。

注意：该解决方案假定空间从字符串去除处理的输入之前。

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