class ArrayStack{
    /**
     * 棧的大小
     */
    private int maxSize;
    /**
     * 數(shù)組，模擬棧
     */
    private int[] stack;
    /**
     * top表示棧頂數(shù)據(jù)所在數(shù)組位置的下標(biāo),初始化為-1
     */
    private int top = -1;
    /**
     * 構(gòu)造器，初始化棧
     * @param maxSize 棧的大小
     */
    public ArrayStack(int maxSize){
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }
    /**
     * 返回當(dāng)前棧頂?shù)闹担怀鰲?
     * @return 當(dāng)前棧頂?shù)闹?
     */
    public int topData(){
        return stack[top];
    }
    /**
     * 判斷棧是否滿
     */
    public boolean isFull(){
        return top==maxSize-1;
    }
    /**
     * 判斷棧是否空
     */
    public boolean isNull(){
        return top==-1;
    }
    /**
     * 入棧
     * @param data 入棧的數(shù)據(jù)
     */
    public void push(int data){
        //先判斷棧是否是滿的
        if (isFull()){
            //如果是滿的，打印錯(cuò)誤，直接返回
            System.out.println("棧已滿");
            return;
        }
        //棧沒滿，入棧
        // top++;stack[top]=data;
        stack[++top] = data;
    }
    /**
     * 出棧
     * @return 返回棧頂數(shù)據(jù)
     */
    public int pop(){
        //先判斷棧是否為空
        if (isNull()){
            //如果為空，拋出異常
            throw new RuntimeException("棧為空，沒有可出棧數(shù)據(jù)");
        }
        //不為空?qǐng)?zhí)行出棧
        return stack[top--];
    }
    /**
     * 顯示棧的情況，從棧頂顯示到棧底
     */
    public void showStack(){
        //先判斷是否為空棧
        if (isNull()){
            System.out.println("棧為空，沒有數(shù)據(jù)");
            return;
        }
        //遍歷顯示棧
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d]=%d\n",i,stack[i]);
        }
    }

    /**
     * 判斷char字符是否是一個(gè)運(yùn)算符
     * @param operator 要檢測(cè)是否是運(yùn)算符的char
     * @return 是否為運(yùn)算符
     */
    static boolean isOperator(int operator){
        return operator=='+'||operator=='-'||operator=='*'||operator=='/';
    }
    /**
     * 判斷char字符是否是括號(hào)
     */
    static boolean isBracket(int operator){
        return operator=='('||operator==')';
    }
    /**
     * 返回運(yùn)算符優(yōu)先級(jí)（數(shù)字大優(yōu)先級(jí)高）
     * @param operator 運(yùn)算符
     * @return 表示優(yōu)先級(jí)的int
     */
    static int priority(int operator){
        if (operator == '+' || operator == '-'){
            return 0;
        }
        if (operator == '*' || operator == '/'){
            return 1;
        }
        return -1;
    }
    /**
     * 根據(jù)運(yùn)算符計(jì)算兩個(gè)數(shù)據(jù)
     * @param num1 數(shù)據(jù)1
     * @param num2 數(shù)據(jù)2
     * @param operator 運(yùn)算符（+-*除）
     * @return 運(yùn)算結(jié)果
     */
    static int calculate(int num1,int num2,int operator){
        int res = 0;
        switch (operator){
            case '+':
                res = num2 + num1;
                break;
            case '-':
                res = num2 - num1;
                break;
            case '*':
                res = num2 * num1;
                break;
            case '/':
                res = num2 / num1;
                break;
            default:
                break;
        }
        return res;
    }

    /**
     * 計(jì)算中綴表達(dá)式的結(jié)果（不能含有括號(hào)）
     * @param expression 中綴表達(dá)式
     * @return 結(jié)果
     */
    static int calculateMid(String expression) {
        //數(shù)字棧
        ArrayStack numStack = new ArrayStack(10);
        //運(yùn)算符棧
        ArrayStack operatorStack = new ArrayStack(10);
        //遍歷字符串進(jìn)行入棧等運(yùn)算操作
        for (int i = 0; i < expression.length(); i++) {
            //遍歷到字符串中的一個(gè)字符
            char ch = expression.charAt(i);
            //判斷是否為運(yùn)算符
            if (isOperator(ch)) {
                //如果是運(yùn)算符,判斷當(dāng)前符號(hào)棧是否為空
                //不為空，判斷當(dāng)前符號(hào)優(yōu)先級(jí)和棧中符號(hào)優(yōu)先級(jí)的關(guān)系進(jìn)行操作
                //當(dāng)前運(yùn)算符優(yōu)先級(jí)小于等于棧中運(yùn)算符優(yōu)先級(jí)，從數(shù)棧中pop兩個(gè)數(shù)據(jù)，運(yùn)算符棧中pop一個(gè)運(yùn)算符進(jìn)行計(jì)算，計(jì)算結(jié)果push進(jìn)數(shù)棧，新運(yùn)算符再次進(jìn)行優(yōu)先級(jí)判斷
                while (!operatorStack.isNull() && priority(ch) <= priority(operatorStack.topData())){
                    int num1 = numStack.pop();
                    int num2 = numStack.pop();
                    int operator = operatorStack.pop();
                    int res = calculate(num1, num2, operator);
                    numStack.push(res);
                }
                //直到當(dāng)前運(yùn)算符優(yōu)先級(jí)大于棧中運(yùn)算符優(yōu)先級(jí)或棧為空，再入棧
                operatorStack.push(ch);
            }else {
                //如果不是運(yùn)算符,判斷是否是數(shù)字
                if (Character.isDigit(ch)) {
                    //如果是數(shù)字，準(zhǔn)備記錄下這個(gè)數(shù)字
                    StringBuilder num = new StringBuilder(String.valueOf(ch));
                    //找到下一個(gè)字符判斷，進(jìn)行拼接操作，直到下一個(gè)為運(yùn)算符或沒有下一個(gè)字符為止
                    while (i+1 < expression.length()&&!isOperator(expression.charAt(i+1))) {
                        //如果還是數(shù)字，先將數(shù)字拼接,再i++
                        num.append(expression.charAt(i+1));
                        i++;
                    }
                    numStack.push(Integer.parseInt(num.toString()));
                }else {
                    //如果不是數(shù)字（到這里就既不是數(shù)字也不是運(yùn)算符）報(bào)錯(cuò)表達(dá)式有誤
                    throw new RuntimeException("運(yùn)算表達(dá)式有誤,不支持的符號(hào):[ "+ch+" ]");
                }
            }
        }
        //遍歷結(jié)束后將棧中繼續(xù)計(jì)算直到數(shù)棧中只有一個(gè)數(shù)字，就是結(jié)果
        while (!operatorStack.isNull()){
            int num1 = numStack.pop();
            int num2 = numStack.pop();
            int operator = operatorStack.pop();
            int res = calculate(num1, num2, operator);
            numStack.push(res);
        }
        return numStack.pop();
    }

    /**
     * 計(jì)算后綴表達(dá)式
     * @param expression 后綴表達(dá)式
     * @return 計(jì)算結(jié)果
     */
    static int calculateSuf(String expression){
        //1.將后綴表達(dá)式拆開放入集合
        String[] expressionList = expression.split(" ");
        //2.創(chuàng)建數(shù)棧
        ArrayStack numStack = new ArrayStack(10);
        for (String s : expressionList) {
            //判斷是否是符號(hào)
            if (isOperator(s.charAt(0))) {
                //是符號(hào)就出棧兩個(gè)數(shù)據(jù)進(jìn)行計(jì)算
                int num1 = numStack.pop();
                int num2 = numStack.pop();
                int res = calculate(num1, num2, s.charAt(0));
                //計(jì)算結(jié)果入棧
                numStack.push(res);
            }else {
                //不是符號(hào)轉(zhuǎn)換為數(shù)字入棧即可
                int num;
                try {
                    num = Integer.parseInt(s);
                }catch (NumberFormatException e){
                    throw new RuntimeException("錯(cuò)誤的表達(dá)式：[ "+s+" ]");
                }
                numStack.push(num);
            }
        }
        return numStack.pop();
    }

    static String infixToSuffix(String infix){
        //運(yùn)算符棧
        ArrayStack operatorStack = new ArrayStack(20);
        //結(jié)果棧
        ArrayStack resStack = new ArrayStack(20);
        //遍歷掃描中綴表達(dá)式
        for (int i = 0; i < infix.length(); i++) {
            //遍歷到的一個(gè)字符
            char ch = infix.charAt(i);
            //判斷是否為運(yùn)算符
            if (isOperator(ch)){
                //循環(huán)判斷如果運(yùn)算符棧不為空且當(dāng)前運(yùn)算符優(yōu)先級(jí)不大于棧頂運(yùn)算符
                while (!operatorStack.isNull() && priority(ch) <= priority(operatorStack.topData())){
                    //彈出運(yùn)算符棧壓入結(jié)果棧
                    resStack.push(operatorStack.pop());
                }
                //當(dāng)前運(yùn)算符入運(yùn)算符棧
                operatorStack.push(ch);

            }
            //如果不是運(yùn)算符再判斷是否是運(yùn)算數(shù)，是就直接壓入結(jié)果棧
            else if (Character.isDigit(ch)){
                //如果是數(shù)字，記錄下這個(gè)數(shù)字壓入結(jié)果棧
                StringBuilder num = new StringBuilder(String.valueOf(ch));
                //找到下一個(gè)字符判斷，進(jìn)行拼接操作，直到下一個(gè)為運(yùn)算符或沒有下一個(gè)字符為止
                while (i+1 < infix.length()&&Character.isDigit(infix.charAt(i+1))) {
                    //如果還是數(shù)字，先將數(shù)字拼接,再i++
                    num.append(infix.charAt(i+1));
                    i++;
                }
                resStack.push(Integer.parseInt(num.toString()));
            }
            //如果不是運(yùn)算符也不是操作數(shù)，判斷是否為括號(hào)
            else if (isBracket(ch)){
                //如果是括號(hào)，判斷左括號(hào)壓入運(yùn)算符棧
                if (ch=='('){
                    operatorStack.push(ch);
                }
                //如果是右括號(hào)，依次彈出s1的運(yùn)算符，壓入結(jié)果棧，直到遇見左括號(hào)（丟棄這一對(duì)括號(hào)）
                else if (ch==')'){
                    while (true){
                        int top = operatorStack.pop();
                        if (top=='('){
                            break;
                        }
                        resStack.push(top);
                    }
                }
            }
        }
        //遍歷結(jié)束后，將運(yùn)算符棧中剩余的運(yùn)算符依次彈出壓入結(jié)果棧
        while (!operatorStack.isNull()){
            resStack.push(operatorStack.pop());
        }
        //遍歷結(jié)果棧返回后綴表達(dá)式字符串(這里是反的)
        StringBuilder res = new StringBuilder();
        while (!resStack.isNull()){
            int pop = resStack.pop();
            if (isOperator(pop)){
                char popChar = (char) pop;
                res.append(popChar).append(" ");
            }else {
                res.append(pop).append(" ");
            }
        }
        //將結(jié)果字符串反轉(zhuǎn)返回后綴表達(dá)式
        String s = res.toString();
        String[] s1 = s.split(" ");
        StringBuilder builder = new StringBuilder();
        for (int i = s1.length-1; i >= 0; i--) {
            builder.append(s1[i]).append(" ");
        }
        return builder.toString();
    }