双栈实现补齐括号

双栈

今天看算法4 里面的一道练习题，百思不得其解，百度发现可以用双栈实现；
编写一段程序，从标准输入得到一个缺少左括号的表达式并打印出补全括号之后的中序表达式。例如
输入：1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )
输出：( ( 1 + 2 ) * ( ( 3 - 4 ) * ( 5 - 6 ) ) )

解决思路：

使用两个栈分别保存数值和操作符，分别为opr和data。顺序处理输入字符串的字符：

• 如果为操作符，压入opr。
• 否则，如果为右括号，从data取出两个操作数，从opr取出1个操作符，添加括号组合后压入data。
• 否则，为数字，压入data。

以上处理办法需要输出满足以下条件，也就是有如下的假设：

• 输出表达式是合法的

public static void main(String[] args) {

      //双栈法
      //数值栈，压入数值
      LinkedListStack<String> dataStack = new LinkedListStack<>();
      //操作符栈，压入+-*/
      LinkedListStack<String> oprStack  = new LinkedListStack<>();
      String str ="1+2)*3-4)*5-6)))";
      String[] param = str.split("");

      for(int i= 0 ; i< str.length();i++){
          if(param[i].equals("+") || param[i].equals("-") || param[i].equals("*") || param[i].equals("/")){
              oprStack.push(param[i]);
          }else if(param[i].equals(")")){
              StringBuilder res = new StringBuilder();
              //因为是压栈，压进去的是相反的
              res.append(")").append(dataStack.pop()).append(oprStack.pop()).append(dataStack.pop()).append("(");
              dataStack.push(res.toString());
          }else {
              dataStack.push(param[i]);
          }
      }
      String res = dataStack.pop();
      System.out.println(res);
      StringBuilder temp = new StringBuilder();

      for(int i= res.length() -1; i>=0; i--){  
          temp.append(res.charAt(i));
      }
      System.out.println(temp.toString());

  }
}

整个过程看下来我是觉得，这个设计精巧，通过一个存储操作符一个存储数值，然后通过')'来判断缺不缺，遇到）则补上（ ，由于是栈的出来的表达式是反的，这样反转一下，就得出最终结果