// 说明：用于过滤重复的表达式
// 思路：按顺序层层筛选，由于转换成后缀表达式，不用考虑括号
//   a. 先去除运算过程含负数的
//   b. 先比较结果
//   c. 比较表达式是否一样
//   d. 再比较包含的运算符是否相同
//   e. 比较第一次运算的两数是否只是交换位置
public static List<Equation> filter(List<Equation> list){
        for(int i=0;i < list.size();i++){
            Equation equation = list.get(i);
            //如果运算过程含负数,则跳过
            if(equation.isOf()){
                list.remove(equation);
                //remove会整体前移
                i--;
                continue;
            }
            //和整个list比较
            //标签方便下面层层嵌套能直接goto出来
            flag:
            for(int o=0;o< list.size();o++){
                Equation toCompare = list.get(o);
                //删除后有空位,要跳过
                if(toCompare == null){
                    continue;
                }
                //遇到自己就跳过
                if(equation == toCompare){
                    continue;
                }
                //先比较结果
                if(Math.abs(equation.getResult() - toCompare.getResult()) < 0.000001) {
                    //结果相同,看是否完全一样
                    if(equation.equals(toCompare)){
                        list.remove(equation);
                        //remove会整体前移
                        i--;
                        break flag;
                    }
                    //再比较运算符
                    List<Arithmetic> postfix1 = equation.getPostfix();
                    List<Arithmetic> postfix2 = toCompare.getPostfix();
                    List<Operator> operators1 = equation.getOperators();
                    List<Operator> operators2 = toCompare.getOperators();
                    //有不同运算符就保留
                    if(operators1.size() != operators2.size()){
                        break flag;
                    }
                    for(int j=0;j<operators1.size();j++){
                        if(operators1.get(j) != operators2.get(j)){
                            break flag;
                        }
                    }
 
                    //运算符相同,只比较第一次计算的两数字是否交换位置
                    //找到第一个运算符,取前两个数字
                    List<Operand> operands1 = new ArrayList<>();
                    List<Operand> operands2 = new ArrayList<>();
                    for(int j=0;j<postfix1.size();j++){
                        if(postfix1.get(j) instanceof Operator){
                            operands1.add((Operand) postfix1.get(j-1));
                            operands1.add((Operand) postfix1.get(j-2));
                            break;
                        }
                    }
                    for(int j=0;j<postfix1.size();j++){
                        if(postfix2.get(j) instanceof Operator){
                            operands2.add((Operand) postfix2.get(j-1));
                            operands2.add((Operand) postfix2.get(j-2));
                            break;
                        }
                    }
                    //比较两对数字
                    if((operands1.get(0).equals(operands2.get(0)) || operands1.get(0).equals(operands2.get(1)))
                            && (operands1.get(1).equals(operands2.get(0)) || operands1.get(1).equals(operands2.get(1)))){
                        list.remove(equation);
                        //remove会整体前移
                        i--;
                        break flag;
                    }else{
                        //两对数字不相同,保留
                        break flag;
                    }
                }else{
                    //结果不一样,保留
                    break flag;
                }
            }
 
        }
        return list.stream().toList();
    }


// generate()
// ● 说明：用于生成随机表达式
// ● 思路：通过传参确定此次生成中包含的操作数数量、运算符数量、括号数量、数的范围，然后随机new出各对象，交替拼接操作数和运算符，最后随机添加括号
public static Equation generate(int operandNo, int operatorNo, int bracketsNo
            , int lowEnd, int upEnd){
        Random r = new Random();
        int scope = upEnd - lowEnd;
        List<Arithmetic> arithmetics = new ArrayList<>();
        List<Operand> operands = new ArrayList<>();
        List<Operator> operators = new ArrayList<>();
        List<Brackets> brackets = new ArrayList<>();
 
        try {
            for (int i = 0; i < operandNo; i++) {
                // 操作数类型 自然数(0),真分数(1)
                int type = r.nextInt(10)%2;
                if(0 == type){
                    //生成随机整数
                    operands.add(new Operand(type, r.nextInt(scope) + lowEnd + ""));
                }else if (1 == type){
                    //生成真分数
                    int denominator = r.nextInt(scope) + lowEnd + 1;
                    // 分子 > 0
                    int numerator = r.nextInt(denominator - 1) + 1;
                    String str = numerator + "/" + denominator;
                    operands.add(new Operand(type, str));
                }
            }
 
            for (int i = 0; i < operatorNo; i++) {
                // 除去等号
                int index = r.nextInt(4) + 1;
                operators.add(Operator.getByIndex(index));
            }
 
            for (int i = 0; i < bracketsNo; i++) {
                brackets.add(Brackets.getByIndex(0));
                brackets.add(Brackets.getByIndex(1));
            }
 
            for (int i = 0; i < operands.size(); i++) {
                if(operands.get(i) != null){
                    arithmetics.add(operands.get(i));
                }
                if(i == operands.size()-1){
                    break;
                }
                if(operators.get(i) != null) {
                    arithmetics.add(operators.get(i));
                }
            }

        }catch (Exception e){
            e.printStackTrace();
            return null;
        }
        return new Equation(arithmetics);
    }



// 1.扫描中缀表达式的每一个字符,将数字入列;
// 2.遇到运算符,栈空时直接进栈,栈顶非空时,运算符优先级大于栈顶元素才进栈,
// 否则栈顶元素退栈入列,当前运算符再进栈;
// 3.依次进行直至所有字符操作完毕
// 有括号:
// 1.扫描中缀表达式的每一个字符,将数字入列;
// 2.遇到运算符,栈空时直接进栈,栈顶非空时,运算符优先级大于栈顶元素才进栈,
// 否则栈顶元素退栈入列,当前运算符再进栈;
// 3.遇到左括号,直接进栈,左括号后面的运算符直接进栈,直至遇到右括号;
// 4.遇到右括号时,将栈顶元素依次退栈入列,直到遇到左括号,将左括号退栈,符号操作移动下一位
// 5.重复以上操作,直至所有字符操作完成。
public List<Arithmetic> infixToPostfix(){
        Stack<Arithmetic> stack = new Stack<>();
        List<Arithmetic> postfix = new ArrayList<>();
        for(int start = 0; start < infix.size(); start++){
            //如果是运算符
            if(infix.get(start).priority > 0) {
                //栈空 或 "(" 或 符号优先级>栈顶符号 且 不为")" 直接进栈
                if (stack.isEmpty() || infix.get(start).priority == 3 ||
                        ((infix.get(start).priority > stack.peek().priority) && infix.get(start).priority < 4)) {
                    stack.push(infix.get(start));
                } else if (!stack.isEmpty() && infix.get(start).priority <= stack.peek().priority) {
                    //栈非空 且 符号优先级≤栈顶符号, 出栈; 直到 栈为空 或 遇到了"("
                    while (!stack.isEmpty() && infix.get(start).priority <= stack.peek().priority) {
                        if (stack.peek().priority == 3) {
                            stack.pop();
                            break;
                        }
                        postfix.add(stack.pop());
                    }
                    stack.push(infix.get(start));
                } else if (infix.get(start).priority == 4) {
                    //")",依次出栈直到空栈或遇到第一个"(",此时"("出栈
                    while (!stack.isEmpty()) {
                        if (stack.peek().priority == 3) {
                            stack.pop();
                            break;
                        }
                        postfix.add(stack.pop());
                    }
 
                }
            }else if(infix.get(start).priority == -1){
                postfix.add(infix.get(start));
            }
        }
        while(!stack.isEmpty()){
            postfix.add(stack.pop());
        }
        return postfix;
    }