逆波兰式的转换与计算

第一步：中缀表达式转后缀表达式

转换规则：

第二步：后缀表达式计算得值

计算规则：

代码实现：

package calculator;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class CalculatoDemo {
    public static void main(String[] args) {
        String origin = "2+4+5*2-3/1";
        System.out.println(infixToList(origin));
        System.out.println(infixTOSufix(infixToList(origin)));
        System.out.println(Calculator(infixTOSufix(infixToList(origin))));
    }

    private static List infixToList(String origin) {
        List list = new ArrayList<>();
        int i = 0;   //定义一个指针变量，用于遍历字符串
        StringBuilder str; //定义一个字符串，用于字符串拼接
        char c;//定义一个字符，用于接收每次遍历的字符
        while (i < origin.length()) {
            if ((c = origin.charAt(i)) < 48 || (c = origin.charAt(i)) > 57) {  //如果c不是数字
                list.add("" + c);
                i++;
            } else {
                str = new StringBuilder();
                while (i < origin.length() && (c = origin.charAt(i)) >= 48 && (c = origin.charAt(i)) <= 57) {
                    str.append(c);
                    i++;
                }
                list.add(str.toString());
            }
        }
        return list;
    }

    private static List infixTOSufix(List ls) {
        //定义两个栈
        Stack operStack = new Stack<>();
        List templist = new ArrayList<>();//由于第二个栈没有pop操作，且结果要将要逆序输出，这里直接用List代替
        for (String item : ls) {
            if (item.matches("\d+")) {   //若是操作数则直接入templist
                templist.add(item);
            } else if (item.equals("(")) {   //如果是“（”则直接入operStack栈
                operStack.push(item);
            } else if (item.equals(")")) {   //若是“）”，则弹栈至“（”
                while (!operStack.peek().equals("(")) {
                    templist.add(operStack.pop());
                    operStack.pop();
                }
            } else {
                while (operStack.size() != 0 && judgePriority(item) <= judgePriority(operStack.peek())) {
                    templist.add(operStack.pop());
                }
                operStack.push(item);
            }
        }
        while (operStack.size() != 0) {
            templist.add(operStack.pop());
        }
        return templist;
    }

    private static int judgePriority(String value) {
        return (value.equals("*") || value.equals("/")) ? 2 : 1;
    }
    private static int Calculator(List list){
        Stack stack = new Stack<>();
        int i =0; //定义指针遍历集合
        for (String item:list
             ) {
            if (item.matches("\d++")){
                stack.push(item);
            }else {
                stack.push(Operation(stack.pop(),stack.pop(),item)+"");
            }
        }
        return Integer.parseInt(stack.pop());
    }
    private static int Operation(String a,String b,String c){
        int y = Integer.parseInt(a);
        int x = Integer.parseInt(b);
        return c.equals("+")?x+y:c.equals("-")?x-y:c.equals("*")?x*y:x/y;
    }
}

运行结果：