《算法4》1.3.9题，题目让缺少左括号的表达式补全字符串：

如：str1: 1+2)*3-4)*5-6)))要输出：((1+2)*((3-4)*(5-6)))

思路：

参考双栈计算表达式式值的算法，我们尝试由两个栈分别存储操作数与操作符：

LinkStack<String> valStack = new LinkStack<>();
LinkStack<String> opStack = new LinkStack<>();

依次遍历str1，当遇到)时，对opStack出栈，对valStack出栈两次，并在字符串头部补全(：

String op = opStack.pop();
String val1 = valStack.pop();
String val2 = valStack.pop();

那么对于多个的子操作，如何连起来呢，我们可以把补全的子字符串，作为一个字符串压栈，这样再遇到)时，执行相似操作，

valStack.push("(" + val2 + op + val1 + ")");

完整代码：

LinkStack<String> valStack = new LinkStack<>();
LinkStack<String> opStack = new LinkStack<>();
String listStr = "";
String str = "1+2)*3-4)*5-6)))";
//str = "1+2)*4-3))";
char[] chars = str.toCharArray();

for (int i = 0; i < chars.length; i++)
{
    if (chars[i] == '+' || chars[i] == '-' || chars[i] == '*' || chars[i] == '/')
    {
        opStack.push(String.valueOf(chars[i]));
    }
    else if (chars[i] == ')')
    {
        String op = opStack.pop();
        String val1 = valStack.pop();
        String val2 = valStack.pop();

        valStack.push("(" + val2 + op + val1 + ")");
    }
    else
    {
        valStack.push(String.valueOf(chars[i]));
    }
}

while (!valStack.isEmpty())
{
    listStr = valStack.pop() + listStr;
}

System.out.println(listStr);