图解中缀表达式转后缀表达式及后缀表达式求值

- * + 3 4 5 6

1.通过一个index值（索引），来遍历表达式；
2.如果发现是一个数字，就直接入数栈；
3.如果发现扫描到的是一个符号，分如下情况：
 3.1如果发现当前的符号栈为空，直接入栈；
 3.2如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或等于栈中的操作符，就需要从数栈中pop出两个数（这里注意如果是减法和除法，次顶元素作为被减数或被除数，与前缀表达式相反），再从符号栈中pop出一个符号，进行运算，将得到的结果入数栈，然后操作符入符号栈；如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈。
4.当表达式扫描完毕，就顺序从数栈中和符号栈中pop出相应的数和符号，并运算。
5.最后在数栈只有一个数字，就是表达式的结

1.扫描表达式，如果是数直接入栈；
2.如果是运算符，从栈中弹出两个数进行运算，然后将结果入栈；
3.最后栈中剩余的一个值即为表达式的值

3 4 + 5 * 6 -

1.初始化两个栈：运算符栈s1和中间结果栈s2；2.从左到右扫描中缀表达式；3.遇到操作数时，将其压入s2；4.遇到运算符时，比较其与s1栈顶运算符的优先级；4.1.如果s1为空，或运算符栈顶为左括号“（”，则直接将此运算符入栈；4.2.否则，若优先级比栈顶运算符的高，也将运算符压入s1（注意必须是高，等于或低于都不行） 4.3.否则，将s1栈顶的运算符弹出并压入s2中，再次转到4.1与s1中新的栈顶运算符进行比较；5.遇到括号时：5.1.如果是左括号“（”，则直接压入s1；5.2.如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃；6.重复步骤2-5，直到表达式的最右边；7.将s1中剩余的运算符依次弹出并压入s2；8.依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

s2弹出顺序：- 5 + * 4 + 3 2 1 
逆序，即后缀表达式：1 2 3 + 4 * + 5 -

public static List<String> infixExpression2List(String infixExpression) {
    ArrayList<String> ls = new ArrayList<String>();
    int i = 0;
    String str;//对多位数进行拼接
    char ch;//每遍历到一个字符，就放入ch
    do {
        //如果ch是一个非数字，加入ls
        if ((ch = infixExpression.charAt(i)) < 48 || (ch = infixExpression.charAt(i)) > 57) {
            ls.add("" + ch);
            i++;
        } else {
            str = "";//先将str置空
            //这里判断i的范围是因为内层循环结束后才会判断外层循环条件，如果不加会在内层循环时出现下标越界
            while (i < infixExpression.length() && (ch = infixExpression.charAt(i)) >= 48 && (ch = infixExpression.charAt(i)) <= 57) {
                str += ch;//拼接多位数
                i++;
            }
            ls.add(str);
        }
    } while (i < infixExpression.length());
    return ls;
}

class Operation {
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;


    public static int getValue(String operation) {
        int result = 0;
        switch (operation) {
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                System.out.println("不存在的运算符");
                break;
        }
        return result;
    }
}

public static List<String> infix2SuffixExpressionList(List<String> infixList) {
    Stack<String> s1 = new Stack<String>();//操作符栈
    //由于在整个转换过程中s2栈都没有pop操作，而且后面需要逆序输出，为了简化，可以不用栈结构，改用List<String> s2代替
    List<String> s2 = new ArrayList<String>();




    //遍历infixList
    for (String item : infixList) {
        //如果是一个数，则入s2
        if (item.matches("\\d+")) {
            s2.add(item);
        } else if (item.equals("(")) {//如果是左括号，直接入s1栈
            s1.push(item);
        } else if (item.equals(")")) {//如果是右括号，则依次弹出s1栈顶的运算符，并加入s2，直到遇到左括号为止，此时将这一对括号丢弃；
            while (!s1.peek().equals("(")) {
                s2.add(s1.pop());
            }
            s1.pop();//去除s1中对应的左括号，很重要！！！
        } else {
            //如果是运算符，比较其与s1栈顶运算符的优先级：
            //1.如果s1为空，或运算符栈顶为左括号“（”，则直接将此运算符入栈；
            //2.否则，若优先级比栈顶运算符的高，也将运算符压入s1（注意必须是高，等于或低于都不行）
            //3.否则，将s1栈顶的运算符弹出并压入s2中，再次转到4.1与s1中新的栈顶运算符进行比较；
            //当item的优先级小于等于s1栈顶的优先级时，将s1栈顶的运算符弹出并加入s2中，再次转到1与s1中新的栈顶运算符进行比较
            while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
                s2.add(s1.pop());
            }
            //将item入栈s1
            s1.push(item);
        }
    }
    //将s1中的剩余运算符弹出并加入s2
    while (s1.size() != 0) {
        s2.add(s1.pop());
    }
    return s2;//由于加入的是一个List，本身有序，所以正常输出即为后缀表达式而不必逆序
}

public static int calculator(List<String> ls){
   Stack<String> stack = new Stack<String>();
   //遍历ls
   for (String item : ls) {
       if (item.matches("\\d+")){//如果是数直接入栈
           stack.push(item);
       }else{
           int num2=Integer.parseInt(stack.pop());
           int num1=Integer.parseInt(stack.pop());
           int res=0;
           if (item.equals("+")){
               res=num1+num2;
           }else if (item.equals("-")){//后缀表达式用后取出的数-先取出的数
               res=num1-num2;
           }else if (item.equals("*")){
               res=num1*num2;
           }else if(item.equals("/")){
               res=num1/num2;
           }else{
               throw new RuntimeException("运算符有误");
           }
           stack.push(res+"");
       }
   }
   //栈最后剩下的数即为运算结果
   return Integer.parseInt(stack.pop());
}