前两天室友面试深信服的时候，遇到了个有意思的题目，要求用c或者c++求解如下题目：用户输入一个可以包含加减乘除的数学表达式，你给这个表达式加上任意多的括号，使得这个表达式结果最大。
分析
来看一下这个题目，比如用户输入了如下表达式
那么我们随便加些括号
显然加上括号后比初始的结果要大，我们需要做的就是加些括号使得原始表达式最大。
如果需要比较结果，第一想到的就是枚举出所有的可能性，由于括号个数和位置都是不定的，我们如何编程来找出加上括号的所有可能情况呢？
我们知道一个左括号必然对应一个右括号，且用括号括住一个数是无意义的，比如((3))*2这种的括号就是无意义的，所以就是说一个括号括住至少两个数才是有意义的。看一下式(1.1)，那么我们就可以知道，1的左侧最多有三个有意义的左括号，因为1的右边只有三个数，三个左括号对应三个右括号，1的右侧最多有0个有意义的右括号，因为1左边没有其他数了，同理2的左侧有意义的括号数为2,2的右侧为1,3的左侧为1，右侧为2,5的左侧为0，右侧为3。
我们定义1、2、3、5的左右侧有意义括号数为a0、a1、b0、b1、c0、c1、d0、d1(这里为了方便大家看，定义的很多变量，真正写代码的时候当然是用数组啦)，那么这些量符合如下约束：
那么我们通过求解出符合条件的值即可知道如何添加括号。
求解
显然式(1.3)应该是属于一个整型规划问题，那么lingo、matlab、R、python等等甚至可以通过函数或者可视化工具求解，C则需要自己实现整型规划问题的算法，如何求解整型规划问题网上教程很多，在此不做详解。
总结
上述提出的解法只是自己个人的一点分析，里面得到的括号添加方式是可能有重复的，如((1+2*3+5))最外面的两个括号和一个括号、无括号的情况下是一样的，所以此法并非最优解法，欢迎大家可以提出更好的解法。