Algs4-1.3.9补全中序表达式的左括号(第二次实现)

 1.3.9编写一段程序,从标准输入得到一个缺少左括号的表达式并打印出补全括号之后的中序表达式。
例如,给定输入:
1+2)*3-4)*5-6)))
你的程序应该输出:
((1+2)*((3-4)*(5-6)))
图片

答:与上一次实现时没有本质区别,都是用两个栈,数据从左到右或是从右到左移动。实现方面略有差别。
粗算法:遇到读入的是右括号时,在第二个运算符的后面添加左括号。
1)往表达式左边找,找到最左边后仍就找不到第二个运算符,那么在表达式最左边加左括号。
2)往表达式左边找时,遇到了右括号,那么再往左边找,在遇到与之对应的左括号后遇到的运算符才能计数。

细算法:
1)不断的读入字符串,直到读到空串时结束读入。
    1.2)读入非右括号时,读入的字符串压入左栈。
    1.3)读入右括时
         1.3.1)从左栈中弹出项,直到左栈为空或是运算符计数器是2时结束左栈弹出操作
                1.3.1.1)从左栈弹出的值为LeftItem,将弹出的值压入右栈。
                1.3.1.1)如果弹出项的值为右括号时,括号计数器增1;
                1.3.1.2)如果弹出项的值为左括号时,括号计数器减1;
                1.3.1.3)如果弹出项的值是运算符,并且括号计数器的值是0,那么运算符计数器增1;
         1.3.2.1)运算符计数器置0;
         1.3.2.2)如果左栈有内容,那么先从右栈中弹出一项压入左栈,然后将一个左括号压入左栈,然后将右栈的所有项弹出并压入左栈。
         1.3.2.3)如果左栈没有内容,那么将一个左括号压入左栈,然后将右栈的所有项弹出并压入左栈。
2)将左栈内容反序输出
 

public class test
{
   public static void main(String[] args)
   {
     
   Stack<String> leftStack=new Stack<String>();
      Stack<String> rightStack=new Stack<String>();
      //
      int countOfOperator=0;
      int countOfRightParenthesis=0;
      //
      while(!StdIn.isEmpty())
      {
          String item=StdIn.readString();
          if(!item.equals(")"))
              leftStack.push(item);
          else
          {
              while(!(leftStack.isEmpty() || countOfOperator==2))
              {
                  String leftItem=leftStack.pop();
                  rightStack.push(leftItem);
                  if(leftItem.equals(")"))
                      countOfRightParenthesis++;
                  else if(leftItem.equals("("))
                      countOfRightParenthesis--;
                  else if((leftItem.equals("+") || leftItem.equals("-") || leftItem.equals("*")) && countOfRightParenthesis==0)
                      countOfOperator++;
              }//frim left stack to right stack
                countOfOperator=0;
                if(!leftStack.isEmpty())  leftStack.push(rightStack.pop());
                leftStack.push("(");
                while(!rightStack.isEmpty())
                      leftStack.push(rightStack.pop());
                leftStack.push(")");
           }//end if ")"
      }//end while read
      while(!leftStack.isEmpty())
          rightStack.push(leftStack.pop());
      while(!rightStack.isEmpty())
          StdOut.print(rightStack.pop());
    }//end main
}//end class

原文地址:https://www.cnblogs.com/longjin2018/p/9849325.html