【leetcode】计算器问题汇总

腾讯面试手撕计算器，带括号和加减乘除的中缀表达式，面试的时候没有写出来，必须得学学咋做了。

前置知识

我们平时遇到的数学表达式其实都是中缀表达式，比如1+2/3这一类。但是对于计算机而言，计算后缀表达式是更加方便的操作，包括我们自己写计算的函数，也是后缀表达式更加好处理。

所以我们应该先记住中缀、后缀、前缀表达式的区别，以及如何将中缀表达式转为后缀表达式。因为选择题有时候也会考相关的题目，不仅是要会写代码，还得记住怎么人工转换。

我当时面试的时候就是忘记怎么把中缀转为后缀了，结果一直在死算，手撕给的时间本来就不多，临时写之前没写过的代码实在是写不出来，一堆BUG，突出一个菜。

这部分内容都在本站的另外一篇博客逆波兰表达式求值中有提到，本文不再重复。阅读本文之前，建议先阅读该文章并完成 leetcode 150.逆波兰表达式求值那道题。后缀表达式求值的思路如下：

从左往右遍历，遇到操作数，入栈；
遇到运算符，取栈顶两个连续数据进行计算（第二个取出来的是左操作数），再将计算结果入栈；

下面给出的是逆波兰表达式求值的代码。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> s;
        map<string,function<int(int,int)>> FuncMap = {
            {"+",[](int x,int y){return x+y;}},
            {"-",[](int x,int y){return x-y;}},
            {"*",[](int x,int y){return x*y;}},
            {"/",[](int x,int y){return x/y;}}
        };
        for(auto& ch : tokens)
        {
            if(ch=="+"||ch=="-"||ch=="*"||ch=="/")
            {
                int right=s.top();
                s.pop();
                int left=s.top();
                s.pop();
                int ret = FuncMap[ch](left,right);
                s.push(ret);
            }
            else{
                s.push(stoi(ch));
            }   
        }
        return s.top();
    }
};

题目一：227. 基本计算器 II

227. 基本计算器 II 和面试题 16.26. 计算器

这是leetcode上和计算器有关的题目中最简单的一个，它并不需要我们将中缀表达式转为后缀，直接通过一个栈加遍历的方式就可以将其写出来。

1
2
3

给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。

表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格。 整数除法仅保留整数部分。

代码如下，我们需要一个栈来存放处理的数字，并用一个num来拼接字符串里面的数字（虽然用例都是一位数字，但是题目并没有说不会出现多位数字，所以需要拼接），和一个prevClac指代上一个操作符。

当遇到操作符且不为空格，或者当前已经遍历到字符串末尾的时候，就需要进行计算。其他情况都说明是数字，对num变量进行拼接就可以了。

在计算过程中，我们把加减计算给替代成用数字的正负号来处理，乘除计算则直接对栈内元素做处理。这里需要记住一个小知识点，即STL的stack.top()函数返回的是栈顶元素的引用，所以我们可以直接对其进行修改，不需要用临时变量来处理。

class Solution {
public:
    // 是不是数字？
    bool isNum(char& c) { return c >= '0' && c <= '9'; }

    int calculate(string s) {
        stack<int> numSt;
        int num = 0;         // 拼数字
        char prevClac = '+'; // 上一位运算符
        // 遍历字符串，跳过空格，遇到乘除直接计算，遇到加减推后计算
        for (int i = 0; i < s.size(); i++) {
            char& c = s[i];
            if (isNum(c)) {
                num = num * 10 + int(c - '0');
            }
            // 如果是操作符（注意不能是空格），或者当前已经是最后一位了，就需要计算
            if ((!isNum(c) && c != ' ') || i == s.size() - 1) {
                // 我们把加减操作改成数字的正负来处理
                if (prevClac == '+') {
                    numSt.push(num);
                } else if (prevClac == '-') {
                    numSt.push(-num);
                }
                // 直接计算乘除，top返回的是引用
                else if (prevClac == '*') {
                    numSt.top() *= num;
                } else if (prevClac == '/') {
                    numSt.top() /= num;
                }
                // 更新操作符
                prevClac = c;
                num = 0;
            }
        }
        // 最后统一求和
        int sum = 0;
        while (!numSt.empty()) {
            sum += numSt.top();
            numSt.pop();
        }
        return sum;
    }
};

题目二：224. 基本计算器

https://leetcode.cn/problems/basic-calculator/description/

这道题在原本的普通中缀表达式的基础上，添加了括号，但没有乘除法。

我们可以用中缀表达式先转为后续表达式的方式，再使用上文提到过的150逆波兰表达式求值的代码来计算它。

题目

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

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

示例 1：
输入：s = "1 + 1"
输出：2

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

示例 3：
输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

提示

1 <= s.length <= 3 * 105
s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
s 表示一个有效的表达式
'+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)
'-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)
输入中不存在两个连续的操作符
每个数字和运行的计算将适合于一个有符号的 32位 整数

中缀表达式转后缀表达式

使用一个栈来存放操作符，注意左右括号，左括号的优先级低于任何操作符，右括号优先级高于任何操作符。

遇到操作数的时候 先输出 到结果表达式中;
遇到操作符，和栈顶进行比较
- 如果栈为空/操作符优先级高于栈顶，入栈；
- 操作符优先级低于栈顶或和栈顶相同，出栈顶操作符（然后继续比较当前操作符和栈顶操作符）；
如果是左括号(，正常入栈；
遇到右括号)，出栈内所有操作符，直到遇到对应左括号，注意，最终的输出后缀表达式中不需要添加左/右括号；
最后将栈中的操作符全部出栈，就可以获得后缀表达式；

具体的代码如下，有点长，但是不难理解

#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;

// 判断当前的操作符优先级是不是比栈顶更高？
bool isCalcHigher(const string& cur, const string& target)
{
    // 如果是乘除，且栈顶是加减，那么优先级就更高
    if ((cur == "*" || cur == "/") && (target == "+" || target == "-"))
    {
        return true;
    }
    // 如果target是左括号，则为true
    if (target == "(") {
        return true;
    }
    // 其他情况，包括栈顶也是乘除的情况，优先级都低
    return false;
}

// 中序表达式转后缀表达式
vector<string> inOrderTobackOrder(const string& s)
{
    vector<string> retV;
    stack<string> st; //  操作符栈
    string num;       // 零时存放数字
    for (auto& itr : s)
    {
        string c;
        c.push_back(itr);
        // 跳过空格
        if (c == " ")
        {
            continue;
        }
        // 操作数
        if (c >= "0" && c <= "9")
        {
            num.push_back(c[0]);
            continue;
        }
        // 其他情况都说明不是操作数，需要将之前的操作数输出
        if (num.size() > 0)
        {
            retV.push_back(num);
            num.resize(0);
        }

        // 左括号入栈
        if (c == "(")
        {
            st.push(c);
        }
        // 遇到右括号，需要一直出栈内操作符，直到遇到左括号
        else if (c == ")")
        {
            // 遇到右括号的时候不可能出现栈为空的情况
            while (st.top() != "(")
            {
                retV.emplace_back(st.top());
                st.pop();
            }
            st.pop(); // 弹出左括号
        }
        // 如果栈为空，则入栈
        else if (st.empty())
        {
            st.push(c);
        }
        else // 其他操作符
        {
            // 栈不为空，和栈顶的优先级进行比较
            // 操作符优先级高于栈顶，入栈;
            if (isCalcHigher(c, st.top()))
            {
                st.push(c);
                continue;
            }
            // 优先级低于/等于栈顶操作符，将栈顶出栈（放入结果表达式）
            retV.emplace_back(st.top());
            st.pop();
            // 继续判断，直到高于栈顶运算符
            while (!st.empty() && !isCalcHigher(c, st.top()))
            {
                retV.emplace_back(st.top());
                st.pop();
            }
            // 栈顶高于当前运算符或栈为空，入栈
            st.push(c);
        }
    }
    // num不为空，还需要处理
    if (num.size() > 0)
    {
        retV.push_back(num);
    }
    // 结束遍历，将栈内操作符依次输出，即得到了最终的后缀表达式
    while (!st.empty())
    {
        retV.emplace_back(st.top());
        st.pop();
    }
    return retV;
}

int main()
{
    string s;
    cout << "enter inOrder > ";
    getline(cin, s);
    // 处理
    auto retV = inOrderTobackOrder(s);
    cout << "backOrder result: [";
    for (int i = 0;i<retV.size();i++)
    {
        cout << "\"" << retV[i] << "\"";
        if(i!=retV.size()-1){
            cout << ", ";
        }
    }
    cout << "]"<< endl;
    return 0;
}

在224题目中给出的(1+(4+5+2)-3)+(6+8)这个表达式，经过转换的结果如下。

1
2
3

❯ g++ 中缀表达式转后缀表达式.cpp -o test && ./test
enter inOrder > (1+(4+5+2)-3)+(6+8)
backOrder result: ["1", "4", "5", "+", "2", "+", "+", "3", "-", "6", "8", "+", "+"]

把这个结果提供给150题目中的代码，计算结果就是23，代表我们的中缀转后缀的转换代码是正确的。

单独的正负号处理

有了这个函数后，我们就可以编写OJ的代码了，先把给出的中缀表达式转成后缀的，在进行计算。

先把基本的代码合并在一起，然后运行。此时会发现题目中有些刁钻的测试用例是过不了的。比如下面这个，它缺少了一个操作数，这导致我们中序转后续转出来的表达式是错误的。

"1-(     -2)"

题目中的提示也说明了这一点

1 2	'+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效) '-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)

这就需要我们对这种情况做个单独处理，即把-2变成0-2。

// 修改中缀表达式为合法表达式
void stringHandler(string &s)
{
    // 去除所有空格
    std::string tmp;
    for (auto &c : s)
    {
        if (c != ' ')
        {
            tmp += c;
        }
    }
    // 处理独立的负号或者正号
    // (-n) -> (0-n)
    // (+n) -> (0+n)
    // 开头的-n -> 0-n
    // 开头的+n -> 0+n
    s.resize(0);
    int n = tmp.length();
    for (int i = 0; i < n; ++i)
    {
        // 开头的-n或者括号里面的-n
        if (tmp[i] == '-' && (i == 0 || tmp[i - 1] == '('))
        {
            s += "0-";
        }
        // 开头的+n或者括号里面的+n
        else if (tmp[i] == '+' && (i == 0 || tmp[i - 1] == '('))
        {
            s += "0+";
        }
        else
        {
            // 其他情况说明是有匹配的表达式的，所以不需要处理
            s += tmp[i];
        }
    }
}

可以看到，通过这个函数处理后，一切都正常了。

1 2	enter inOrder > 1-( -2) handle: 1-(0-2)

完整代码

class Solution {
    // 判断当前的操作符优先级是不是比栈顶更高？
    bool isCalcHigher(const string& cur, const string& target) {
        // 如果是乘除，且栈顶是加减，那么优先级就更高
        if ((cur == "*" || cur == "/") && (target == "+" || target == "-")) {
            return true;
        }
        // 如果target是左括号，则为true
        if (target == "(") {
            return true;
        }
        // 其他情况，包括栈顶也是乘除的情况，优先级都低
        return false;
    }
    // 修改中缀表达式为合法表达式
    void stringHandler(string& s) {
        // 去除所有空格
        std::string tmp;
        for (auto& c : s) {
            if (c != ' ') {
                tmp += c;
            }
        }
        // 处理独立的负号或者正号
        // (-n) -> (0-n)
        // (+n) -> (0+n)
        // 开头的-n -> 0-n
        // 开头的+n -> 0+n
        s.resize(0);
        int n = tmp.length();
        for (int i = 0; i < n; ++i) {
            // 开头的-n或者括号里面的-n
            if (tmp[i] == '-' && (i == 0 || tmp[i - 1] == '(')) {
                s += "0-";
            }
            // 开头的+n或者括号里面的+n
            else if (tmp[i] == '+' && (i == 0 || tmp[i - 1] == '(')) {
                s += "0+";
            } else {
                // 其他情况说明是有匹配的表达式的，所以不需要处理
                s += tmp[i];
            }
        }
    }

    // 中序表达式转后缀表达式
    vector<string> inOrderTobackOrder(string& s) {
        vector<string> retV;
        stack<string> st; //  操作符栈
        string num;       // 零时存放数字
        stringHandler(s);
        for (auto& itr : s) {
            string c;
            c.push_back(itr);
            // 跳过空格
            if (c == " ") {
                continue;
            }
            // 操作数
            if (c >= "0" && c <= "9") {
                num.push_back(c[0]);
                continue;
            }
            // 其他情况都说明不是操作数，需要将之前的操作数输出
            if (num.size() > 0) {
                retV.push_back(num);
                num.resize(0);
            }

            // 左括号入栈
            if (c == "(") {
                st.push(c);
            }
            // 遇到右括号，需要一直出栈内操作符，直到遇到左括号
            else if (c == ")") {
                // 遇到右括号的时候不可能出现栈为空的情况
                while (st.top() != "(") {
                    retV.emplace_back(st.top());
                    st.pop();
                }
                st.pop(); // 弹出左括号
            }
            // 如果栈为空，则入栈
            else if (st.empty()) {
                st.push(c);
            } else // 其他操作符
            {
                // 栈不为空，和栈顶的优先级进行比较
                // 操作符优先级高于栈顶，入栈;
                if (isCalcHigher(c, st.top())) {
                    st.push(c);
                    continue;
                }
                // 优先级低于/等于栈顶操作符，将栈顶出栈（放入结果表达式）
                retV.emplace_back(st.top());
                st.pop();
                // 继续判断，直到高于栈顶运算符
                while (!st.empty() && !isCalcHigher(c, st.top())) {
                    retV.emplace_back(st.top());
                    st.pop();
                }
                // 栈顶高于当前运算符或栈为空，入栈
                st.push(c);
            }
        }
        // num不为空，还需要处理
        if (num.size() > 0) {
            retV.push_back(num);
        }
        // 结束遍历，将栈内操作符依次输出，即得到了最终的后缀表达式
        while (!st.empty()) {
            retV.emplace_back(st.top());
            st.pop();
        }
        return retV;
    }

public:
    int calculate(string s) {
        auto retV = inOrderTobackOrder(s);
        // 后缀表达式计算
        stack<int> st;
        unordered_map<string, function<int(int, int)>> funcMap = {
            {"+", [](int x, int y) { return x + y; }},
            {"-", [](int x, int y) { return x - y; }},
            {"*", [](int x, int y) { return x * y; }},
            {"/", [](int x, int y) { return x / y; }}};
        for (auto& ch : retV) {
            if (ch == "+" || ch == "-" || ch == "*" || ch == "/") {
                int right = st.top();
                st.pop();
                int left = st.top();
                st.pop();
                int ret = funcMap[ch](left, right);
                st.push(ret);
            } else {
                st.push(stoi(ch));
            }
        }
        return st.top();
    }
};