栈的应用之逆波兰计算器练习

文章目录

• 创建操作运算符的类
• 计算器

创建操作运算符的类

public 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:
                break;
        }
        return result;
    }
}

计算器

逆波兰表达式，在逆波兰记法中，所有操作符置于操作数的后面，所以逆波兰表示又称后缀表达式。逆波兰记法不需要括号来标识操作符的优先级。

将中缀表达式转成后缀表达式

将中缀表达式转后后缀表达式需要用到两个栈，一个是符号栈，一个是结果栈。
先将表达式转成List类型（我这里表达式写的是String类型，转成List好操作）

    //将中缀表达式转成list，拆分中缀表达式
    public static List<String> toInfixExpressionList(String s){
        ArrayList<String> expression = new ArrayList<String>();
        int i = 0;   //用于遍历中缀表达式
        String keepNum = "";  //用于拼接多位数
        char ch;   //存放遍历得到的符号和数
        do{
            if((ch = s.charAt(i)) < 48 || (ch = s.charAt(i)) > 57){   //如果不是数字
                expression.add("" + ch);
                i++;
            }else{  //如果是数字的话，就要考虑多位数的问题了
                keepNum = "";   //要把keepNum置成空串，这部需要注意
                while(i < s.length() && (ch = s.charAt(i)) >= 48 && (ch = s.charAt(i)) <= 57){
                    keepNum += ch;
                    i++;
                }
                expression.add(keepNum);
            }
        }while(i < s.length());
        return expression;
    }

然后就可以进行转换了，举例：

从左往右扫描中缀表达式，扫描到第一个是"("，直接压入符号栈

继续扫描，扫描到数字，直接入结果栈

继续扫描，扫描到"+"，由于符号栈栈顶是"("，不需要比较运算符优先级，直接将"+“压入符号栈中

继续扫描，遇到数字2，直接压入栈中

继续扫描，遇到”)"，弹出符号栈中的运算符压入结果栈中去，直到遇到"("，同时将此时符号栈栈顶的"(“弹出，一对括号就消除掉了

继续扫描，扫描到”*"，此时符号栈为空，可以直接压入符号栈中

继续扫描，数字直接压入结果栈中

继续扫描，遇到运算符"+"，此时符号栈不为空，此时需要和符号栈栈顶的运算符进行优先级的比较，如果此时运算符的优先级大于符号栈栈顶运算符的优先级可以直接将该运算符压入符号栈，否则需要将符号栈栈顶的运算符压入结果栈中，再次与符号栈栈顶的运算符进行比较，反复上述操作，直到优先级大于符号栈栈顶运算符的优先级，就将该运算符压入符号栈中。

继续扫描，是数字，直接压入结果栈
扫描结束，将符号栈中的运算符依次压入结果栈中

将结果栈中的元素依次弹出，结果的逆序就是后缀表达式

    public static List<String> toSuffixExpreesionList(String infixExpression){
        List<String> s = toInfixExpressionList(infixExpression);
        Stack<String> s1 = new Stack<>();    //符号栈
        List<String> s2 = new ArrayList<>();    //存储结果的栈，因为逆序的结果的后缀表达式，所以直接用List不需要再次逆序拿出来
        for(String item : s){
            //如果是一个数,直接入栈
            if(item.matches("\\d+")){
                s2.add(item);
            }else{
                if(s1.isEmpty() || s1.peek() == "("){ //如果栈为空或者栈顶是"("，符号直接入栈
                    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(item) <= Operation.getValue(s1.peek())){
                        //如果item的优先级小于s1栈顶的优先级，就将符号栈栈顶的运算符压入s2中
                        s2.add(s1.pop());
                    }
                    s1.push(item);  //最后将item压入符号栈中
                }
            }
        }
        //将符号栈中剩余的运算符压入最后的结果栈中
        while(!s1.isEmpty()){
            s2.add(s1.pop());
        }
        return s2;
    }

计算器实现

计算器的实现只需要一个站
依次扫描后缀表达式，数字直接压入栈中，遇到运算符从栈中压入两个数进行运算，将结果再次压入栈中，继续扫描

    public static int PolandNotationcalculator(String expression){
        List<String> list = toSuffixExpreesionList(expression);
        Stack<String> stack = new Stack<>();
        for(String item : list){
            if(item.matches("\\d+")){  //如果是数字，则直接入栈
                stack.push(item);
            }else{                      //如果是运算符，从栈中弹出两个数进行运算，将运算结果再次压入栈中
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int result = 0;
                if(item.equals("+")){
                    result = num1 + num2;
                }else if(item.equals("-")){
                    result = num1 - num2;
                }else if(item.equals("/")){
                    result = num1 / num2;
                }else if(item.equals("*")){
                    result = num1 * num2;
                }else{
                    throw new RuntimeException("符号错误");
                }
                stack.push("" + result);
            }
        }
        return Integer.parseInt(stack.pop());
    }