meh*_*ix_ 2 c++ algorithm stack
我一直在寻找适合某个特定问题的解决方案,一直在互联网上寻找一些想法.无法找到任何.
问题是:编写一个程序,从标准输入中获取一个没有左括号的表达式,并打印插入括号的等效中缀表达式.
给定表达式:1 + 2) * 3 - 4)* 5 - 6)))
输出:((1 + 2) * ((3 - 4) * (5 - 6)))
什么是解决这个问题的最佳方法？
小智 9
我认为目标是假设你只是表达式括号,而不是单独的数字.
因此,您需要抓住每个令牌并将它们扔到堆栈上
2
+
1
抓住下一个标记,这是现在占据堆栈的前三个并将其夹在那些parens(1 + 2)之间,将其作为一个表达式放回堆栈.
下一次推送堆栈看起来像这样
4
-
3
*
(1 + 2)
拔出前三名并将其放回堆叠括号内(3-4)*(1 + 2)
然后再次
6
-
5
*
(3-4)
*
(1+2)
我们击中另一个paren并再次从筹码中抢到前3名,括号并推回
(5-6)
*
(3-4)
*
(1+2)
我们抓住另一个paren,再次从筹码中抢到前3名,括号并推回
((3-4)*(5-6))
*
(1+2)
然后再次...
((1 + 2) * ((3 - 4) * (5 - 6)))
没有更多的输入,所以这是我们的答案