一、题目大意

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

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

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

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

示例 1：

输入：s = “3+2*2”
输出：7

示例 2：

输入：s = ” 3/2 “
输出：1

示例 3：

输入：s = ” 3+5 / 2 “
输出：5

提示：

  • 1 <= s.length <= 3 * 105
  • s 由整数和算符 (‘+’, ‘-‘, ‘*’, ‘/’) 组成，中间由一些空格隔开
  • s 表示一个 有效表达式
  • 表达式中的所有整数都是非负整数，且在范围 [0, 231 – 1] 内
  • 题目数据保证答案是一个 32-bit 整数

二、解题思路

如果我们在字符串左边加上一个加号，可以证明其不改变运算结果，且字符串可以分割成多个对子的形式；这样一来我们就可以从左往右处理了。由于乘除的优先级高于加减，因此我们需要使用一个中间变量来存储高优先度的运算结果。

还要注意无运算符和多个空格的情况。

三、解题方法3.1 Java实现

public class Solution {    public int calculate(String s) {        return (int) parseExpr(s, 0);    }    /**     * 辅函数 - 递归parse从位置i开始的剩余字符串     */    long parseExpr(String s, int i) {        char op = '+';        long left = 0;        long right = 0;        while (i < s.length()) {            if (s.charAt(i) != ' ') {                long n = parseNum(s, i);                switch (op) {                    case '+':                        left += right;                        right = n;                        break;                    case '-':                        left += right;                        right = -n;                        break;                    case '*':                        right *= n;                        break;                    case '/':                        right /= n;                        break;                }                if (i < s.length()) {                    op = s.charAt(i);                }            }            i++;        }        return left + right;    }    /**     * 辅函数 - parse从位置i开始的一个数字     */    long parseNum(String s, int i) {        long n = 0;        while (i < s.length() && Character.isDigit(s.charAt(i))) {            n = 10 * n + (s.charAt(i++) - '0');        }        return n;    }}

四、总结小记

  • 2022/8/29 大多数人每天的工作都在围绕着紧急的事情瞎忙活