数据结构和算法【45】计算器

皮皮克克 2023-09-14

163

点击关注公众号，干货第一时间送达

这绝对是一道非常非常经典的题，

同样也是一道面试题。

喏~

原谅小编没钱充会员的，

是哪些企业的面试题，小编目前也不知

一起来看看。

原题链接：

https://leetcode.cn/problems/calculator-lcci/description/

一、屏幕前的吴彦祖和刘亦菲们，请听题

举个例子：

这道题里面的字符，不包含括号。

然后用队列即可计算完成。

如果小编给加点难度呢？

字符串中可以有括号：

请问阁下如何应对？

小编下面提供的解法，可以解力扣上面的这题，

也可以解出刚才的扩展，也就是字符串里面有括号。

二、解题

表达式运算，考虑加减乘除的优先级，用队列可以完成。

但是如果有括号，那么括号里面的优先级，

是高于外部的。

肯定是先计算完括号内部的，再计算外部的。

这个，可以利用熟知的递归。

先计算内部，结果返回到上层，再统一计算即可。

步骤：递归遍历表达式字符串 str = "3*(4+5)+7"

1，遍历开始的时候，就进入第一层递归栈

当遇到 '('，说明接下来遇到括号了，需要进入下一层递归栈，

此时，先把当前递归栈的遍历过程记录下来：

2，遇到左括号 '('，进入下一层递归栈

每次的递归栈，都遍历到右括号，也就是需要结束的地方，

然后把当前递归栈中的表达式进行计算，

然后把结果返回到上层递归栈即可。

3，直到遍历完，都类似。计算结果即可

看看代码。

完整代码：

public class CodingDemo {

    /**
     * TODO; 计算器
     * @param s
     * @return
     */
    private static int calculate(String s) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != ' '){
                builder.append(s.charAt(i));
            }
        }
        char[] ch = builder.toString().toCharArray();

        return getValue(ch, 0)[0];
    }

    private static int[] getValue(char[] ch, int i){
        //1，创建队列，用于存储当前栈内的表达式
        Deque<String> deque = new LinkedList<String>();

        //2, 结果值集合
        int[] res = null;

        //记录表达式中的数值
        int pre = 0;

        while (i < ch.length && ch[i] != ')'){//遇到 ) ，则表示要跳出当前栈了

            if (ch[i] >= '0' && ch[i] <= '9'){ //当前遇到的字符是数字
                pre = pre *10 + ch[i++] - '0';
            } else if (ch[i] != '(') {
                //遇到的不是数字，也不是左括号，那么肯定是运算符了，
                // 把运算符前面的数值和队列中的值进行计算
                addNum(deque, pre);
                //加入当前运算符
                deque.addLast(String.valueOf(ch[i++]));
                pre = 0;
            } else {
                //此时，则表示遇到的是 (, 需要进入到下一个栈了
                res = getValue(ch, i+1);
                pre = res[0];
                i = res[1] + 1;
            }
        }
        addNum(deque, pre);
        return new int[]{getNum(deque), i};
    }

    /**
     * 把num，加入当前栈的队列中，如果遇到* /，则计算完后再把结果加入队列
     * @param deque
     * @param num
     * @return
     */
    private static void addNum(Deque<String> deque, int num){
        if (!deque.isEmpty()){
            int cur = 0;
            String top = deque.pollLast();

            //因为涉及到运算符优先级问题，遇到+ -，先不动，看看是否还有* /，
            if (top.equals("+") || top.equals("-")){
                deque.addLast(top);
            } else {
                //因为通过我们的设置，队列里面只能存在数字和+ -
                //此时在弹出的的就是 * /
                cur = Integer.parseInt(deque.pollLast());
                num = top.equals("*") ? (cur * num) : (cur / num);
            }
        }
        deque.addLast(String.valueOf(num));
    }

    /**
     * 计算当前队列包含的数字和运算符的结果值
     * @param deque
     * @return
     */
    private static int getNum(Deque<String> deque){
        int res = 0;

        //遇到的是否是 +
        boolean add = true;
        String cur = null; //当前字符
        int num = 0;

        while (!deque.isEmpty()){
            cur = deque.pollFirst();

            if (cur.equals("+")){
                add = true;
            } else if (cur.equals("-")){
                add = false;
            } else {
                //当前cur是数字
                num = Integer.parseInt(cur);
                res += add ? num : (-num);
            }
        }
        return res;
    }

    public static void main(String[] args) {

        String str = "3*(4+5) + 7";
        System.out.println(calculate(str));
    }
}