c++ - 将缺少的左括号添加到方程中

Question

我一直在为给定问题寻找合适的解决方案，一直在互联网上寻找一些想法。怎么也找不到。

问题是：编写一个程序，从标准输入中获取一个不带左括号的表达式，并打印插入括号的等效中缀表达式。

给定表达式：1 + 2) * 3 - 4)* 5 - 6)))
输出：((1 + 2) * ((3 - 4) * (5 - 6)))

解决这个问题的最佳方法是什么？

Answer 1

我认为目标是假设您只用括号括起来表达式，而不是孤立的数字。

所以你会想要抓住每个令牌并将它们扔到堆栈上

2
+
1

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

下一次推送堆栈看起来像这样

4
-
3
*
(1 + 2)

拉出前三个并放回括号中的堆栈（3-4）*（1+2）

然后再次

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

我们打了另一个括号并再次从堆栈中获取前 3 个，括号内并推回

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

我们抓住另一个括号，再次从堆栈中抓取前 3 个，加上括号并向后推

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

然后再次...

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

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