当前位置:   article > 正文

基本计算器算法实现_输入一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。

输入一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。

基本计算器

没有括号基本计算

题目

给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数,比如 eval() 。

示例 1:

输入:s = “3+2*2” 输出:7 示例 2:

输入:s = " 3/2 " 输出:1 示例 3:

输入:s = " 3+5 / 2 " 输出:5

代码实现
public int calculate(String s) {
    //优先级Map
    HashMap<Character, Integer> prio = new HashMap<>();
    prio.put('+', 2);
    prio.put('-', 2);
    prio.put('*', 3);
    prio.put('/', 3);
    //存放解析的数字
    Stack<Integer> stk = new Stack<>();
    //存放操作符
    Stack<Character> ops = new Stack<>();
    //由整数和算符 ('+', '-', '*', '/') 组成,中间由一些空格隔开 过滤空格
    s = s.replace(" ", "");
    int length = s.length();
    for (int i = 0; i < length;) {
        // 依次获取字符
        char c = s.charAt(i);
        if (Character.isDigit(c)) {
            // 属于数字逻辑
            int num = 0;
            while (i < length && Character.isDigit(s.charAt(i))) {
                num = num * 10 + s.charAt(i) - '0';
                i++;
            }
            //存放数字
            stk.push(num);
        } else {
            //属于('+', '-', '*', '/')
            while (!ops.isEmpty() && prio.get(c) <= prio.get(ops.peek())) {
                /** 判断优先级由于我们使用栈存放数字和操作符(先进后出) 举个例子:
                1-1-3 假如没有优先级:先算1-3 = -2 然后 -2 进栈,最后 1-(-2) = 3
                有优先级控制,当第二个‘-’号判断的时候会和ops.peek() 做比较一样就进来做计算。
                1-1*3 这个就不需要进来因为本来就是先算1*3
                **/
                calculateBase(ops, stk);
            }
            //存放当前操作符
            ops.push(c);
            i++;
        }
    }

    while (!ops.isEmpty()) {
        //最后计算里面剩余的逻辑比如:3+2*2 (本题最多两个操作符)1-1-3 由于上面优先级判断的时候计算过一轮 最后只有两个数字一个操作符
        calculateBase(ops, stk);
    }
    return stk.peek();
}

/**
 * 加减乘除基础计算结果入栈
 * @param ops
 * @param stk
 */
private static void calculateBase(Stack<Character> ops, Stack<Integer> stk) {
    if (ops.isEmpty() || stk.size() < 2) {
        return;
    }
    char op = ops.pop();

    int r = stk.pop();
    int l = stk.pop();
    int res = 0;

    if (op == '*') {
        res = l * r;
    }
    if (op == '/') {
        res = l / r;
    }
    if (op == '+') {
        res = l + r;
    }
    if (op == '-') {
        res = l - r;
    }
    stk.push(res);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78

带括号的基本计算

题目

给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数,比如 eval() 。

示例 1:

输入:s = “1 * 1 + 1/1+(1-1)” 输出:2 示例 2:

输入:s = " 2-1 + 2 " 输出:3 示例 3:

输入:s = “(1+(4+5+2)-3)+(6+8)” 输出:23

代码实现
public int calculate(String s) {
        //优先级Map
        HashMap<Character, Integer> prio = new HashMap<>();
        prio.put('(', 1);
        prio.put('+', 2);
        prio.put('-', 2);
        prio.put('*', 3);
        prio.put('/', 3);
        //过滤空格、特殊表达式替换(-2)替换成(0-2)、(+2)替换成(0+2)方便统一计算
        s = s.replace(" ", "").replace("(-", "(0-").replace("(+", "(0+");
        //获取替换后字符串长度
        int length = s.length();
        //存放解析的数字
        Stack<Integer> stk = new Stack<>();
        //存放操作符
        Stack<Character> ops = new Stack<>();
        for (int i = 0; i < length; ) {
        // 依次获取字符
        char c = s.charAt(i);
        if (Character.isDigit(c)) {
        // 属于数字逻辑
        int num = 0;
        //判断是否存在连续的数字eg:1234+3 1234就得通过下面逻辑处理
        while (i < length && Character.isDigit(s.charAt(i))) {
            num = num * 10 + (s.charAt(i) - '0');
            i++;
        }
            //存放数字
            stack.push(num);
        } else if (c == '(') {
            //遇到左括号入栈 因为需要判断和右括号对应
            op.push(c);
            i++;
        } else if (c == ')') {
            //遇到右括号,判断是否需要计算
            while (i < length && !op.isEmpty() && op.peek() != '(') {
                calculateBase(op, stack);
            }
            //出栈对应的左括号
            if (!op.isEmpty()) {
                op.pop();
            }
            i++;
        } else {

           //属于('+', '-', '*', '/')
            while (!op.isEmpty() && prio.get(c) <= prio.get(op.peek())) {
                /** 判断优先级由于我们使用栈存放数字和操作符(先进后出) 举个例子:
                1-1-3 假如没有优先级:先算1-3 = -2 然后 -2 进栈,最后 1-(-2) = 3
                有优先级控制,当第二个‘-’号判断的时候会和ops.peek() 做比较一样就进来做计算。
                1-1*3 这个就不需要进来因为本来就是先算1*3
                **/
                calculateBase(op, stack);
            }
            //处理-()
            if (stack.isEmpty()) {
                stack.push(0);
            }
            op.push(c);
            i++;
        }
    }
    while (!op.isEmpty()) {
        //最后计算里面剩余的逻辑比如:3+2*2 (本题最多两个操作符)1-1-3 由于上面优先级判断的时候计算过一轮 最后只有两个数字一个操作符
        calculateBase(op, stack);
    }
    return stack.peek();
}

  
    
  private static void calculateBase(Stack<Character> ops, Stack<Integer> stk) {
      if (ops.isEmpty() || stk.size() < 2) {
          return;
      }
      char op = ops.pop();

      int r = stk.pop();
      int l = stk.pop();
      int res = 0;

      if (op == '*') {
          res = l * r;
      }
      if (op == '/') {
          res = l / r;
      }
      if (op == '+') {
          res = l + r;
      }
      if (op == '-') {
          res = l - r;
      }
      stk.push(res);
  }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号