利用栈结构生成后缀表达式

我不是女神ヾ 2022-07-13 10:27 158阅读 0赞

利用栈结构来构建后缀表达式

关于后缀表达式，推荐博客http://blog.csdn.net/antineutrino/article/details/6763722/

博客中详细介绍了表达式的生成过程。这里作简要介绍。

后缀表达式的生成准则：

![20170105170301600][]![20170105170313754][]

利用该准则转换A\*（B+C）

![20170105170329866][]

利用该准则转换A+B\*C

![20170105170700412][]![20170105170710293][]

利用该准则转换A+B-C

![20170105170844530][]

有了这个准则，我们就可以设计一个栈来实现后缀表达式的转换。

// infix.java
    // converts infix arithmetic expressions to postfix
    // to run this program: C>java InfixApp
    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); }
    //-------------------------------------------------------------
       public int size()         // return size
          { return top+1; }
    //--------------------------------------------------------------
       public char peekN(int n)  // return item 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 InToPost                  // 定义后缀表达式转换准则
       {
       private StackX theStack;
       private String input;
       private String output = "";
    //--------------------------------------------------------------
       public InToPost(String in)   // constructor
          {
          input = in;
          int stackSize = input.length();
          theStack = new StackX(stackSize);
          }
    //--------------------------------------------------------------
       public String doTrans()      // do translation to postfix
          {
          for(int j=0; j<input.length(); j++)      // for each char
             {
             char ch = input.charAt(j);  // 获得input对应的字符数组中下标为j的字符值
             theStack.displayStack("For "+ch+" "); // *diagnostic*
             switch(ch)
                {
                case '+':               // it's + or -
                case '-':
                   gotOper(ch, 1);      // 第二个参数“1”表示+和-的优先级为1
                   break;               //   (precedence 1)
                case '*':               // it's * or /
                case '/':
                   gotOper(ch, 2);      //第二个参数“2”表示*和/的优先级为2
                   break;               //   (precedence 2)
                case '(':               // it's a left paren
                   theStack.push(ch);   // push it
                   break;
                case ')':               // it's a right paren
                   gotParen(ch);        // go pop operators
                   break;
                default:                // must be an operand
                   output = output + ch; // 如果是数字而不是操作符，不入栈直接输出
                   break;
                }  // end switch
             }  // end for
          while( !theStack.isEmpty() )     // pop remaining opers
             {
             theStack.displayStack("While ");  // *diagnostic*
             output = output + theStack.pop(); // write to output
             }
          theStack.displayStack("End   ");     // *diagnostic*
          return output;                   // return postfix
          }  // end doTrans()
    //--------------------------------------------------------------
       public  void gotOper(char opThis, int prec1)//处理加减乘除操作符
          {                                // got operator from input
          while( !theStack.isEmpty() )
             {
             char opTop = theStack.pop();
             if( opTop == '(' )            // if it's a '('
                {
                theStack.push(opTop);      // restore '('
                break;
                }
             else                          // it's an operator
                {
                int prec2;                 // precedence of new op
    
                if(opTop=='+' || opTop=='-')  // find new op prec
                   prec2 = 1;
                else
                   prec2 = 2;
                if(prec2 < prec1)          // if prec of new op less
                   {                       //    than prec of old
                   theStack.push(opTop);   // save newly-popped op
                   break;
                   }
                else                       // prec of new not less
                   output = output + opTop;  // than prec of old
                }  // end else (it's an operator)
             }  // end while
          theStack.push(opThis);           // push new operator
          }  // end gotOp()
    //--------------------------------------------------------------
       public  void gotParen(char ch)//处理“）”
          {                             // got right paren from input
          while( !theStack.isEmpty() )
             {
             char chx = theStack.pop();
             if( chx == '(' )           // if popped '('
                break;                  // we're done
             else                       // if popped operator
                output = output + chx;  // output it
             }  // end while
          }  // end popOps()
    //--------------------------------------------------------------
       }  // end class InToPost
    
    class InfixApp
       {
       public static void main(String[] args) throws IOException
          {
          String input, output;
          while(true)
             {
             System.out.print("Enter infix: ");
             System.out.flush();
             input = getString();         // read a string from kbd
             if( input.equals("") )       // quit if [Enter]
                break;
                                          // make a translator
             InToPost theTrans = new InToPost(input);
             output = theTrans.doTrans(); // do the translation
             System.out.println("Postfix is " + output + '\n');
             }  // 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 InfixApp

[20170105170301600]: https://img-blog.csdn.net/20170105170301600
[20170105170313754]: /images/20220713/35e64e21cc584837b28f0469a95fdf7a.png
[20170105170329866]: /images/20220713/ff71ec9824df4f88b87f7a87cddebbfd.png
[20170105170700412]: https://img-blog.csdn.net/20170105170700412
[20170105170710293]: /images/20220713/7ffc7748673b4a098510b6604b2423ef.png
[20170105170844530]: /images/20220713/41874b3553554dca88f495b4906f2abe.png