JAVA数据结构--解析数学表达式

  1 // brackets.java
  2 // stacks used to check matching brackets
  3 // to run this program: C>java bracketsApp
  4 import java.io.*;                 // for I/O
  5 ////////////////////////////////////////////////////////////////
  6 class StackX
  7    {
  8    private int maxSize;
  9    private char[] stackArray;
 10    private int top;
 11 //--------------------------------------------------------------
 12    public StackX(int s)       // constructor
 13       {
 14       maxSize = s;
 15       stackArray = new char[maxSize];
 16       top = -1;
 17       }
 18 //--------------------------------------------------------------
 19    public void push(char j)  // put item on top of stack
 20       {
 21       stackArray[++top] = j;
 22       }
 23 //--------------------------------------------------------------
 24    public char pop()         // take item from top of stack
 25       {
 26       return stackArray[top--];
 27       }
 28 //--------------------------------------------------------------
 29    public char peek()        // peek at top of stack
 30       {
 31       return stackArray[top];
 32       }
 33 //--------------------------------------------------------------
 34    public boolean isEmpty()    // true if stack is empty
 35       {
 36       return (top == -1);
 37       }
 38 //--------------------------------------------------------------
 39    }  // end class StackX
 40 ////////////////////////////////////////////////////////////////
 41 class BracketChecker
 42    {
 43    private String input;                   // input string
 44 //--------------------------------------------------------------
 45    public BracketChecker(String in)        // constructor
 46       { input = in; }
 47 //--------------------------------------------------------------
 48    public void check()
 49       {
 50       int stackSize = input.length();      // get max stack size
 51       StackX theStack = new StackX(stackSize);  // make stack
 52 
 53       for(int j=0; j<input.length(); j++)  // get chars in turn
 54          {
 55          char ch = input.charAt(j);        // get char
 56          switch(ch)
 57             {
 58             case '{':                      // opening symbols
 59             case '[':
 60             case '(':
 61                theStack.push(ch);          // push them
 62                break;
 63 
 64             case '}':                      // closing symbols
 65             case ']':
 66             case ')':
 67                if( !theStack.isEmpty() )   // if stack not empty,
 68                   {
 69                   char chx = theStack.pop();  // pop and check
 70                   if( (ch=='}' && chx!='{') ||
 71                       (ch==']' && chx!='[') ||
 72                       (ch==')' && chx!='(') )
 73                      System.out.println("Error: "+ch+" at "+j);
 74                   }
 75                else                        // prematurely empty
 76                   System.out.println("Error: "+ch+" at "+j);
 77                break;
 78             default:    // no action on other characters
 79                break;
 80             }  // end switch
 81          }  // end for
 82       // at this point, all characters have been processed
 83       if( !theStack.isEmpty() )
 84          System.out.println("Error: missing right delimiter");
 85       }  // end check()
 86 //--------------------------------------------------------------
 87    }  // end class BracketChecker
 88 ////////////////////////////////////////////////////////////////
 89 class BracketsApp
 90    {
 91    public static void main(String[] args) throws IOException
 92       {
 93       String input;
 94       while(true)
 95          {
 96          System.out.print(
 97                       "Enter string containing delimiters: ");
 98          System.out.flush();
 99          input = getString();     // read a string from kbd
100          if( input.equals("") )   // quit if [Enter]
101             break;
102                                   // make a BracketChecker
103          BracketChecker theChecker = new BracketChecker(input);
104          theChecker.check();      // check brackets
105          }  // end while
106       }  // end main()
107 //--------------------------------------------------------------
108    public static String getString() throws IOException
109       {
110       InputStreamReader isr = new InputStreamReader(System.in);
111       BufferedReader br = new BufferedReader(isr);
112       String s = br.readLine();
113       return s;
114       }
115 //--------------------------------------------------------------
116    }  // end class BracketsApp
117 ////////////////////////////////////////////////////////////////