在等式中加上缺失的左括号

Question

我在寻找一个合适的解决方案，但是一直没有找到什么好的想法。问题是：编写一个程序，从标准输入中获取没有左括号的表达式，并打印出插入括号后的等价中缀表达式。给定的表达式为：1 + 2) * 3 - 4)* 5 - 6)))，输出结果应该为：((1 + 2) * ((3 - 4) * (5 - 6)))。如何解决这个问题呢？

- mehdix_

---

你怎么知道它不应该是1 + ((2) * 3 - ((4)* 5 - (6)))？ - lc.

你是否只想在前一个右括号后添加左括号？ - jab

@lc，因为输出格式已经作为答案给出。 - mehdix_

@mehdix_ 这与格式无关，这是完全不同的解释。就目前而言，这个问题是不完整的，也无法回答。 - us2012

@jab，那样做会很容易！但我认为那行不通。该算法应该能够解析输入，评估缺失的括号对。 - mehdix_

@us2012，不幸的是，这本书现在被很多计算机科学专业使用。 - mehdix_

Answer 1

我认为这个目标是假设你只对表达式进行括号，而不对单独的数字进行括号。

因此，您需要获取每个令牌并将它们放入堆栈中。

2
+
1

获取下一个标记，即 )， 现在从栈中取出前三个并将它们夹在这些括号之间（1 + 2），将其作为一个表达式放回到栈中。

下一步将推送的堆栈看起来像这样

4
-
3
*
(1 + 2)

将前三个元素弹出，加上括号重新放回栈中

(3-4) * (1+2)

再次执行相同的操作。

6
-
5
*
(3-4)
*
(1+2)

我们遇到另一个括号，再次从堆栈中获取前三个元素，添加括号后再将它们推回去。

(5-6)
*
(3-4)
*
(1+2)

我们获取另一个括号，再次从栈顶获取前3个元素，加上括号后再放回去。

((3-4)*(5-6))
*
(1+2)

再一次...

((1 + 2) * ((3 - 4) * (5 - 6)))

没有更多的输入，所以这就是我们的答案

- agoaj

---

太棒了，这就是正确的方式。你真的帮了大忙@agoaj。 - mehdix_

因为最后一个括号没有平衡，所以出现了错误。 - TheM00s3