中缀表达式转换为后缀表达式以及逆波兰计算器

在写代码时，早早遇到过栈：

1. 子程序调用：
   1. 在跳往子程序前，先将下个指令的地址存到堆栈中，直到子程序执行完毕再将地址取出，以回到原来的程序中。
   2. 换句话理解：一个函数中调用另一个函数时，会将这个函数现场保留（压栈），以便于被调用的函数执行完毕后，原函数直接出栈。
2. 处理递归调用：
   1. 和子程序递归的调用类似，除了存储下一个指令的地址外，也将参数、区域变量等数据存入栈中。
3. 表达式转换：如使用中缀表达式转换为后缀表达式，以便于求值；
4. 二叉树的遍历；
5. 图的深度优先遍历搜索；

基于栈的简单计算器

• 中缀表达式–>中缀表达式 ArrayList：依次扫描字符，是字符直接入链表，否则拼接整个整数出来

  • 在ASCII表中 0-9的ASCII码为48-57
  • Java字符串遍历中s.charAt(i)可以快速指定位置的字符

• 中缀表达式List –>后缀表达式：

  • 创建操作符栈s1，和临时结果栈s2（此处使用List，方便后续计算）
  • 依次扫描表达式，数字则入s2，
  • 考虑( )
  • 在s1非空时，将s1中优先级高的出栈，压栈到s1。可能会遗忘非空条件，因为这步操作目的是将此前优先级高的操作符取出。

• 后缀表达式（逆波兰表达式）计算

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

public class PolandNotation {
    public static void main(String[] args) {
        //后缀表达式
        String suffixExpression = "4 5 * 8 - 60 + 8 2 / +";

        List<String> list = getListString(suffixExpression);
        System.out.println("rpnList= " + list);
        int res = calculate(list);
        System.out.println("the Result = " + res);

        System.out.println("========请输入中缀表达式，俺们自动计算=========");
        Scanner sc = new Scanner(System.in);
        String expression = sc.next();
        List<String> expList = toExpressionList(expression);
        List<String> suffixExpList = parseSuffixExpressionList(expList); //此处转换为后缀表达式
        int res2 = calculate(suffixExpList);
        System.out.println("Great, your expression Result = " + res2);
    }


    //中缀表达式list --》 后缀表达式list
    public static List<String> parseSuffixExpressionList(List<String> ls){
        //1. 定义栈
        Stack<String> s1 = new Stack<>(); //符号栈
        //注意 s2栈 在处理过程中 不需要pop 而是在完成后 用于后缀表达式计算
        //所以不用Stack
        List<String> s2 = new ArrayList<>(); //存储中间结果

        //遍历ls
        for (String item : ls){
            if (item.matches("\\d+")){ //如果是一个数 直接加入s2
                s2.add(item);
            }else if (item.equals("(")){
                s1.push(item);
            }else if (item.equals(")")){
                //")" 需要依次将s1中栈顶运算符依次弹出，，并压入s2，直至“（”
                while (!s1.peek().equals("(")){
                    s2.add(s1.pop()); //将s1中的运算符依次压入s2
                }
                s1.pop(); //弹出小括号
            }else {
                //上面解决了 数字直接压入s2 、
                //当item 优先级小于等于 s1 栈顶的运算符 时，s1.pop()并加入s2中，item继续与s1.peek()比较
                //换句话说，运算符 优先级高的优先入s2（中间结果）
                while (s1.size() != 0 && Operation.getVlaue(s1.peek()) >= Operation.getVlaue(item)){
                    //运算符栈 中 >= 表达式中的这个时 将s1中的操作符 存入s2中
                    s2.add(s1.pop());
                }
                s1.push(item); //否则或结束后，将 本次遍历的item存入s1
            }
        }// end forloop ls
        //遍历完毕表达式后，将s1中剩余的运算符弹出并加入s2
        while (s1.size() != 0){
            s2.add(s1.pop());
        }
        return s2; //因为我们存放的是List数据结构 ,直接按照顺序输出即可
    }

    //表达式（字符串） 转 List
    /*
    利用s1存储运算符，s2临时存储数。 注意优先级高的先压入栈s2
    */
    public static List<String> toExpressionList(String s){
         //list存放中缀表达式内容
        List<String> ls = new ArrayList<>();
        int i = 0; //遍历中缀表达式字符串 指针
        String str; //用于对多位数拼接
        char c; //遍历到字符
        do{
            if ((c=s.charAt(i)) < 48 || (c=s.charAt(i)) > 57){
                //若c不是数字
                ls.add("" + c);
                i++;
            }else { //若 c为数字
                str = ""; //在ASCII中 0【48】 -- 9【57】
                while (i < s.length() && (c=s.charAt(i)) >= 48 && (c=s.charAt(i)) <= 57){
                    str += c; //拼接数字成整体
                    i++;
                }
                ls.add(str);
            }
        }while (i < s.length());

        return ls;
    }

    //将字符串表达式中 数字、运算符 放入ArrayList中
    public static List<String> getListString(String suffixExpression){
        //分割字符串
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<>();
        for (String ele : split){
            list.add(ele);
        }
        return list;
    }

    //对逆波兰表达式（后缀表达式）运算
    public static int calculate(List<String> ls){
        //申请一个栈
        Stack<String> stack = new Stack<String>();
        for (String item : ls){
            //使用正则表达式取出数
            if (item.matches("\\d+")){ //匹配 数 则入栈
                stack.push(item);
            }else{ //否则为操作符 需要pop出两个数
                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 {
                    //System.out.println("Sorry, we DONOT support the operator now!");
                    throw new RuntimeException("Sorry, we DONOT support the operator now!");
                }
                stack.push("" + res); //将计算解决压栈
            }// end num cal
        }//end for loop of ls
        return Integer.parseInt(stack.pop()); //最后栈中的值为结果。
    }
}