读完本文，你能够去力扣拿下如下题目：

224.根本计算器

227.根本计算器II

772.根本计算器III

-----------

咱们最终要实现的计算器性能如下：

1、输出一个字符串，能够蕴含+ - * /、数字、括号以及空格，你的算法返回运算后果。

2、要合乎运算法令，括号的优先级最高，先乘除后加减。

3、除号是整数除法，无论正负都向 0 取整（5/2=2，-5/2=-2）。

4、能够假设输出的算式肯定非法，且计算过程不会呈现整型溢出，不会呈现除数为 0 的意外状况。

比方输出如下字符串，算法会返回 9：

3 * (2-6 /(3 -7))

能够看到，这就曾经十分靠近咱们理论生存中应用的计算器了，尽管咱们以前必定都用过计算器，然而如果简略思考一下其算法实现，就会大惊失色：

1、依照常理解决括号，要先计算最内层的括号，而后向外缓缓化简。这个过程咱们手算都容易出错，何况写成算法呢！

2、要做到先乘除，后加减，这一点教会小朋友还不算难，但教给计算机恐怕有点艰难。

3、要解决空格。咱们为了好看，习惯性在数字和运算符之间打个空格，然而计算之中得想方法疏忽这些空格。

我记得很多大学数据结构的教材上，在讲栈这种数据结构的时候，应该都会用计算器举例，然而有一说一，讲的真的垃圾，不晓得多少将来的计算机科学家就被这种简略的数据结构劝退了。

那么本文就来聊聊怎么实现上述一个性能齐备的计算器性能，关键在于层层拆解问题，化整为零，一一击破，置信这种思维形式能帮大家解决各种简单问题。

上面就来拆解，从最简略的一个问题开始。

一、字符串转整数

是的，就是这么一个简略的问题，首先通知我，怎么把一个字符串模式的正整数，转化成 int 型？

string s = "458";int n = 0;for (int i = 0; i < s.size(); i++) {    char c = s[i];    n = 10 * n + (c - '0');}// n 当初就等于 458

这个还是很简略的吧，老套路了。然而即使这么简略，仍然有坑：(c - '0')的这个括号不能省略，否则可能造成整型溢出。

因为变量c是一个 ASCII 码，如果不加括号就会先加后减，设想一下s如果靠近 INT_MAX，就会溢出。所以用括号保障先减后加才行。

二、解决加减法

当初进一步，如果输出的这个算式只蕴含加减法，而且不存在空格，你怎么计算结果？咱们拿字符串算式1-12+3为例，来说一个很简略的思路：

1、先给第一个数字加一个默认符号+，变成+1-12+3。

2、把一个运算符和数字组合成一对儿，也就是三对儿+1，-12，+3，把它们转化成数字，而后放到一个栈中。

3、将栈中所有的数字求和，就是原算式的后果。

咱们间接看代码，联合一张图就看明确了：

int calculate(string s) {    stack<int> stk;    // 记录算式中的数字    int num = 0;    // 记录 num 前的符号，初始化为 +    char sign = '+';    for (int i = 0; i < s.size(); i++) {        char c = s[i];        // 如果是数字，间断读取到 num        if (isdigit(c))             num = 10 * num + (c - '0');        // 如果不是数字，就是遇到了下一个符号，        // 之前的数字和符号就要存进栈中        if (!isdigit(c) || i == s.size() - 1) {            switch (sign) {                case '+':                    stk.push(num); break;                case '-':                    stk.push(-num); break;            }            // 更新符号为以后符号，数字清零            sign = c;            num = 0;        }    }    // 将栈中所有后果求和就是答案    int res = 0;    while (!stk.empty()) {        res += stk.top();        stk.pop();    }    return res;}

我预计就是两头带switch语句的局部有点不好了解吧，i就是从左到右扫描，sign和num跟在它身后。当s[i]遇到一个运算符时，状况是这样的：

所以说，此时要依据sign的 case 不同抉择nums的正负号，存入栈中，而后更新sign并清零nums记录下一对儿合乎和数字的组合。

另外留神，不只是遇到新的符号会触发入栈，当i走到了算式的止境（i == s.size() - 1），也应该将后面的数字入栈，不便后续计算最终后果。

至此，仅解决紧凑加减法字符串的算法就实现了，请确保了解以上内容，后续的内容就基于这个框架修修改改就完事儿了。

三、解决乘除法

其实思路跟仅解决加减法没啥区别，拿字符串2-3*4+5举例，外围思路仍然是把字符串分解成符号和数字的组合。

比方上述例子就能够合成为+2，-3，*4，+5几对儿，咱们方才不是没有解决乘除号吗，很简略，其余局部都不必变，在switch局部加上对应的 case 就行了：

for (int i = 0; i < s.size(); i++) {    char c = s[i];    if (isdigit(c))         num = 10 * num + (c - '0');    if (!isdigit(c) || i == s.size() - 1) {        switch (sign) {            int pre;            case '+':                stk.push(num); break;            case '-':                stk.push(-num); break;            // 只有拿出前一个数字做对应运算即可            case '*':                pre = stk.top();                stk.pop();                stk.push(pre * num);                break;            case '/':                pre = stk.top();                stk.pop();                stk.push(pre / num);                break;        }        // 更新符号为以后符号，数字清零        sign = c;        num = 0;    }}

乘除法优先于加减法体现在，乘除法能够和栈顶的数联合，而加减法只能把本人放入栈。

当初咱们思考一下如何解决字符串中可能呈现的空格字符。其实也非常简单，想想空格字符的呈现，会影响咱们现有代码的哪一部分？

// 如果 c 非数字if (!isdigit(c) || i == s.size() - 1) {    switch (c) {...}    sign = c;    num = 0;}

显然空格会进入这个 if 语句，然而咱们并不想让空格的状况进入这个 if，因为这里会更新sign并清零nums，空格基本就不是运算符，应该被疏忽。

那么只有多加一个条件即可：

if ((!isdigit(c) && c != ' ') || i == s.size() - 1) {    ...}

好了，当初咱们的算法曾经能够依照正确的法令计算加减乘除，并且主动疏忽空格符，剩下的就是如何让算法正确辨认括号了。

四、解决括号

解决算式中的括号看起来应该是最难的，但真没有看起来那么难。

为了躲避编程语言的繁琐细节，我把后面解法的代码翻译成 Python 版本：

def calculate(s: str) -> int:            def helper(s: List) -> int:        stack = []        sign = '+'        num = 0        while len(s) > 0:            c = s.pop(0)            if c.isdigit():                num = 10 * num + int(c)            if (not c.isdigit() and c != ' ') or len(s) == 0:                if sign == '+':                    stack.append(num)                elif sign == '-':                    stack.append(-num)                elif sign == '*':                    stack[-1] = stack[-1] * num                elif sign == '/':                    # python 除法向 0 取整的写法                    stack[-1] = int(stack[-1] / float(num))                                    num = 0                sign = c        return sum(stack)    # 须要把字符串转成列表不便操作    return helper(list(s))

这段代码跟方才 C++ 代码完全相同，惟一的区别是，不是从左到右遍历字符串，而是一直从右边pop出字符，实质还是一样的。

那么，为什么说解决括号没有看起来那么难呢，因为括号具备递归性质。咱们拿字符串3*(4-5/2)-6举例：

calculate(3*(4-5/2)-6)
= 3 * calculate(4-5/2) - 6
= 3 * 2 - 6
= 0

能够脑补一下，无论多少层括号嵌套，通过 calculate 函数递归调用本人，都能够将括号中的算式化简成一个数字。换句话说，括号蕴含的算式，咱们间接视为一个数字就行了。

当初的问题是，递归的开始条件和完结条件是什么？遇到(开始递归，遇到)完结递归：

def calculate(s: str) -> int:            def helper(s: List) -> int:        stack = []        sign = '+'        num = 0        while len(s) > 0:            c = s.pop(0)            if c.isdigit():                num = 10 * num + int(c)            # 遇到左括号开始递归计算 num            if c == '(':                num = helper(s)            if (not c.isdigit() and c != ' ') or len(s) == 0:                if sign == '+': ...                elif sign == '-': ...                 elif sign == '*': ...                elif sign == '/': ...                num = 0                sign = c            # 遇到右括号返回递归后果            if c == ')': break        return sum(stack)    return helper(list(s))

你看，加了两三行代码，就能够解决括号了，这就是递归的魅力。至此，计算器的全副性能就实现了，通过对问题的层层拆解化整为零，再回头看，这个问题仿佛也没那么简单嘛。

五、最初总结

本文借实现计算器的问题，次要想表白的是一种解决简单问题的思路。

咱们首先从字符串转数字这个简略问题开始，进而解决只蕴含加减法的算式，进而解决蕴含加减乘除四则运算的算式，进而解决空格字符，进而解决蕴含括号的算式。

可见，对于一些比拟艰难的问题，其解法并不是欲速不达的，而是步步推动，螺旋回升的。如果一开始给你原题，你不会做，甚至看不懂答案，都很失常，关键在于咱们本人如何简化问题，如何以退为进。

退而求其次是一种很聪慧策略。你想想啊，假如这是一道考试题，你不会实现这个计算器，然而你写了字符串转整数的算法并指出了容易溢出的陷阱，那起码能够得 20 分吧；如果你可能解决加减法，那能够得 40 分吧；如果你能解决加减乘除四则运算，那起码够 70 分了；再加上解决空格字符，80 有了吧。我就是不会解决括号，那就算了，80 曾经很 OK 了好不好。