栈结构应用的两个实例

ゝ一纸荒年。 2022-07-13 10:07 161阅读 0赞

两个实例来自Java数据结构和算法.（第二版）第四章

1、单词逆序。

要求从控制台读入一串字符，按回车结束输入，同时显示其逆序字符串。

对于颠倒顺序的操作，用栈来解决是很方便的。具体思想是把字符串中的每一个字符按顺序存入栈中，然后再一个一个的从栈中取出。这时就是按照逆序取出的字符串。

// reverse.java
    // stack used to reverse a string
    // to run this program: C>java ReverseApp
    import java.io.*;                 // for I/O
    
    class StackX//定义了栈的基本结构和操作
       {
       private int maxSize;//栈最大值
       private char[] stackArray;//栈内用数组存储数据
       private int top;//当前栈顶标号，从0开始
    //--------------------------------------------------------------
       public StackX(int max)    // constructor
          {
          maxSize = max;
          stackArray = new char[maxSize];
          top = -1;
          }
    //--------------------------------------------------------------
       public void push(char j)  // put item on top of stack
          {
          stackArray[++top] = j;
          }
    //--------------------------------------------------------------
       public char pop()         // take item from top of stack
          {
          return stackArray[top--];
          }
    //--------------------------------------------------------------
       public char peek()        // peek at top of stack
          {
          return stackArray[top];
          }
    //--------------------------------------------------------------
       public boolean isEmpty()  // true if stack is empty
          {
          return (top == -1);
          }
    //--------------------------------------------------------------
       }  // end class StackX
    
    class Reverser//封装了单词逆序的操作
       {
       private String input;                // input string
       private String output;               // output string
    //--------------------------------------------------------------
       public Reverser(String in)           // constructor
          { input = in; }
    //--------------------------------------------------------------
       public String doRev()                // reverse the string
          {
          int stackSize = input.length();   // get max stack size
          StackX theStack = new StackX(stackSize);  // make stack
    
          for(int j=0; j<input.length(); j++)
             {
             char ch = input.charAt(j);     // get a char from input
             theStack.push(ch);             // push it
             }
          output = "";
          while( !theStack.isEmpty() )
             {
             char ch = theStack.pop();      // pop a char,
             output = output + ch;          // append to output
             }
          return output;
          }  // end doRev()
    //--------------------------------------------------------------
       }  // end class Reverser
    
    class ReverseApp
       {
       public static void main(String[] args) throws IOException
          {
          String input, output;
          while(true)
             {
             System.out.print("Enter a string: ");
             System.out.flush();
             input = getString();          // read a string from kbd
             if( input.equals("") )        // 若没有输入字符串直接按回车，则结束
                break;
                                           // make a Reverser
             Reverser theReverser = new Reverser(input);
             output = theReverser.doRev(); // use it
             System.out.println("Reversed: " + output);
             }  // end while
             System.out.println("this is end");
          }  // end main()
    //--------------------------------------------------------------
       public static String getString() throws IOException
          {
          InputStreamReader isr = new InputStreamReader(System.in);
          BufferedReader br = new BufferedReader(isr);
          String s = br.readLine();
          return s;
          }
    //--------------------------------------------------------------
       }  // end class ReverseApp

2.分隔符匹配

有些分割符在编程中一定是成对出现的，例如（），\{\}，和\[\]等。如果发现有未匹配的分隔符，编译器会报错。因为匹配操作采取就近原则，后输入的分割符优先匹配，具有“后进先出”的特点。这个匹配操作可以用栈来实现。

具体操作是在输入过程中，如果遇到左匹配符，则将左匹配符压入栈中。如果遇到右匹配符，则从栈中取出一个数据，分析其与右匹配符是否相匹配。若匹配，则继续进行，若不匹配，则报错终止。

// brackets.java
    // stacks used to check matching brackets
    // to run this program: C>java bracketsApp
    import java.io.*;                 // for I/O
    
    class StackX
       {
       private int maxSize;
       private char[] stackArray;
       private int top;
    //--------------------------------------------------------------
       public StackX(int s)       // constructor
          {
          maxSize = s;
          stackArray = new char[maxSize];
          top = -1;
          }
    //--------------------------------------------------------------
       public void push(char j)  // put item on top of stack
          {
          stackArray[++top] = j;
          }
    //--------------------------------------------------------------
       public char pop()         // take item from top of stack
          {
          return stackArray[top--];
          }
    //--------------------------------------------------------------
       public char peek()        // peek at top of stack
          {
          return stackArray[top];
          }
    //--------------------------------------------------------------
       public boolean isEmpty()    // true if stack is empty
          {
          return (top == -1);
          }
    //--------------------------------------------------------------
       }  // end class StackX
    
    class BracketChecker
       {
       private String input;                   // input string
    //--------------------------------------------------------------
       public BracketChecker(String in)        // constructor
          { input = in; }
    //--------------------------------------------------------------
       public void check()
          {
          int stackSize = input.length();      // get max stack size
          StackX theStack = new StackX(stackSize);  // make stack
    
          for(int j=0; j<input.length(); j++)  // get chars in turn
             {
             char ch = input.charAt(j);        // get char
             switch(ch)
                {
                case '{':                      // opening symbols
                case '[':
                case '(':
                   theStack.push(ch);          // push them
                   break;
    
                case '}':                      // closing symbols
                case ']':
                case ')':
                   if( !theStack.isEmpty() )   // if stack not empty,
                      {
                      char chx = theStack.pop();  // pop and check
                      if( (ch=='}' && chx!='{') ||
                          (ch==']' && chx!='[') ||
                          (ch==')' && chx!='(') )//分隔符不匹配
                         System.out.println("Error: "+ch+" at "+j);
                      }
                   else                        // prematurely empty
                      System.out.println("Error: "+ch+" at "+j);
                   break;
                default:    // no action on other characters
                   break;
                }  // end switch
             }  // end for
          // at this point, all characters have been processed
          if( !theStack.isEmpty() )
             System.out.println("Error: missing right delimiter");
          }  // end check()
    //--------------------------------------------------------------
       }  // end class BracketChecker
    
    class BracketsApp
       {
       public static void main(String[] args) throws IOException
          {
          String input;
          while(true)
             {
             System.out.print(
                          "Enter string containing delimiters: ");
             System.out.flush();
             input = getString();     // read a string from kbd
             if( input.equals("") )   // quit if [Enter]
                break;
                                      // make a BracketChecker
             BracketChecker theChecker = new BracketChecker(input);
             theChecker.check();      // check brackets
             }  // end while
          }  // end main()
    //--------------------------------------------------------------
       public static String getString() throws IOException
          {
          InputStreamReader isr = new InputStreamReader(System.in);
          BufferedReader br = new BufferedReader(isr);
          String s = br.readLine();
          return s;
          }
    //--------------------------------------------------------------
       }  // end class BracketsApp