万能计算器的实现以及源码分析

/**
 * 我们尝试写一个完整版的计算器,由于计算机不能很好的识别括号,所以一般要转换为逆波兰表达式求解
 * 思路解析 :
 * 1. 输入一个 中缀表达式
 * 2. 中缀表达式转化为list存储
 * 3. 把list转换为一个逆波兰表达式
 *      规则如下 首先准备两个栈,stack1 , list2(stack2)
 *      如果是数字直接装入 list2
 *      如果是括号 分为左括号跟右括号
 *         如果是左括号直接进入stack1
 *         如果是右括号 stack1 弹栈 ,弹出的元素进入stack2,直到出现 ')' ,抵消掉一个右括号
 *      如果是操作符
 *          如果stack1 为空 或者是 栈顶为左括号,那么直接入栈          <---------------------------
 *          如果操作符的优先级大于 栈顶 操作符的优先级,直接入栈                                    *
 *          如果操作符的优先级小于等于 栈顶操作符 ,那么就弹出栈顶元素入stack2,然后进入第一条比较 --------
 *
 * 4. 利用逆波兰表达式进行求值
 */
class MyCalculator{
    public static void main(String[] args) {
        String s = "1+ ((2 +3) *4 )-5";
        List<String> infixexperssion = toList(s);
        List<String> suffixexpression = toSuffixexpression(infixexperssion);
        int ret = calculate(suffixexpression);
        System.out.println(ret);
    }

    /**
     * 该方法的作用就是把一个字符串转换为一个中缀表达式的list
     * @param infixexpression : 中缀表达式
     * @return
     */
    public static List<String> toList(String infixexpression){
        List<String> ret = new ArrayList<>();
        int count = 0;
        while(count < infixexpression.length()){
            if(infixexpression.charAt(count) == ' '){
                count++;
                continue;
            }
            if(infixexpression.charAt(count) < '0' || infixexpression.charAt(count) > '9'
                    && infixexpression.charAt(count)!=' '){
                ret.add(infixexpression.charAt(count) + "");
                count++;
            }else{
                StringBuilder stringBuilder = new StringBuilder();
                while(count < infixexpression.length() && infixexpression.charAt(count)>='0'
                        && infixexpression.charAt(count)<='9'){
                    stringBuilder.append(infixexpression.charAt(count));
                    count++;
                }
                ret.add(stringBuilder.toString());
            }
        }
        return ret;
    }


    /**
     * 该方法的作用是将我们的中缀表达式转化为逆波兰表达式
     * @param infixexpression : 传入的中缀表达式
     * @return
     */
    public static List<String> toSuffixexpression(List<String> infixexpression){
        //首先创建两个栈,因为第二个栈不涉及弹栈操作,所以我们可以创建为顺序表
        Stack<String> stack = new Stack<>();
        List<String> list = new ArrayList<>();

        for(String elem : infixexpression){
            if(elem.equals("(")){
                stack.push(elem);
            }else if(elem.equals(")")){
                while(stack.size() != 0 && !stack.peek().equals("(")){
                    list.add(stack.pop());
                }
                stack.pop();
            }else if(isOperator(elem) ){
                if(stack.size() == 0 || stack.peek().equals("(") || priority(elem) > priority(stack.peek())){
                    stack.push(elem);
                    continue;
                }
                while(stack.size() != 0 && priority(elem) <= priority(stack.peek()) && !stack.peek().equals("(")){
                    list.add(stack.pop());
                }
                stack.push(elem);
            }else{
                list.add(elem);
            }
        }
        while(stack.size() != 0){
            list.add(stack.pop());
        }
        return list;
    }

    //判断是否是操作符
    public static boolean isOperator(String elem){
        if(elem.equals("+")||elem.equals("-")||elem.equals("*")||elem.equals("/")){
            return true;
        }
        return false;
    }

    //判断优先级的大小
    public static int priority(String elem){
        if(elem.equals("+") || elem.equals("-")){
            return 1;
        }else{
            return 2;
        }
    }

    /**
     * 最后收一下尾巴,用我们所得到的逆波兰表达式求出值
     * 求值的基本思路应该比较好理解
     * 如果是数字直接入栈,如果不是,弹出两个数字,然后进行运算结果入栈
     */
    public static int calculate(List<String> sufferixexperssion){
        Stack<String> stack = new Stack<>();
        for(String elem : sufferixexperssion){
            if(isOperator(elem)){
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                switch (elem){
                    case "+" :
                        stack.push((num1+num2)+"");
                        break;
                    case "-" :
                        stack.push((num1-num2)+"");
                        break;
                    case "*" :
                        stack.push((num1*num2)+"");
                        break;
                    case "/" :
                        stack.push((num1/num2)+"");
                        break;
                }
            }else{
                stack.push(elem);
            }
        }
        return Integer.parseInt(stack.pop());
    }
}

1. leetcode 150 逆波兰表达式求值

逆波兰表达式又叫做后缀表达式,因为计算机是好辨认出中缀表达式的计算顺序的,所以有时候要用后缀表达式进行求解
题目描述

思路分析:
1.如果是数字,直接入栈
2.如果是操作符,弹出两个数字分别作为右操作数跟左操作数运算,结果入栈
3.最后弹出栈内的最后一个元素
代码实现如下

	public static int evalRPN(String[] tokens) {
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < tokens.length; ++i) {
            String s = tokens[i];
            if (toolOperator(s)) {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                switch (s) {
                    case "+":
                        stack.push((num2 + num1) + "");
                        break;
                    case "-":
                        stack.push((num2 - num1) + "");
                        break;
                    case "*":
                        stack.push((num2 * num1) + "");
                        break;
                    case "/":
                        stack.push((num2 / num1) + "");
                        break;
                }
            } else {
                stack.push(s);
            }
        }
        return Integer.parseInt(stack.pop());
    }

    //判断是不是操作符
    public static boolean toolOperator(String s) {
        if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
            return true;
        }
        return false;
    }