利用栈结构求取后缀表达式的值

分手后的思念是犯贱 2022-07-13 10:49 171阅读 0赞

后缀表达式的求值准则：

从左到右依次读取表达式，每遇到一个操作符，就读取该操作符之前的最后两个操作数，计算其值并把计算结果作为一个新的操作数，然后继续向后读取直到结束。从过程上可以看出，优先计算的是后出现的操作数，符合栈结构的特点，所以可以用栈结构来实现。

具体来说，用一个栈来存储操作数，每遇到一个操作符，就执行两次出栈操作。然后把计算的结果在推入栈中。当扫描完整个后缀表达式后，栈中就只剩一个数值，也就是最后的计算结果。

// postfix.java
    // parses postfix arithmetic expressions
    // to run this program: C>java PostfixApp
    import java.io.*;              // for I/O
    
    class StackX//定义栈结构
       {
       private int maxSize;
       private int[] stackArray;
       private int top;
    //--------------------------------------------------------------
       public StackX(int size)      // constructor
          {
          maxSize = size;
          stackArray = new int[maxSize];
          top = -1;
          }
    //--------------------------------------------------------------
       public void push(int j)     // put item on top of stack
          { stackArray[++top] = j; }
    //--------------------------------------------------------------
       public int pop()            // take item from top of stack
          { return stackArray[top--]; }
    //--------------------------------------------------------------
       public int peek()           // peek at top of stack
          { return stackArray[top]; }
    //--------------------------------------------------------------
       public boolean isEmpty()    // true if stack is empty
          { return (top == -1); }
    //--------------------------------------------------------------
       public boolean isFull()     // true if stack is full
          { return (top == maxSize-1); }
    //--------------------------------------------------------------
       public int size()           // return size
          { return top+1; }
    //--------------------------------------------------------------
       public int peekN(int n)     // peek at index n
          { return stackArray[n]; }
    //--------------------------------------------------------------
       public void displayStack(String s)
          {
          System.out.print(s);
          System.out.print("Stack (bottom-->top): ");
          for(int j=0; j<size(); j++)
             {
             System.out.print( peekN(j) );
             System.out.print(' ');
             }
          System.out.println("");
          }
    //--------------------------------------------------------------
       }  // end class StackX
    
    class ParsePost//计算后缀表达式
       {
       private StackX theStack;
       private String input;
    //--------------------------------------------------------------
       public ParsePost(String s)
          { input = s; }
    //--------------------------------------------------------------
       public int doParse()
          {
          theStack = new StackX(20);             // make new stack
          char ch;
          int j;
          int num1, num2, interAns;//定义两个操作数和计算结果
    
          for(j=0; j<input.length(); j++)       // for each char,
             {
             ch = input.charAt(j);              // read from input
             theStack.displayStack(""+ch+" ");  // *diagnostic*
             if(ch >= '0' && ch <= '9')         // if it's a number
                theStack.push( (int)(ch-'0') ); //(int)(ch-'0')是ch的数值，不加int是AScii
             else                               // it's an operator
                {
                num2 = theStack.pop();          // pop operands
                num1 = theStack.pop();
                switch(ch)                      // do arithmetic
                   {
                   case '+':
                      interAns = num1 + num2;
                      break;
                   case '-':
                      interAns = num1 - num2;
                      break;
                   case '*':
                      interAns = num1 * num2;
                      break;
                   case '/':
                      interAns = num1 / num2;
                      break;
                   default:
                      interAns = 0;
                   }  // end switch
                theStack.push(interAns);        // push result
                }  // end else
             }  // end for
          interAns = theStack.pop();            // get answer
          return interAns;
          }  // end doParse()
       }  // end class ParsePost
    
    class PostfixApp
       {
       public static void main(String[] args) throws IOException
          {
          String input;
          int output;
    
          while(true)
             {
             System.out.print("Enter postfix: ");
             System.out.flush();
             input = getString();         // read a string from kbd
             if( input.equals("") )       // quit if [Enter]
                break;
                                          // make a parser
             ParsePost aParser = new ParsePost(input);
             output = aParser.doParse();  // do the evaluation
             System.out.println("Evaluates to " + output);
             }  // 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 PostfixApp