题目描述

227. 基本计算器 II
151. 表达式计算4

给你一个字符串表达式 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 整数

题解

表达式与遍历强相关。与二叉树有关系，所以与栈有关系，因为栈与二叉树有着很深的关系。

错误示范

坑： 这个字符’+‘与to_stirng(’+‘) ，实际上就是把这个’+'字符放到string当中，也就是"43",因为题目当中的"43",这种就会被误认为43是‘+’号，所以这种做法是不行的。
当然这是因为我把字符先将整数和操作符都切分成字符串放入numstr当中。

class Solution {
public:
    int calculate(string a) {
        stringstream ss(a);
        string s;
        string tmp;
        while (ss >> tmp)
        {
            s += tmp;
        }
        stack<int> numst;
        stack<string> symbolst;
        vector<string> numstr;
        int pre = 0, cur = 0;
        unordered_map<string, int> um;
        um[to_string('+')] = 1;
        um[to_string('-')] = 1;
        um[to_string('*')] = 2;
        um[to_string('/')] = 2;
        while (cur < s.size())
        {
            while (pre < s.size() && um.find(to_string(s[pre])) != um.end())
            {
                pre++;
            }
            while (cur < s.size() && um.find(to_string(s[cur])) == um.end())
            {
                cur++;
            }
            if (um.find(to_string(s[pre])) == um.end())
            {
                numstr.push_back(s.substr(pre, cur - pre));
                if (cur != s.size())
                {
                    numstr.push_back(to_string(s[cur]));
                }
                pre = cur;
                cur++;
            }
        }

        unordered_map<string, function<int(int, int)>> funtionum = {
            make_pair(to_string('+'),[](int x,int y) {return x + y; }),make_pair(to_string('-'),[](int x,int y) {return x - y; }),
            make_pair(to_string('*'),[](int x,int y) {return x * y; }),make_pair(to_string('/'),[](int x,int y) {return x / y; })
        };
        for (int i = 0; i < numstr.size(); ++i)
        {
            if (um.count(numstr[i]) != 0)
            {
                if (!symbolst.empty() && um[to_string(s[i])] <= um[symbolst.top()])
                {
                    int y = numst.top();
                    numst.pop();
                    int x = numst.top();
                    numst.pop();
                    string ch = symbolst.top();
                    symbolst.pop();
                    int res = funtionum[ch](x, y);
                    numst.push(res);
                }
                symbolst.push(to_string(s[i]));
            }
            else
            {
                numst.push(atoi(numstr[i].c_str()));
            }
        }
        while (!symbolst.empty())
        {
            int y = numst.top();
            numst.pop();
            int x = numst.top();
            numst.pop();
            string ch = symbolst.top();
            symbolst.pop();
            int res = funtionum[ch](x, y);
            numst.push(res);
        }

        return numst.top();
    }
};

正确答案

class Solution {
public:
    int calculate(string a) {
        stringstream ss(a);
        string s;
        string tmp;
        while (ss >> tmp)
        {
            s += tmp;
        }
        stack<int> numst;
        stack<char> symbolst;
        unordered_map<char, int> compareum;
        compareum['+'] = 1;
        compareum['-'] = 1;
        compareum['*'] = 2;
        compareum['/'] = 2;

        unordered_map<char, function<int(int, int)>> funtionum = {
            make_pair('+',[](int x,int y) {return x + y; }),make_pair('-',[](int x,int y) {return x - y; }),
            make_pair('*',[](int x,int y) {return x * y; }),make_pair('/',[](int x,int y) {return x / y; })
        };
        int cur = 0;
        while (cur < s.size())
        {
            if (s[cur] >= '0' && s[cur] <= '9')
            {
                int tmp = 0;
                while (cur < s.size() && s[cur] >= '0' && s[cur] <= '9')
                {
                    tmp *= 10;
                    tmp += s[cur] - '0';
                    cur++;
                }
                numst.push(tmp);
            }
            else
            {
                while (!symbolst.empty() && compareum[s[cur]] <= compareum[symbolst.top()])
                {
                    int y = numst.top();
                    numst.pop();
                    int x = numst.top();
                    numst.pop();
                    char ch = symbolst.top();
                    symbolst.pop();
                    int res = funtionum[ch](x, y);
                    numst.push(res);
                }
                symbolst.push(s[cur]);
                ++cur;
            }
        }

        while (!symbolst.empty())
        {
            int y = numst.top();
            numst.pop();
            int x = numst.top();
            numst.pop();
            char ch = symbolst.top();
            symbolst.pop();
            int res = funtionum[ch](x, y);
            numst.push(res);
        }

        return numst.top();
    }
};

比较完美的答案（重要）

解析计算器的一个步骤

• 需要两个栈，一个存放数值，一个存放运算符，如 1 * 1 - 2 ^ 2 ，当我们遍历到 -的时候才知道前面的 1*1可以计算，同理，遍历到-号的时候不能确定是否能够执行，只有当前运算符出现比栈顶的运算符优先级低的时候，说明栈顶是优先级高的运算符，此时才可以拿出来计算。
• 如果同等级的运算符，如 + 号 后遇到 + 号，那么前面的+号要比后面的+号的优先级高，因为我们默认同等级运算符是从左往后运算的。也就是前一个+可以出栈了。
• 需要考虑遇到 括号()的问题，实际上是否遇到括号可以用同一种逻辑表示，只需要入左括号(，遇到右括号的时候将栈当中元素拿出来计算，知道运算符栈的栈顶元素是(，从始至终)是不需要入栈的，所以为了保证测试用例当中出现(1+2))))))))这种测试用例，我们统一可以添加字符串长度的左括号在字符串前面，这样就保证了每一个右括号一定有一个左括号匹配。
• 并且为了扩展性更强，定义了两个成员变量 pri_um ，operator_um ，pri_um 可以用来自定义运算符和对应优先级的映射，operator_um 可以用来规定自定义运算符和运算方法。

至此，下面的代码实际上更加全面，甚至能够自定义运算符的运算方式和优先等级。

如1+(((3+2) 等用例的出现导致我们必须在结尾进行判断，当然也可以添加相同数量的右扩号解决。

#include<iostream>
using namespace std;
#include<string>
#include<stack>
#include<unordered_map>
#include<functional>
#include<sstream>
#include<cmath>
class Solution {
public:
    stack<int> _numst;
    stack<char> _operatorst;
    unordered_map<char, int> pri_um = {
        {'+',1},
        {'-',1},
        {'*',2},
        {'/',2},
        {'^',3},
    };
    unordered_map<char, function<int(int, int)>> operator_um = {
        {'+', [](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; }},
        {'^', [](int x,int y) {return pow(x,y); }},
    };

    int calculate(string s) {
        string l = "(";
        for (size_t i = 0; i < s.size(); ++i)
        {
            l += '(';
        }
        l += s;
        s = move(l);
        //s += ')';
        _numst.push(0);// -1 + 2 ，若先入0，后续会入 负号， 再入1 就和正常计算一样了，若第一个数是正数，后续st计算完这个也不会使用到。
        for (int i = 0; i < s.size(); ++i)
        {
            if (s[i] == ' ') continue;//第一种情况，遇到空格
            else if (s[i] == '(')//遇到左括号
            {
                //入左括号，(-1 + 2) ,判断是否是以负数开头
                _operatorst.push(s[i]);
                if (i + 1 < s.size() && s[i + 1] == '-')
                {
                    _numst.push(0);
                    _operatorst.push('-');
                    ++i;
                }
            }
            else if (s[i] == ')') // 此时_operatorst当中直接一个个出，因为当中的优先级是已经排序好的，以(结尾即可
            {
                //右括号，此时不需要入右括号，只需要计算到栈顶是(为止，并把左括号弹出
                while (_operatorst.top() != '(')//此时严格'('的数量多余')',当遍历到'('说明区间内的数据都计算完全了~
                {
                    cal();
                }
                _operatorst.pop();//去掉 '('，此时严格'('的数量多余')'
            }
            else if (s[i] >= '0' && s[i] <= '9')//数字中穿插空格的情况不考虑，这个应用层的问题
            {//若是正常正常数字，则进行计算
                int pre = i;
                //while (i + 1 < s.size() && pri_um.find(s[i + 1]) == pri_um.end())//即找到不是操作符，error
                while (i + 1 < s.size() && s[i + 1] >= '0' && s[i + 1] <= '9')//即往后找的一定还是数字
                {
                    i++;
                }
                int res = stoi(s.substr(pre, i - pre + 1));
                _numst.push(res);
            }
            else
            {//即操作符st为空，或者操作符st栈顶是(，或者是操作符的优先级，opers.top()!='('括号不匹配才会有这个问题。
                while (!_operatorst.empty() && _operatorst.top() != '(' && pri_um[s[i]] <= pri_um[_operatorst.top()])
                {
                    cal();
                }
                _operatorst.push(s[i]);
            }
        }
        while (!_operatorst.empty())
        {
            if (_operatorst.top() != '(')
            {
                cal();
            }
            else
            {
                _operatorst.pop();
            }
        }
        return _numst.top();
    }
	//只做一次计算，从_numst拿两个元素，_operatorst拿一个运算符做计算
    int cal()
    {
        int r = _numst.top(); _numst.pop();
        int l = _numst.top(); _numst.pop();
        char op = _operatorst.top(); _operatorst.pop();
        int res = operator_um[op](l, r);
        _numst.push(res);

        return res;
    }
};




int main()
{
    string str;
    getline(cin,str);
    Solution s1;
    cout << s1.calculate(str) << endl;
    return 0;
}

当然，若是不想加入最后一层while循环，实际上可以在s字符串添加相同数量的)，只需要在遍历到)的时候判断需要改动，如是否有操作符以及是否是(，以及对出(做判断，因为此时不一定满足(的数量大于)。

#include<iostream>
using namespace std;
#include<string>
#include<stack>
#include<unordered_map>
#include<functional>
#include<sstream>
#include<cmath>
class Solution {
public:
    stack<int> _numst;
    stack<char> _operatorst;
    unordered_map<char, int> pri_um = {
        {'+',1},
        {'-',1},
        {'*',2},
        {'/',2},
        {'^',3},
    };
    unordered_map<char, function<int(int, int)>> operator_um = {
        {'+', [](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; }},
        {'^', [](int x,int y) {return pow(x,y); }},
    };

    int calculate(string s) {
        string l = "(";
        int sz = s.size();
        for (size_t i = 0; i < s.size(); ++i)
        {
            l += '(';
        }
        l += s;
        s = move(l);
        for (size_t i = 0; i < sz; ++i)
        {
            s += ')';
        }
        //cout << s << endl;
        //s += ')';
        _numst.push(0);// -1 + 2 ，若先入0，后续会入 负号， 再入1 就和正常计算一样了，若第一个数是正数，后续st计算完这个也不会使用到。
        for (int i = 0; i < s.size(); ++i)
        {
            if (s[i] == ' ') continue;//第一种情况，遇到空格
            else if (s[i] == '(')//遇到左括号
            {
                //入左括号，(-1 + 2) ,判断是否是以负数开头
                _operatorst.push(s[i]);
                if (i + 1 < s.size() && s[i + 1] == '-')
                {
                    _numst.push(0);
                    _operatorst.push('-');
                    ++i;
                }
            }
            else if (s[i] == ')') // 此时_operatorst当中直接一个个出，因为当中的优先级是已经排序好的，以(结尾即可
            {
                //右括号，此时不需要入右括号，只需要计算到栈顶是(为止，并把左括号弹出
                while (!_operatorst.empty() && _operatorst.top() != '(')
                {
                    cal();
                }
                if (!_operatorst.empty())
                    _operatorst.pop();//去掉 '('
            }
            else if (s[i] >= '0' && s[i] <= '9')//数字中穿插空格的情况不考虑，这个应用层的问题
            {//若是正常正常数字，则进行计算
                int pre = i;
                //while (i + 1 < s.size() && pri_um.find(s[i + 1]) == pri_um.end())//即找到不是操作符
                while (i + 1 < s.size() && s[i + 1] >= '0' && s[i + 1] <= '9')//即找到不是操作符
                {
                    i++;
                }
                int res = stoi(s.substr(pre, i - pre + 1));
                _numst.push(res);
            }
            else
            {//即操作符st为空，或者操作符st栈顶是(，或者是操作符的优先级，opers.top()!='('括号不匹配才会有这个问题。
                while (!_operatorst.empty() && _operatorst.top() != '(' && pri_um[s[i]] <= pri_um[_operatorst.top()])
                {
                    cal();
                }
                _operatorst.push(s[i]);
            }
        }
        return _numst.top();
    }

    int cal()
    {
        int r = _numst.top(); _numst.pop();
        int l = _numst.top(); _numst.pop();
        char op = _operatorst.top(); _operatorst.pop();
        int res = operator_um[op](l, r);
        _numst.push(res);

        return res;
    }
};




int main()
{
    string str;
    getline(cin,str);
    Solution s1;
    cout << s1.calculate(str) << endl;
    return 0;
}

参考：
https://www.acwing.com/solution/content/39453/

end

• 喜欢就收藏
• 认同就点赞
• 支持就关注
• 疑问就评论