算术表达式括号补全问题分析

问题描述

    假定我们有一个数学表达式，我们把里面所有的左括号都去掉了，比如说：1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )。我们需要找到一个方法将缺失的这部分左括号补全使得它成为一个完整正确的表达式。对应于前面的示例，它对应的完整的数学表达式为：( ( 1 + 2 ) * ( ( 3 - 4 ) * ( 5 - 6 ) ) )。这里的有一个要求是所有表达式必须是用括号包含的，但是又不包含冗余的。

 

问题分析

    粗看这个问题的时候，有点不知道从哪里下手。因为对于一个表达式来说，比如前面的1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )。因为我们这里不考虑对单独的数字用一组括号包含起来。所以不存在如(1)这样的情况。 所以这里第一个关键的点就是，我们里面所有括号里包含的表达式必然是一个(a op b)这种样式。这里假设a和b是一个子表达式， 而op表示一个运算符。对于比如((1 + 2) * (3 + 4))这样的表达式来说，它也相当于我们前面的一种表达式。不过光从这一点来分析的话，我们似乎还是没有多少线索。看来还需要进一步的分析。

 

歧义分析

    最开始要找这些个匹配的括号时，最让人困惑的地方就是，感觉似乎有很多种可能。然后就没法确定了。比如说，在我们前面的表达式里，我们既可以组织表达式成( ( 1 + 2 ) * (3 - 4) )， 也可以组织成(1 + (2 * ( 3 - 4) ) ) 这种。这样，当我们读取到某个操作符后面的数字时，就不知道该将这个数字包含到哪个部分。这部分解读看似有点道理，但是我们还忽略了一个地方。就是对于我们要找到的符号匹配，我们虽然没有了左括号，可是我们是有右括号的。在前面的示例中，虽然我们组成的表达式不一样，但是它们右括号的数量不一样。也就是说，采用不一样数目的右括号，才能对应不同的表达式。至此，我们可以推断，右括号的布局和数量其实在某种程度上已经确定了这个表达式。

    我们现在再来看一个简单的示例：比如说1 + 2 * 3。 我们将他们组合成这种表达式：((1 + 2) * 3) 也可以组合成这种表达式：((1 + (2 * 3))。 在这里，我们组合的方式不一样，但是右括号的位置和数量也有差别。在前面这种情况下，我们的两个右括号一个是在2的右边，一个是在3的右边。而后面这种则是两个都在3的后边。可见，在这里我们至少可以确定右括号的位置和数量不同它们就确定了唯一不同的表达式结构。现在的问题是，就算我们知道它们不同，有什么办法把这个表达式的完整结构给整出来呢？

 

进一步分析

    我们知道对于一个表达式来说，因为我们这里采取用括号来包括他们的结构和运算关系，他们可以笼统的概括成一个(a op b)的这种样式。这样就形成了一个递归定义的结构。而如果我们对编译原理的一些概念还有点印象的话，会想到抽象语法树这个东西。比如说a + b 则可以形成一个以+为根而分别以a, b为左右子节点的二叉树。那么，以我们前面列举的表达式( ( 1 + 2 ) * ( ( 3 - 4 ) * ( 5 - 6 ) ) )为例，它对应的构造语法树会是个什么样子呢？ 我们一步步的把它构建出来：

    首先，它既然是一个(a op b)这种结构。那么当我们把最外面那一层括号剥除的时候，它对应的应该是(1 + 2) * ((3- 4) * (5 - 6)) ，其中a对应(1 + 2)， op操作符对应 *， b对应((3-4) * (5 - 6))。 它对应的语法树结构如下：

    我们可以进一步的展开(1 + 2)，它既然也应该对应(a op b)这种结构，那么a= 1, b = 2, op = +：

    右边的子节点也按照这种方式展开：

    最后的结果将如下图：

 

     刚才这个过程展示了两点。一个就是我们每展开一个节点的时候，相当于去掉了一层括号。另外就是每个节点最终是一个数字或者两个数字和一个计算符号的组合。我们回顾一下刚才这个展开的过程。每次我们要去掉一组括号，对应的这个括号里就必然包含这一个计算表达式加上一个运算符再加上一个表达式。我们这样不断的去掉括号，不断的构造出来了这个表达式树。

    而如果我们把前面的这个过程倒过来呢？我们每次不断的合并一个表达式加上一个元算符再加上一个表达式，然后把他们加上括号，这里不就构造出我们原来的这个大的数学表达式了吗？没错，这一步是确定的。可是如果我们要这样做的话，这里是要求前面的左右括号都有。而我们这里是去掉了左括号。不过没关系，因为我们既然有了右括号，我们就知道，对于一个完整的表达式来说，它至少应该保证它的左右括号数量是一样的。所以对于一个右括号来说，当我们从左到右遍历，碰到第一个右括号时，它必然是构成一个最小表达式的一部分。而如果要构成一个最小的表达式来说，无非就是像1 + 2, 2 * 3等这样的形式。对于这种1 + 2 )，或者 2 * 3 )，我们很显然，只要将它前面的两个数字和符号组合起来，再在左边加上左括号就可以了。

     前面的这一步，相当于构造了一个表达式，它本身也将作为另外一个大的表达式的一部分。我们按照类似递归的概念。既然这个右括号它所涵盖的这部分，比如(1 + 2)是一个表达式，这个时候，如果我们将它作为一个整体，在后面再碰到右括号的时候，我们是不是同样也可以把它当作第一个右括号那样来使用呢？比如说，我们前面的表达式((1 + 2) * 3)，在去掉左括号的时候它是1 + 2) * 3。按照刚才的思路，我们应该是组合( 1 + 2 )， 然后我们碰到运算符号* 和数字3。接着我们又碰到右括号，这个时候类似，我们将右括号前面的两个运算表达式和运算符组合起来，这就是((1 + 2) * 3)。我们再看((1 + (2 * 3)) 这个。它去掉左括号则是1 + 2 * 3))。我们在碰到第一个右括号的时候，组合的第一个表达式是(2 * 3)，然后再碰到另外一个右括号，这个时候再组合，就有(1 + (2 * 3))。 

    哈哈，看来到了这一步，我们找到了一个构造表达式的规律了。无非就是每次我们碰到一个右括号的时候，将这个右括号左边的两个表达式和一个运算符组合成一个表达式。这样不断循环到最后。

 

实现 

    从前面的讨论里，我们就已经知道一个最终解析的方法了。就是通过碰到一个右括号，然后将它前面的部分组合起来构成新的表达式。这个新的表达式也将作为一个子节点参与到后面的组合中。那么，从实现的角度来说，我们可以发现如果用栈来解决这个问题简直就是最理想的方法。因为每次都要取前面的结果，而这些结果是对应每个右括号最接近的，这不就是对应着栈的LIFO吗？假设我们用栈来解析前面的表达式1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )，那么该是个什么样的过程呢？

    我们将这个过程的图示标注下来：

         首先，我们碰到1, +, 2， 那么这3个元素依次入栈。如下图：

    

 

    这个时候，我们碰到第一个右括号，我们需要将栈里的两个表达式和一个运算符取出来，然后组成(1 + 2)，然后将这个组合的表达式入栈：

    然后我们将* 3 - 4这部分入栈：

     这个时候我们又碰到一个右括号，老规矩，弹出前面的两个表达式和一个运算符，则有(3 - 4)，再将它入栈：

     接着是后面的* 5 - 6:

     然后我们后面有3个有括号，我们一个个的来处理：

     第二个右括号：

     最后一个：

 

    在上面的每次调整的过程中，我们将前面压在栈底的3个元素都弹出来，然后组织的时候是后面弹出的元素放在前面，然后再包装一层括号，再入栈。这就是我们每次弹栈后做的事情。这样最后栈顶剩下的那个元素就是我们拼装出来的结果。

    有了前面的这个描述，我们就可以很容易得到代码实现了：

 

public static String parse(String[] tokens) {        
        Stack<String> stack = new Stack<String>();
        for(String str : tokens) {
            System.out.println(str);
            if(str.equals(")")) {
                StringBuilder builder = new StringBuilder();
                builder.append("(");
                String op2 = stack.pop();
                String operator = stack.pop();
                String op1 = stack.pop();
                builder.append(op1);
                builder.append(operator);
                builder.append(op2);
                builder.append(str);
                stack.push(builder.toString());
            } else {
                stack.push(str);
            }
        }
        return stack.peek();
    }

     前面已经说的很清楚，这里无需解释。你懂的。

 

总结

    这里主要是针对一个算术表达式的结构在它的右括号已经确定的情况下，讨论怎么去填充它的左括号。我们会发现实际上对于一个表达式来说，只要有一边的括号是完全确定的，它就可以唯一的确定这个表达式了。同样的，假设我们有了左括号，对于缺失的右括号来说也可以按照同样的思路来补。对于这些问题后面的数学原理我们暂时没有深究。实际上它和数学上的catalan数有着密切的关系。在后续相关的文章里会做相应的分析。

 

参考材料

http://www.amazon.com/Algorithms-4th-Robert-Sedgewick/dp/032157351X/ref=sr_1_1?s=books&ie=UTF8&qid=1403251503&sr=1-1&keywords=algorithms