package com.ys.poland;
public class MyCharStack {
    private char[] array;
    private int maxSize;
    private int top;
    public MyCharStack(int size){
        this.maxSize = size;
        array = new char[size];
        top = -1;
    }
    //壓入數(shù)據(jù)
    public void push(char value){
        if(top < maxSize-1){
            array[++top] = value;
        }
    }
    //彈出棧頂數(shù)據(jù)
    public char pop(){
        return array[top--];
    }
    //訪問(wèn)棧頂數(shù)據(jù)
    public char peek(){
        return array[top];
    }
    //查看指定位置的元素
    public char peekN(int n){
        return array[n];
    }
    //為了便于后面分解展示棧中的內(nèi)容，我們?cè)黾恿艘粋€(gè)遍歷棧的方法(實(shí)際上棧只能訪問(wèn)棧頂元素的)
    public void displayStack(){
        System.out.print("Stack(bottom-->top):");
        for(int i = 0 ; i < top+1; i++){
            System.out.print(peekN(i));
            System.out.print(' ');
        }
        System.out.println("");
    }
    //判斷棧是否為空
    public boolean isEmpty(){
        return (top == -1);
    }
    //判斷棧是否滿了
    public boolean isFull(){
        return (top == maxSize-1);
    }
}

package com.ys.poland;
public class InfixToSuffix {
    private MyCharStack s1;//定義運(yùn)算符棧
    private MyCharStack s2;//定義存儲(chǔ)結(jié)果棧
    private String input;
    //默認(rèn)構(gòu)造方法，參數(shù)為輸入的中綴表達(dá)式
    public InfixToSuffix(String in){
        input = in;
        s1 = new MyCharStack(input.length());
        s2 = new MyCharStack(input.length());
    }
    //中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，將結(jié)果存儲(chǔ)在棧中返回，逆序顯示即后綴表達(dá)式
    public MyCharStack doTrans(){
        for(int j = 0 ; j < input.length() ; j++){
            System.out.print("s1棧元素為：");
            s1.displayStack();
            System.out.print("s2棧元素為：");
            s2.displayStack();
            char ch = input.charAt(j);
            System.out.println("當(dāng)前解析的字符:"+ch);
            switch (ch) {
            case '+':
            case '-':
                gotOper(ch,1);
                break;
            case '*':
            case '/':
                gotOper(ch,2);
                break;
            case '(':
                s1.push(ch);//如果當(dāng)前字符是'(',則將其入棧
                break;
            case ')':
                gotParen(ch);
                break;
            default:
                //1、如果當(dāng)前解析的字符是操作數(shù)，則直接壓入s2
                //2、
                s2.push(ch);
                break;
            }//end switch
        }//end for
        while(!s1.isEmpty()){
            s2.push(s1.pop());
        }
        return s2;
    }
    public void gotOper(char opThis,int prec1){
        while(!s1.isEmpty()){
            char opTop = s1.pop();
            if(opTop == '('){//如果棧頂是'(',直接將操作符壓入s1
                s1.push(opTop);
                break;
            }else{
                int prec2;
                if(opTop == '+' || opTop == '-'){
                    prec2 = 1;
                }else{
                    prec2 = 2;
                }
                if(prec2 < prec1){//如果當(dāng)前運(yùn)算符比s1棧頂運(yùn)算符優(yōu)先級(jí)高，則將運(yùn)算符壓入s1
                    s1.push(opTop);
                    break;
                }else{//如果當(dāng)前運(yùn)算符與棧頂運(yùn)算符相同或者小于優(yōu)先級(jí)別，那么將S1棧頂?shù)倪\(yùn)算符彈出并壓入到S2中
                    //并且要再次再次轉(zhuǎn)到while循環(huán)中與 s1 中新的棧頂運(yùn)算符相比較；
                    s2.push(opTop);
                }
            }
        }//end while
        //如果s1為空，則直接將當(dāng)前解析的運(yùn)算符壓入s1
        s1.push(opThis);
    }
    //當(dāng)前字符是 ')' 時(shí)，如果棧頂是'(',則將這一對(duì)括號(hào)丟棄，否則依次彈出s1棧頂?shù)淖址?，壓入s2，直到遇到'('
    public void gotParen(char ch){
        while(!s1.isEmpty()){
            char chx = s1.pop();
            if(chx == '('){
                break;
            }else{
                s2.push(chx);
            }
        }
    }
}

@Test
public void testInfixToSuffix(){
    String input;
    System.out.println("Enter infix:");
    Scanner scanner = new Scanner(System.in);
    input = scanner.nextLine();
    InfixToSuffix in = new InfixToSuffix(input);
    MyCharStack my = in.doTrans();
    my.displayStack();
}