/**
 * Created With IntelliJ IDEA.
 * Descriptions:
 * 1、定义一个栈stack，用来接收运算符；定义一个char类型数组chars，用于接收输出结果
 * 2、从左到右遍历字符串，遇到字符添加到输chars，遇到运算符栈为空入栈，不为空，
 * 当前运算符A和栈顶运算符B比较，如果A的优先级大于B，那么A入栈，否则A出栈，并添加到chars，B入栈
 * 3、遇到左括号入栈，右括号则进行出栈操作，直到匹配到左括号，出栈结束
 * 4、将栈中剩余元素加入到chars中
 * User:Mr.Du
 * Date:2021/6/19
 * Time:21:22
 */

 

 

/**
     *
     * @param s        输入表达式
     * @param stack   存储操作符和括号
     * @return
     */
    public static String infixToPostFix(String s, Stack<Character> stack){
        int index = 0;
        char[] tmp = s.toCharArray();
        char[] chars = new char[s.length()];
        for(int i = 0;i < s.length();i++){
//            (a+b)*c+d*(e+f)
            if(tmp[i] >= '0' && tmp[i] <= '9'){
                chars[index++] = tmp[i];
            }else if(tmp[i] == '('){
                stack.add(tmp[i]);
            }else if(tmp[i] == '+' || tmp[i] == '-'
                        || tmp[i] == '*'
                        || tmp[i] == '/'){
                if(!stack.isEmpty()){
                    char c = stack.peek();
                    if(c == '('){
                        stack.push(tmp[i]);
                    } else if(getPriority(tmp[i],c)){
                        stack.push(tmp[i]);
                    }else{
                        chars[index++] = c;
                        stack.pop();
                        stack.push(tmp[i]);
                    }
                }else{
                    stack.push(tmp[i]);
                }

            }else if(tmp[i] == ')'){
                char c;
                while((c = stack.pop()) != '('){
                    chars[index++] = c;
                }

            }
        }
        while(!stack.isEmpty()){
            chars[index++] = stack.pop();
        }
        return String.valueOf(chars);
    }

    /**
     * 比较算术运算符大小
     * @param a
     * @param b
     * @return   true代表a的优先级高于b
     */
    public static boolean getPriority(char a,char b){
        if((a == '*' || a == '/') && (b == '+' || b == '-')) return true;
        return false;
    }