java实现中缀表达式转后缀表达式（逆波兰计算器）

java实现中缀表达式转后缀表达式（逆波兰计算器） 思路：

步骤：

 1定义一个list容器用于存放中缀表达式的内容，便于遍历

2准备两个栈s1，s2。s1表示符号栈，s2用于存储中间结果，由于s2没有进行pop（） *** 作，并且需要逆序输出，所以用list就好。

3进行中缀表达式转后缀表达式：

1）如果是数字直接入s2

2）如果是“（”直接入s1

3）如果是")“则需要不断pop出s1中的 *** 作符直到栈顶是”（“，注意最后要舍弃掉”（“

4)如果运算符则：

                        a：如果栈空或者栈顶为“（”，直接加入

                        b: 如果运算符小于等于栈顶运算符的优先级，则需要不断pop出s1到s2中

                        c: 如果运算符大于栈顶运算符优先级则直接加入s1

5）如果s1不为空，则依次pop到s2中

4从左到右依次扫描后缀表达式，新建一个栈，如果是数字就压入栈，如果遇见运算符则d出栈顶和次栈顶的两个数进行计算，并把计算结果压入栈中

5栈顶就是最终计算结果

代码：

public class Calculator01 {
    public Calculator01() {
    }
    //1先把中缀表达式转化为后缀表达式
    //1.1先把中缀表达式中数字和 *** 作符分离出来放进List中便于遍历
    //当进行遍历时主要遇到的问题1
    //下标越界问题（在拼接数字时），因为我们总是需要判断当前字符的下一位是否是数字，那么当遍历到最后一个字符时，便会发生越界异常
    //解决方法： while (i splitexpression(String expression) {
        List list=new ArrayList();
        String res="";//用于拼接保存的数字，比如100
        char c=' ';//用于保存 *** 作符
        for (int i = 0; i  infixTranslatePostFix(List list) {
        Stack s1=new Stack<>();
        ArrayList s2=new ArrayList<>();
        for (String item:
             list) {
            //如果是数字就直接入s2
            if(item.matches("\d+")) {
                s2.add(item);
            }
            //()的处理
            else if(item.equals("(")) {s1.push(item);}
            else if(item.equals(")")) {
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop();//丢弃s1中的（
            }
            // *** 作符的处理
            else {
                //栈为空时，直接加入
                if(s1.empty()||s1.peek().equals("(")) {
                    s1.push(item);
                }
                //运算符优先级《=栈顶时
                else if(ComparePriority.priority(item)<=ComparePriority.priority(s1.peek())) {
                    while (!s1.empty()&&ComparePriority.priority(item)<=ComparePriority.priority(s1.peek())) {
                        s2.add(s1.pop());
                    }
                    s1.push(item);
                }
                else {
                    s1.push(item);
                }
            }


        }
        //如果s1不为空就把其中的操作符依次添加到s2
       while (s1.size()>0) {
           s2.add(s1.pop());
       }
        //现在s2中正序就是后缀表达式了
        List postFixList=new ArrayList<>();
        for (String item:
             s2) {
            postFixList.add(item);
        }
        return postFixList;
    }


    public  int calculate(String expression) {
        List list=this.infixTranslatePostFix(this.splitexpression(expression));
        int res=0;
        Stack s=new Stack<>();
        //从左到右依次扫描list，遇到数字就压栈，遇见运算符接从栈中d出两个数进行相应的计算
        for (String item:
             list) {
            if(item.matches("\d+")) {
                s.push(Integer.parseInt(item));
            }
            else {
                int num1=s.pop();
                int num2=s.pop();
                if(item.equals("*")) {
                    res=num1*num2;
                }
                else if(item.equals("/")) {
                    res=num2/num1;
                }
                else if(item.equals("-")) {
                    res=num2-num1;
                }
                else if(item.equals("+")) {
                    res=num2+num1;
                }
                else {
                    System.out.println("运算符有误");
                }
                s.push(res);
            }
        }
        return s.peek();
    }


}
//该类用于比较 *** 作符的优先级
class ComparePriority{
    public static int priority(String s) {
        if(s.equals("*")||s.equals("/")) {
            return 2;
        }
        else if(s.equals("+")||s.equals("-")) {
            return 1;
        }
        else return 0;
    }
}