day06-逆波兰表达式的计算器

目标：完成一个逆波兰表达式的计算器(分为两个步骤)

1. 计算后缀表达式：
2. 中缀表达式转成后缀表达式：

1.计算后缀表达式：

思路：

1. 遍历表达式
2. 遇到数字就压入栈中
3. 遇到运算符就从栈中取出两个数字进行运算。结果放入栈中。
4. 遍历结束，数栈中唯一的值就是结果。

  public static int calculate(List<String> list){
        // 需要一个栈存数字
        Stack<String> num = new Stack<>();
        for (String item : list) {
            if (item.matches("\\d+")){//item是数字的情况
                num.push(item);
            }else {//item 是符号
                int num2 = Integer.parseInt(num.pop());
                int num1 = Integer.parseInt(num.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("符号有误");
                }
                num.push(res+"");//将结果压入栈中
            }
        }
        return Integer.parseInt(num.pop());
    }
}

代码实现：（输入后缀表达式计算结果）

public class PolandNotation {
    public static void main(String[] args) {
        //完成逆波兰表达式
        //(3+4)*5-6  => 3 4 + 5 * 6 -
        String suffixExpression = "3 4 + 5 * 6 -";
        // 借助ArrayList来遍历表达式
        ArrayList<String> listString = getListString(suffixExpression);
        System.out.println(listString);
        System.out.println(calculate(listString));
    }

    //将逆波兰表达式，依次将数据和运算符存入ArrayList中
    public static ArrayList<String> getListString(String suffixExpression){
        String[] split = suffixExpression.split(" ");
        ArrayList<String> list = new ArrayList<>();
        for (String ele : split) {
            list.add(ele);
        }
        return list;
    }

    public static int calculate(List<String> list){
        // 需要一个栈存数字
        Stack<String> num = new Stack<>();
        for (String item : list) {
            if (item.matches("\\d+")){//item是数字的情况
                num.push(item);
            }else {//item 是符号
                int num2 = Integer.parseInt(num.pop());
                int num1 = Integer.parseInt(num.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("符号有误");
                }
                num.push(res+"");//将结果压入栈中
            }
        }
        return Integer.parseInt(num.pop());
    }
}

2.（改进增加） 中缀表达式转成后缀表达式：

1+((2+3)*4)-5   =》 123+4*+5-

1. 初始化两个栈：运算符栈s1 和存储中间过程的栈s2（s2不会出现pop的操作）。
2. 从左向右扫描中缀表达式。
3. 遇到数字的时候直接入s2。
4. 遇到操作符的时候。

• 如果s1为空或者栈顶操作运算符为“（” 的时候直接入栈。
• 否则，优先级比栈顶高 直接压入s1栈中。
• 否则，优先级比栈顶底将s1栈顶操作符弹出压入s2，转到（4）与s1中新的栈顶运算符进行相比较。

5. 遇到扩号的时候

• 如果是“（”，则直接压入s1中。
• 如果是“）”依次弹出s1中的操作符压入s2中，直到遇到“（”，此时将“（”丢弃。

6. 一直重复2-5的操作直到扫描结束。
7. 将s1中剩余的操作符取出并压入s2、
8. 依次弹出s2中的元素并输出。结果就是中缀表达式转后缀表达式的结果。

代码实现：中缀表达式转成后缀表达式

   // 中缀转换为后缀表达式
    public static List<String> parseSuffixExpression(List<String> ls){
        Stack<String> s1 = new Stack<>();
        ArrayList<String> s2 = new ArrayList<>();
        for (String item : ls) {
            if (item.matches("\\d+")){//如果是数字就直接入栈
                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.pop();//消除（
            }else {//符号优先级的情况
                while (s1.size()!=0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)){
                    //如果s1栈中符号优先级大于item就将符号取出放入s2
                    s2.add(s1.pop());
                }
                s1.push(item);
            }
        }
        //将s1剩余的符号存入s2中
        while (s1.size()!=0){
            s2.add(s1.pop());
        }

        return s2;
    }

Operation 类（比较符号优先级）

// 符号类
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 operator){
        int res = 0;
        switch (operator){
            case "+":
                res = ADD;
                break;
            case "-":
                res =  SUB;
                break;
            case "*":
                res =  MUL;
                break;
            case "/":
                res =  DIV;
                break;
            default:
                System.out.println("符号不存在"+operator);
        }
        return res;
    }
}

完整版的逆波兰表达式计算器：（输入中缀表达式计算结果）

public class PolandNotation {
    public static void main(String[] args) {
        // 计算 1+((2+3)*4)-5
        // 1. 中缀表达式先转化为转换为ArrayList
        // 2. 中缀表达式再转为后缀表达式
        // 3. 通过后缀表达式进行计算
        String infixExpression = "1+((2+3)*4)-5";
        // 1. 中缀表达式先转化为转换为ArrayList
        List<String> infixExpressionList = toInfixExpressionList(infixExpression);
        System.out.println("ArrayList 的中缀表达式"+infixExpressionList);
        // 2. 中缀表达式再转为后缀表达式
        List<String> SuffixExpression = parseSuffixExpression(infixExpressionList);
        System.out.println("ArrayList 的后缀表达式"+SuffixExpression);
        // 3. 通过后缀表达式进行计算
        System.out.println("计算结果为："+calculate(SuffixExpression));
    }

    // 中缀转换为后缀表达式
    public static List<String> parseSuffixExpression(List<String> ls){
        Stack<String> s1 = new Stack<>();
        ArrayList<String> s2 = new ArrayList<>();
        for (String item : ls) {
            if (item.matches("\\d+")){//如果是数字就直接入栈
                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.pop();//消除（
            }else {//符号优先级的情况
                while (s1.size()!=0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)){
                    //如果s1栈中符号优先级大于item就将符号取出放入s2
                    s2.add(s1.pop());
                }
                s1.push(item);
            }
        }
        //将s1剩余的符号存入s2中
        while (s1.size()!=0){
            s2.add(s1.pop());
        }
        return s2;
    }

    //将表达式转成list
    public static List<String> toInfixExpressionList(String s){
        List<String> ls = new ArrayList<String>();
        int i = 0;//辅助扫描中缀表达式
        char c ;
        String str = "";
        do{//指针不越界就一直循环
            //通过ASC||来判读是数字还是字符
            if ((c=s.charAt(i))<48 || (c=s.charAt(i)) > 57){//符号直接存入栈中
                ls.add(c+"");
                i++;// 指针后移
            }else {// 数字进行拼接
                str = "";
                // 循环如果下一个是数字就进行拼接
                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 ArrayList<String> getListString(String suffixExpression){
        String[] split = suffixExpression.split(" ");
        ArrayList<String> list = new ArrayList<>();
        for (String ele : split) {
            list.add(ele);
        }
        return list;
    }

    // 后缀表达式的计算
    public static int calculate(List<String> list){
        // 需要一个栈存数字
        Stack<String> num = new Stack<>();
        for (String item : list) {
            if (item.matches("\\d+")){//item是数字的情况
                num.push(item);
            }else {//item 是符号
                int num2 = Integer.parseInt(num.pop());
                int num1 = Integer.parseInt(num.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("符号有误");
                }
                num.push(res+"");//将结果压入栈中
            }
        }
        return Integer.parseInt(num.pop());
    }
}

// 符号类
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 operator){
        int res = 0;
        switch (operator){
            case "+":
                res = ADD;
                break;
            case "-":
                res =  SUB;
                break;
            case "*":
                res =  MUL;
                break;
            case "/":
                res =  DIV;
                break;
            default:
                System.out.println("符号不存在"+operator);
        }
        return res;
    }
}