题解 | #简单表达式计算#

固定思路解决固定问题，还是有点代码量的。属于力扣224号题的简化版本。

#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <unordered_map>

using namespace std;

vector<string> uniformInfixExpr(string& s)  //将数字和运算符单独作为一个字符串放入vector中
{
    int n = s.size(), i = 0, idx = 0;
    vector<string> token(n);
    
    while(i < n)
    {
        char ch = s[i];
        string tmp;
        
        if(isdigit(ch))  //需要将连续的数字作为一个整体
        {
            tmp.append(1, s[i++]);
            while(i < n && isdigit(s[i])) tmp.append(1, s[i++]);
            i--;  //若下一个不是数字字符, 则多移动了一步
        }
        else  //+ - *
        {
            tmp.append(1, ch);
        }
        
        token[idx++] = std::move(tmp);
        
        i++;
    }
    
    token.erase(token.begin() + idx, token.end()); //调整为实际所需的大小

    return std::move(token);
}

vector<string> infixToPostfix(string& infix)
{
    vector<string> infixExpr = uniformInfixExpr(infix);  

    unordered_map<char ,int> prec; //将运算符映射为整数, 以确定运算符的优先级
    prec['*'] = 3;
    prec['+'] = prec['-'] = 2;
    
    stack<char> opSt;
    vector<string> postfixList(infixExpr.size());
    
    int idx = 0;
    for(auto &token : infixExpr)
    {
        char ch = token[0];
        if(isdigit(ch))
        {
            postfixList[idx++] = std::move(token);
        }
        else
        {
            //运算符入栈之前需要先进行优先级的考量
            while(!opSt.empty() && prec[opSt.top()] >= prec[ch])
            {
                postfixList[idx++] = std::move(string(1, opSt.top()));
                opSt.pop();
            }
            opSt.emplace(ch);
        }
    }
    
    //将残留的运算符添加到postfixList的尾部
    while(!opSt.empty())
    {
        postfixList[idx++] = std::move(string(1, opSt.top()));
        opSt.pop();
    }
    
    return std::move(postfixList);
}

int doMath(stack<int>& st, char op)
{
    int a = st.top(); st.pop();
    int b = st.top(); st.pop();

    if (op == '+') return b + a;
    else if (op == '-') return b - a;
    else return b * a;
}

int eval(vector<string>& postfix)
{
    stack<int> numSt;
    
    for(auto &op : postfix)
    {
        if(isdigit(op[0]))
        {
            numSt.emplace(stoi(op));
        }
        else  //碰见运算符就运算
        {
            int ans = doMath(numSt, op[0]);
            numSt.emplace(ans);
        }
    }
    
    int ans = numSt.top();
    
    return ans;
}

int main()
{
    string infixExp;  //只包含非负整数、加法、减法以及乘法符号（不会有括号,空格之类的）
    
    while(cin >> infixExp)
    {
        if(infixExp ==  "END") break;
        
        vector<string> postfix = infixToPostfix(infixExp);
        int res = eval(postfix);
        
        cout << res << endl;
        getchar();
    }
    
    return 0;
}