Java中缀转后缀再计算

一、将字符串放入List集合中，便于处理，主要在于处理多位数字
如：将3+2{1+2[-4/(8-6)+7]} 变为 [3, +, 2, *, {, 1, +, 2, *, [, -, 4, /, (, 8, -, 6, ), +, 7, ], }]
二、处理List集合 得到中缀表达式[3, +, 2, *, (, 1, +, 2, *, (, 0, -, 4, /, (, 8, -, 6, ), +, 7, ), )]
1.将全部的中括号大括号，转换成小括号
2.将全部负数前添加零。如果是第一个符号为“-”，或者“-”前为“{[(”的话为负号，需要处理。
三、中缀转后缀
四、用后缀表达式计算结果

中缀转后缀

1) 初始化两个栈：运算符栈 s1 和储存中间结果的栈 s2；
（程序里只初始化了栈s1,s2是List集合，因为不会对s2有pop操作，所以集合方便，最后也不用逆序输出，直接输出就好）
2) 从左至右扫描中缀表达式；
3) 遇到操作数时，将其压 s2；
4) 遇到运算符时，比较其与 s1 栈顶运算符的优先级：
1.如果 s1 为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
2.否则，若优先级比栈顶运算符的高，也将运算符压入 s1；
3.否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到(4-1)与 s1 中新的栈顶运算符相比较；
（这里程序的写法是，如果栈不为空且当前值优先级<栈内符号时，一直pop栈中元素，由于是一直，所以用while。
否则，也就是不存在优先级比当前大，或者栈空时，将当前符号压入栈中）
5) 遇到括号时：
(1) 如果是左括号“(”，则直接压入 s1
(2) 如果是右括号“)”，则依次弹出 s1 栈顶的运算符，并压入 s2，直到遇到左括号为止，此时将这一对括号丢弃
6) 重复步骤 2 至 5，直到表达式的最右边
7) 将 s1 中剩余的运算符依次弹出并压入 s2
8) 依次弹出 s2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（List不用逆序）

后缀表达式的计算器很简单
从左至右扫描，遇到数压入数栈，遇到符号，弹出栈顶的两个元素，运算，将结果入数栈（注意是后出栈的—+*/先出栈的）

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String expression=sc.nextLine();
        //1.把字符串放入List中，好处理
        Main my=new Main();
        List<String> mid=my.midExpre(expression);
        List<String> middle=my.change(mid);
        //System.out.println(middle);
        //2.中缀变后缀
        List<String> last=my.lastExpre(middle);
        /*System.out.println(last);*/
        //3.后缀运算结果
        int num=my.calculate(last);
        System.out.println(num);
    }

    public int calculate(List<String> last) {

        Stack<String> st=new Stack<>();
        for(String item:last){
            if(item.matches("\\d+")){
                st.push(item);
            }
            else{
                int s2=Integer.parseInt(st.pop());
                int s1=Integer.parseInt(st.pop());
                int num=0;
                if(item.equals("+")){
                    num=s1+s2;
                }
                if(item.equals("-")){
                    num=s1-s2;
                }
                if(item.equals("*")){
                    num=s1*s2;
                }
                if(item.equals("/")){
                    num=s1/s2;
                }
                st.push(num+"");//算了一通要把结果入栈啊！！
            }

        }
        return Integer.parseInt(st.pop());
    }

    //2.此函数用来中缀变后缀
    public List<String> lastExpre(List<String> middle) {//别忘了<String>，否则增强for出错
        //1.按步骤，一个栈（符号），一个List集合（不出只往中放）
        Stack<String> s1=new Stack<>();
        List<String> s2=new ArrayList<>();
        //2.用增强for遍历List
        //3.如果是数、符号、括号
        for(String item:middle){
            if(item.matches("\\d+")){//用正则表达式判断是否为数字
                s2.add(item);//是数字放入f2
            }
            else if(item.equals("(")){
                s1.push(item);
            }
            else if(item.equals(")")){
                while(!s1.peek().equals("(")){//用equals，不要用成==了
                    s2.add(s1.pop());
                }
                s1.pop();//把"("丢弃掉
            }
            else{//如果是运算符的话，此处易错，若优先级低，则不断pop用while,不能只pop一次
                             //且不能忘记pop完后要入栈的。这个写法是最简洁的
                while(s1.size()!=0&&Main.getVal(item)<=Main.getVal(s1.peek())){
                    s2.add(s1.pop());
                }
                s1.push(item);
            }
        }
        while(s1.size()!=0){
            s2.add(s1.pop());
        }
        return s2;
    }

    //创建一个函数，返回各个符号的数值，以能比较优先级
    private static int getVal(String item) {//没有break造成了错误
        int i=0;
        switch(item){
        case "+":
            i=1;
            break;
        case "-":
            i=1;
            break;
        case "*":
            i=2;
            break;
        case "/":
            i=2;
            break;
        default:
            break;
        }
        return i;
    }
    //1.此函数用来把字符串放入List中，好处理。 1+((2553+3)×4)-5=>[1, +, (, (, 2553, +, 3, ), ×, 4, ), -, 5]
    public List<String> midExpre(String expression) {
        List<String> list=new ArrayList<>();
        int i=0;
        String str="";//拼接数字用
        while(i<expression.length()){
            //情况分为是数字，不是数字。不是数字直接加入List
            //数字的ASCII是 a-z:97-122,A-Z:65-90,0-9:48-57,也可以用isDigit
            if(!Character.isDigit(expression.charAt(i))){
                list.add(expression.charAt(i)+"");
                i++;
            }
            else{
                str="";
                //当是数字时就一直拼接，用while
                while(i<expression.length()&&Character.isDigit(expression.charAt(i))){
                    str=str+expression.charAt(i);
                    i++;
                }
                list.add(str);
            }
        }
        return list;
    }

        //处理List变成想要的中缀表达式
        private List<String> change(List<String> mid) {
        for(int i=0;i<mid.size();i++){
            String str=mid.get(i);
            if(str.equals("[")||str.equals("{")){
                mid.set(i,"(");
                System.out.println(mid.get(i));
            }
            else if(str.equals("]")||str.equals("}")){
                mid.set(i,")");
            }
            if(str.equals("-")){
                if(i==0){
                    mid.add(0,"0");
                }
                else if(mid.get(i-1).equals("(")){
                    mid.add(i,"0");
                }
            }
        }
        return mid;
    }
}

代码结束
关于处理括号和负号，还可以用正则表达式处理，应该是简单一些的
直接处理字符串

private String change(String exp) {//中括号特殊字符正则表达式
        exp=exp.replaceAll("(?<![0-9)}\\]])(?=-[0-9({\\[])", "0");
        exp=exp.replaceAll("[\\[]","(");
        exp=exp.replaceAll("[\\]]",")");
        exp=exp.replaceAll("[\\{]","(");
        exp=exp.replaceAll("[\\}]",")");
        System.out.println(exp);
        return exp;    
    }

作为一个菜鸡，我还不是很明白正则表达式的规则
注意replaceAll的用法，[]{}是特殊字符，要加\\