public class Stacks {
    public int maxSize;
    public int top ;
    public int[] stack;
    //構造器，傳入棧的最大容量
    public Stacks(int maxSize) {
        this.maxSize = maxSize;
        //初始化棧頂?shù)奈恢脼?1，?？?
        top = -1;
        //初始化數(shù)組，最大容量為棧的容量
        stack = new int[maxSize];
    }
}

    //因為底層是數(shù)組存儲數(shù)據(jù)，所以索引從0開始，
    //判斷條件為 top == maxSize - 1
    public boolean isFull(){
        return top == maxSize - 1;
    }

    public boolean isEmpty(){
        return top == -1;
    }

    public void push(int data){
        //判斷是否棧滿
        if (isFull()){
            System.out.println("棧滿，無法入棧");
            return;
        }
        top++;
        stack[top] = data;
    }

    public int pop(){
        if (isEmpty()){
            throw new RuntimeException("?？眨瑹o法出棧！");
        }
        //先出棧，后減減
        return stack[top--];
    }

  public void show(){
        if (isEmpty()){
            System.out.println("?？眨瑹o法顯示！");
            return;
        }
        for (int i = top ; i >= 0; i--){
            System.out.printf("stack[%d] = %d\n", i , stack[i]);
        }
    }

    public static List<String> endList(String s){
        String[] s1 = s.split("");
        List<String> stringList = new ArrayList<>();
        for (String s2 : s1) {
            stringList.add(s2);
        }
        return stringList;
    }

  public static int Calcu(String s){
        char ch = s.charAt(0);
        if (ch == '-' || ch == '+'){
            return 0;
        } else if (ch == '*' || ch == '/') {
            return 1;
        }
        return -1;
    }

public static List<String> MiddleToEndExpress(List<String> strings){
        //創(chuàng)建棧，存放運算符
        Stack<String> operStack = new Stack<>();
        //因為這個棧不需要出棧，所以使用集合
        List<String> sumList = new ArrayList<>();
        for (String s : strings) {
            //判斷是否是數(shù)據(jù)
            if (s.matches("\\d+")){
               sumList.add(s);//是數(shù)據(jù)直接加入
            }else if (s.equals("(")){//判斷是否是左括號
                operStack.push(s);//是，直接放入符號棧
            }else if (s.equals(")")){//判斷是否是右括號
                while (!operStack.peek().equals("(")){//如果棧頂是左括號，退出循環(huán)
                    sumList.add(operStack.pop());//不是左括號，就將棧頂?shù)姆栆来畏湃爰?
                }
                //循環(huán)結束，表示棧頂是左括號，把左括號去掉，就去掉了一對括號
                operStack.pop();
            }else {//前面的判斷都不是，那就是運算符
               //如果符號棧為空，并且運算符小于等于棧頂?shù)倪\算符優(yōu)先級
                while (operStack.size() != 0 && Calcu(s) <= Calcu(operStack.peek())){
                    //就將棧頂?shù)倪\算符放入集合中
                    sumList.add(operStack.pop());
                }
                //然后將符號放入符號棧中
                operStack.push(s);
            }
        }
        //遍歷結束，將符號棧剩余的符號依次取出放入集合中
        while (operStack.size() != 0){
            sumList.add(operStack.pop());
        }
        //最后將集合返回
        return sumList;
    }

public static int endCalculator(List<String> stringList){
        //創(chuàng)建棧，存放數(shù)據(jù)
        Stack<String> dataStack = new Stack<>();
        //循環(huán)遍歷集合
        for (String s : stringList) {
            //正則表達式判斷是否是數(shù)據(jù)，如果是，就放入棧中
            if (s.matches("\\d+")){
                dataStack.push(s);
            }else {//否則就是運算符
                //取出兩個數(shù)據(jù)
                int num1 = Integer.parseInt(dataStack.pop());
                int num2 = Integer.parseInt(dataStack.pop());
                //存放運算結果的變量
                int res = 0;
                //判斷運算符繼續(xù)相應的運算
                if (s.equals("+")){
                    res = num1 + num2;
                }else if (s.equals("-")) {
                    res = num2 - num1;
                }else if (s.equals("*")) {
                    res = num1 * num2;
                }else if (s.equals("/")) {
                    res = num2 / num1;
                }else {
                    throw new RuntimeException("運算符異常！");
                }
                //運算過后將結果又放入棧中
                dataStack.push("" + res);
            }
        }
        //最后返回棧中唯一的數(shù)據(jù)既是結果
        return Integer.parseInt(dataStack.pop());
    }