首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >算法细节系列(25):加减乘除

算法细节系列(25):加减乘除

作者头像
用户1147447
发布2019-05-26 09:48:33
4600
发布2019-05-26 09:48:33
举报
文章被收录于专栏:机器学习入门机器学习入门

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434778

算法细节系列(25):加减乘除

详细代码可以fork下Github上leetcode项目,不定期更新。

题目摘自leetcode:

Leetcode 227. Basic Calculator II

思路来源:

  • 首先,所有操作符就加减乘除四个符号,优先级就两层,乘除大于加减,所以,解析字符串时,优先计算乘除,加减可以先放一放。(怎么做?栈可以来控制优先级,还有一种技术可以控制优先级计算,递归!但递归说到底就是栈,本质上一样。)
  • 栈为什么能控制优先级?想象一下,为什么会有数字存入栈中,无非是因为根据当前信息无法进行计算,为啥?因为加减后可能还有优先级更高的操作,对于加减来说,它们没有选择的余地,只能放在栈中等待着被支配。
  • 接着看这道题,如计算2+3*2时,栈中存放了2和3的元素,当遇到乘法2时,它知道了这家伙一定可以被计算,所以再取个2,和3乘得到6。此时表达式就变成了2+6。嘿,好家伙,观察到一个性质没?加减乘除计算都是【就近】找元素来运算的,栈的FILO是不是符合这种就近操作?

代码如下:

    public int calculate(String s) {
        String ss = s.replace("+","#+").replace("-", "#-").replace("/", "#/").replace("*", "#*");
        String[] values = ss.split("#");
        int[] nums = new int[values.length];
        char[] operators = new char[values.length-1];

        int cnt1 = 0;
        int cnt2 = 0;
        for (int i = 0; i < values.length; i++){
            if (values[i].toCharArray()[0] == '+' ||
                    values[i].toCharArray()[0] == '-' ||
                        values[i].toCharArray()[0] == '*' ||
                             values[i].toCharArray()[0] == '/'){
                operators[cnt2++] = values[i].toCharArray()[0];
                nums[cnt1++] = Integer.parseInt(values[i].substring(1).trim());
            }else{
                nums[cnt1++] = Integer.parseInt(values[i].trim());
            }
        }

        Deque<Integer> numStack = new ArrayDeque<>();
        Deque<Character> operatorStack = new ArrayDeque<>();
        numStack.push(nums[0]);
        for (int i = 0; i < operators.length; i++){
            if (operators[i] == '*' || operators[i] == '/'){
                numStack.push(nums[i+1]);
                int a1 = numStack.pollFirst();
                int a2 = numStack.pollFirst();
                switch (operators[i]) {
                case '*':{
                    numStack.push(a2 * a1);
                }
                    break;
                case '/':{
                    numStack.push(a2 / a1);
                }
                    break;
                default:
                    break;
                }
            }else{
                operatorStack.push(operators[i]);
                numStack.push(nums[i+1]);
            }
        }

        while (!operatorStack.isEmpty()){
            char opera = operatorStack.pollLast();
            int a1 = numStack.pollLast();
            int a2 = numStack.pollLast();
            switch (opera) {
            case '+':{
                numStack.addLast(a1 + a2);;
            }
                break;
            case '-':{
                numStack.addLast(a1 - a2);
            }
                break;
            default:
                break;
            }
        }

        return numStack.peek();
    }

我的代码相对复杂,但就照着上面的思路,慢慢敲就出来,我很多细节没考虑,可以优化的地方太多了,诸如为什么不直接边提取数字和操作符边做计算,起码可以省去一个循环,是吧。用的还不是栈,用的是双端队列,吼吼,计算细节可以慢慢体会。dicuss中有更聪明的做法,用到了些基本性质做了优化,可以提提。

比如计算: 2+3*2/4+5-2*2
我的做法就不提了,看代码都能明白。
短码的做法:
a. 对字符做了一次预处理,操作如下:
+2+3*2/4+5-2*2#
注意字符前的"+"和字符后的"#"

b. 对减法的优化:减法就是特殊的加法,操作如下:
+2+3*2/4+5+(-2)*2#
就这两步优化,可以为我们省去很多很多代码!

具体操作来看代码吧,有了上述的铺垫,代码就很容易写出来了。

代码如下:

    public int calculate(String s) {
        if (s == null || s.length() == 0) return 0;
        char[] cs = s.toCharArray();
        Stack<Integer> stack = new Stack<>();
        //相当于字符串前的+
        char sign = '+'; //开始的数字一定为正
        for (int i = 0, num = 0; i < cs.length; i++){
            if (Character.isDigit(cs[i])){
                num = num * 10 + cs[i] - '0';
            }
            //i == cs.length - 1 相当于那个#,读到#号,还要对最后一个操作符进行计算
            if (i == cs.length -1 || !Character.isDigit(cs[i]) && cs[i] != ' '){ //操作符的情况
                if (sign == '+'){
                    stack.push(num);
                }
                //减法当+法,省去了加减运算,做后直接遍历加就好了。
                if (sign == '-'){
                    stack.push(-num);
                }
                //乘除的就近计算
                if (sign == '*'){
                    stack.push(stack.pop() * num);
                }
                if (sign == '/'){
                    stack.push(stack.pop() / num);
                }
                //想想这里,做的其实都是前一步的操作。
                sign = cs[i];
                num = 0;
            }
        }
        int res = 0;
        for (int i : stack){
            res += i;
        }
        return res;
    }

Leetcode 150. Evaluate Reverse Polish Notation

思路:

其实没什么,思路题目已经给你了,还是个就近操作,不过因为加减乘除在这种表达式中无优先级,所以遇到符号就进行计算即可。

代码如下:

public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++){
            if (!isOperator(tokens[i])){
                stack.push(Integer.parseInt(tokens[i]));
            }else{
                int a1 = stack.pop();
                int a2 = stack.pop();
                if (tokens[i].equals("+")){
                    stack.push(a2 + a1);
                }
                if (tokens[i].equals("-")){
                    stack.push(a2 - a1);
                }
                if (tokens[i].equals("*")){
                    stack.push(a2 * a1);
                }
                if (tokens[i].equals("/")){
                    stack.push(a2 / a1);
                }
            }
        }
        return stack.peek();
    }

    private boolean isOperator(String op){
        return op.equals("+") || op.equals("-") || op.equals("*") || op.equals("/");
    }

Leetcode 224. Basic Calculator

先说说我的思路吧:

  • 关键问题是右括号,遇到右括号说明表达式闭合,就必须得计算了,所以一旦遇到右括号进行计算。
  • 那么遇到左括号怎么办?直接建立一个StringBuilder把字符暂存起来,因为我们实在没有足够的信息去计算。那么一旦遇到右括号,就可以利用第一题的计算方法算出表达式的值,拼接下做后续操作即可。

代码如下:

    public int calculate(String s) {
        if (s == null || s.length() == 0) return 0;
        char[] cs = s.toCharArray();
        Stack<StringBuilder> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < cs.length; i++){
            if (cs[i] == '('){
                stack.push(sb);
                sb = new StringBuilder();
            }
            else if (cs[i] == ')'){
                int ans = calculateNoparentheses(validExpression(sb.toString()));
                sb = stack.pop();
                sb.append(ans);
            }else{
                sb.append(cs[i]);
            }
        }
        return calculateNoparentheses(validExpression(sb.toString()));
    }

    private String validExpression(String s){
        return s.replaceAll("-\\s*-", "+").replaceAll("\\+\\s*-", "-");
    }

    //这里还可以优化,其实没必要使用栈
    private int calculateNoparentheses(String s){
        if (s.length() == 0 || s == null) return 0;
        Stack<Integer> stack = new Stack<>();
        char opera = '+';
        char[] cs = s.toCharArray();
        for (int i = 0, num = 0; i < s.length(); i++){
            if (Character.isDigit(cs[i])){
                num = num * 10 + cs[i] - '0';
            }
            if (i == s.length() - 1 || !Character.isDigit(cs[i]) && cs[i] != ' '){
                if (opera == '+'){
                    stack.push(num);
                }

                if (opera == '-'){
                    stack.push(-num);
                }
                opera = cs[i];
                num = 0;
            }
        }
        int res = 0;
        for (int num : stack){
            res += num;
        }
        return res;
    }

这道题,我们还可以换个角度思考,当没有遇到左括号和右括号,随着遍历的进行,可以直接一步步计算。当遇到左括号就把先前计算的结果存入栈中,再一步步计算,而当遇到右括号,就把栈中的元素poll出,在此基础上计算。代码结构和上述代码一致,但代码更加精简,如下:

public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        char[] cs = s.toCharArray();
        int res = 0, sign = 1;
        int num = 0;
        for (int i = 0; i < cs.length; i++){
            if (Character.isDigit(cs[i])){
                num = num * 10 + cs[i] - '0';
            }
            else if (cs[i] == '+'){
                res += sign * num;
                num = 0;
                sign = 1;
            }
            else if (cs[i] == '-'){
                res += sign * num;
                num = 0;
                sign = -1;
            }
            else if (cs[i] == '('){
                stack.push(res);
                stack.push(sign);
                res = 0;
                sign = 1;
            }
            else if (cs[i] == ')'){
                res += sign * num;
                num = 0;
                res *= stack.pop();
                res += stack.pop();
            }
        }
        if (num != 0) res += sign * num;
        return res;
    }

它的思路更加清楚,对只含有加减的字符串计算,我们可以看成如下:

3+4-4+5-1

+3 +4 -4 +5 -1
上述的遍历方式形象点就是计算:
res += (+3);
res += (+4);
res += (-4);
res += (+5);
res += (-1);

而当遇到左括号时,需要压入栈的有之前计算的res,以及当前的符号,这样当括号内的表达式计算完毕后,可以在此基础上继续加or减。

还需注意最后的num != 0的情况是因为我们控制算法计算是当遇到下一个操作符,到了字符串末尾自然没有操作符,所以需要额外计算一次。

当然你也可以初始化s时,在末尾再加一个操作符,如下:

    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        s += "+";
        char[] cs = s.toCharArray();
        int res = 0, sign = 1;
        int num = 0;
        for (int i = 0; i < cs.length; i++){
            if (Character.isDigit(cs[i])){
                num = num * 10 + cs[i] - '0';
            }
            else if (cs[i] == '+'){
                res += sign * num;
                num = 0;
                sign = 1;
            }
            else if (cs[i] == '-'){
                res += sign * num;
                num = 0;
                sign = -1;
            }
            else if (cs[i] == '('){
                stack.push(res);
                stack.push(sign);
                res = 0;
                sign = 1;
            }
            else if (cs[i] == ')'){
                res += sign * num;
                num = 0;
                res *= stack.pop();
                res += stack.pop();
            }
        }
        //if (num != 0) res += sign * num;
        return res;
    }

依旧AC。

Leetcode 282. Expression Add Operators

一道回溯题,主要难点在于对*法的处理,如下:

2 + 3 * 5
在递归回溯搜索时,它实际的优先级计算如下:
(2 + 3) * 5
而我们要改成:2 + 3 * 5

假设当前val = (2 + 3),且记录右括号左侧第一个数 multed = 3,当前 cur = 5

则:val = val - multed + multed * cur

遇到连乘同样起作用,如:
(2 + 3 * 5) * 4
val = 2 + 3 = 5;
multed = 3 * 5;
cur = 4;

则:val = val - multed + multed * cur;

减号取个反就好了,一个道理。

代码如下:

public List<String> addOperators(String num, int target) {
        List<String> rst = new ArrayList<String>();
        if(num == null || num.length() == 0) return rst;
        helper(rst, "", num, 0, target, 0, 0);
        return rst;
    }

    private void helper(List<String> ans, String path, String num, int pos, int target, long val, long multed){
        if (pos == num.length()){
            if (target == val){
                ans.add(path);
            }
        }
        for (int i = pos; i < num.length(); i++){
            //排除以0元素开头i结尾的数,如05,00均不合法
            if(i != pos && num.charAt(pos) == '0') break;
            long cur = Long.parseLong(num.substring(pos, i + 1));
            // 起初默认的为加法
            if (pos == 0){
                helper(ans, path + cur, num, i + 1, target, cur, cur);
            }
            else{
                helper(ans, path + "+" + cur, num, i + 1, target, val + cur, cur);
                helper(ans, path + "-" + cur, num, i + 1, target, val - cur, -cur);
                helper(ans, path + "*" + cur, num, i + 1, target, val - multed + multed * cur, multed * cur);
            }
        }
    }
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017年05月27日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 算法细节系列(25):加减乘除
    • Leetcode 227. Basic Calculator II
      • Leetcode 150. Evaluate Reverse Polish Notation
        • Leetcode 224. Basic Calculator
          • Leetcode 282. Expression Add Operators
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档