一、题目描述

二、解题思路

将中缀表达式转换为后缀表达式。

三、解题代码

class Solution
{
   
private:
    static unordered_map<char, int> icp, isp;
    stack<char> stk;
    string src;
    string sln;
    void Back();
    int calc(int tmp1, char oper, int tmp2);

public:
    int calculate(string str) {
   
        for (size_t i = 0; i < str.size(); i++) // remove space
            if (str.at(i) != ' ')
                src += str[i];
        stk.push('#');
        return eval();
    }
    int eval();
};
unordered_map<char, int> Solution::icp{
   {
   '#', 0}, {
   '(', 6}, {
   ')', 1}, {
   '*', 4}, {
   '/', 4}, {
   '+', 2}, {
   '-', 2}};
unordered_map<char, int> Solution::isp{
   {
   '#', 0}, {
   '(', 1}, {
   ')', 6}, {
   '*', 5}, {
   '/', 5}, {
   '+', 3}, {
   '-', 3}};

void Solution::Back()
{
   
    int left = 0, right = 0;
    auto len = src.size();
    for (; left < len; left++) //双指针法切割字符串
    {
   
        if (isdigit(src[left])) //没有正负号的情况进行切割
        {
   
            for (right = left; right < len && icp.find(src.at(right)) == icp.end(); right++)
                ;
            sln += src.substr(left, right - left);
            sln += " ";
            left = right - 1;
        }
        else
        {
   
            auto tmp = src.at(left);
            if (tmp == '-' || tmp == '+')
            {
   
                //如果开头就是负号，没什么可说的
                //或者该操作符前一个位置还是操作符，但是它前面那个操作符不是')'的话，说明它一定为正负号
                if (!left || (src.at(left - 1) != ')' && icp.find(src.at(left - 1)) != icp.end()))
                {
   
                    if (tmp == '-')
                        sln += tmp;
                    for (right = ++left; right < len && icp.find(src.at(right)) == icp.end(); right++)
                        ;
                    sln += src.substr(left, right - left);
                    sln += " ";
                    left = right - 1;
                    continue;
                }
            }
            if (isp[stk.top()] < icp[tmp])
                stk.push(tmp);
            else // if (isp[stk.top()] > icp[tmp])
            {
       //必须要把if (isp[stk.top()] > icp[tmp])注释掉，否则无法准确识别正负号，无法通过测试点
                while (isp[stk.top()] > icp[tmp])
                {
   
                    sln += stk.top();
                    sln += " ";
                    stk.pop();
                }
                isp[stk.top()] >= icp[tmp] ? stk.pop() : stk.push(tmp);
            }
        }
    }
    while (stk.size() > 1) //切割完成后排空栈
    {
   
        sln += stk.top();
        sln += " ";
        stk.pop();
    }
    sln = sln.substr(0, sln.size() - 1); //去掉结果串结尾的' '
    //cout << sln << endl;
}

int Solution::calc(int first, char oper, int second)
{
   
    int ans;
    if (oper == '+')
        ans = first + second;
    else if (oper == '-')
        ans = first - second;
    else if (oper == '*')
        ans = first * second;
    else if (oper == '/'){
   
        if(!second)    exit(0);
        ans = first / second;
    }   
    else    exit(1);
    return ans;
}

int Solution::eval()
{
   
    Back();
    stack<int> num;
    size_t left = 0, right = 0;
    auto len = sln.size();
    for (; left < len; left++)
    {
   
        for (right = left; right < len && sln.at(right) != ' '; right++)
            ;
        if (right - left == 1)
        {
   
            if (icp.find(sln.at(left)) != icp.end())
            {
   
                auto oper = sln.at(left);
                auto second = num.top();
                num.pop();
                auto first = num.top();
                num.pop();
                num.push(calc(first, oper, second));
            }
            else
                num.push(sln.at(left) - '0');
        }
        else
            num.push(atoi(sln.substr(left, right - left).c_str()));
        left = right;
    }
    return num.top();
}

四、运行结果