中缀转后缀

后缀表达式

也叫逆波兰表达式，将运算符写在操作符之后

中缀形式：(10+20/2*3)/2+8

后缀形式：10 20 2 / 3 * + 2 / 8 +

方便计算机计算，但对用户不友好

中缀转后缀

public class infixToSuffix {
    public static void main(String[] args) {
        String expression = "(10+20/2*3)/2+8";
        expression =  infixToSuffix(expression);
        System.out.println(expression);


    }
    public static String infixToSuffix(String expression){
        //操作符的栈
        ArrayStack<String> opStack = new ArrayStack<>();
        //后缀表达式的线性表
        ArrayList<String > suffixList = new ArrayList<>();
        //格式化表达式
        expression = insertBlanks(expression);
        String [] tokens = expression.split(" ");
        for (String token : tokens){
            //过滤空串
            if (token.length()==0){
                continue;
            }
            //判断操作符+—-*/
            if (isOperator(token)){
                /*
                什么时候操作符进栈？
                1如果栈为空
                2.如果栈顶是（
                3.如果栈顶是操作符，且优先级比当前token小
                什么时候需要将栈顶操作符出栈？
                1.栈顶操作符的优先级>=当前token
                 */
                while (true) {
                    if (opStack.isEmpty() || opStack.peek().equals("(") || priority(opStack.peek()) < priority(token)) {
                        opStack.push(token);
                        break;
                    }
                    suffixList.add(opStack.pop());
                }
            }else if (token.equals("(")){
                opStack.push(token);
            }else if (token.equals(")")){
                while (!opStack.peek().equals("(")){
                    suffixList.add(opStack.pop());
                }
                opStack.pop();
            }else if (isNumber(token)){
                suffixList.add(token);
            }else {
                throw new IllegalArgumentException("wrong char:"+expression);
            }
        }
        while (!opStack.isEmpty()){
            suffixList.add(opStack.pop());
        }
        //将数字元素和操作元素进行拼接
        StringBuilder sb = new StringBuilder();
        for (int i = 0;i<suffixList.size();i++){
            sb.append(suffixList.get(i));
            sb.append(' ');
        }
        return sb.toString();
    }

    private static int priority(String token) {
        if (token.equals("+")||token.equals("-")){
            return 0;
        }
        if (token.equals("*")||token.equals("/")){
            return 1;
        }
            return -1;

    }

    private static boolean isNumber(String token) {
        return token.matches("\\d+");//\d代表数字 +一个起步
    }

    private static boolean isOperator(String token) {
        return token.equals("+")||token.equals("-")||token.equals("*")||token.equals("/");
    }

    private static String insertBlanks(String expression){
        StringBuilder sb = new StringBuilder();
        for (int i = 0;i<expression.length();i++){
            char c = expression.charAt(i);
            if (c=='('||c==')'||c=='+'||c=='-'||c=='*'||c=='/'){
                sb.append(' ');
                sb.append(c);
                sb.append(' ');
            }else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

后缀计算器

//后缀计算器
public class SuffixCalculator {
    public static void main(String[] args) {
        String infixExpression = "(10+20/2*3)/2+8";
        String suffixExpression =infixToSuffix.infixToSuffix(infixExpression);
        int reuslt = evaluateSuffix(suffixExpression);
        System.out.println(reuslt);
    }

    private static int evaluateSuffix(String expression) {
        ArrayStack<Integer> stack = new ArrayStack<>();
        String [] tokens = expression.split(" ");
        for (String token :tokens){
            if(token.length()==0){
                continue;
            }
            if (isNumber(token)){
                stack.push(new Integer(token));
            }else{
                processAnOperator(stack,token);
            }
        }
        return stack.pop();
    }

    private static boolean isNumber(String token) {
        return token.matches("\\d+");
    }

    private static void processAnOperator(ArrayStack<Integer> stack, String token) {
    int num1 = stack.pop();
    int num2 = stack.pop();
    if (token.equals("+")){
        stack.push(num2+num1);
    }else if (token.equals("-")){
            stack.push(num2-num1);
        }else if (token.equals("*")){
            stack.push(num2*num1);
        }else if (token.equals("/")){
            stack.push(num2/num1);
        }

    }
}