基本计算器 II

2023-12-25 12:47:39

题目链接

基本计算器 II

题目描述

注意点

  • s 由整数和算符 (‘+’, ‘-’, ‘*’, ‘/’) 组成,中间由一些空格隔开
  • s 表示一个 有效表达式
  • 整数除法仅保留整数部分
  • 所有中间结果将在整型范围内

解答思路

  • 算术表达式的计算首先想到利用栈先进后出的特点存储符号,关键是要找到各种运算符的计算顺序:如果是*、/则优先计算,如果是+、-则在计算过乘除之后再进行计算,且应该从前往后按顺序计算

代码

class Solution {
    public int calculate(String s) {
        int res = 0;
        int i = 0;
        Deque<Integer> numDeque = new ArrayDeque<>();
        Deque<Character> operateDeque = new ArrayDeque<>();
        while (i < s.length()) {
            if (s.charAt(i) == ' ') {
                i++;
                continue;
            }
            // 运算符直接入栈
            if (s.charAt(i) < '0' || s.charAt(i) > '9') {
                operateDeque.addLast(s.charAt(i));
                i++;
                continue;
            }
            // 寻找整个数字
            int num = 0;
            while (i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                num = num * 10 + (s.charAt(i) - '0');
                i++;
            }
            char operator = operateDeque.isEmpty() ? ' ' : operateDeque.peekLast();
            if (operator == '*' || operator == '/') {
                // 先将'*'和'/'进行运算
                operateDeque.pollLast();
                int prevNum = numDeque.pollLast();
                numDeque.addLast(calTwoNum(prevNum, num, operator));
            } else {
                // 如果无运算符或运算符为'+'、'-',则先将数字入栈
                numDeque.addLast(num);
            }
        }
        // 将剩余的'+'、'-'进行运算(从左到右)
        while (!operateDeque.isEmpty()) {
            int num1 = numDeque.pollFirst();
            int num2 = numDeque.pollFirst();
            char operator = operateDeque.pollFirst();
            numDeque.addFirst(calTwoNum(num1, num2, operator));
        }
        return numDeque.pollLast();
    }

    public int calTwoNum(int num1, int num2, char operator) {
        int tmp = 0;
        switch(operator) {
            case '*':
                tmp = num1 * num2;
                break;
            case '/':
                tmp = num1 / num2;
                break;
            case '+':
                tmp = num1 + num2;
                break;
            case '-':
                tmp = num1 - num2;
                break;
        }
        return tmp;
    }
}

关键点

  • 双端队列的使用
  • 计算完乘除符号对剩余的加减进行运算时要从前往后进行计算(从后往前计算会导致-后面的+计算出问题)

文章来源:https://blog.csdn.net/weixin_51628158/article/details/135128755
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。