[模板/OpenJudge 3882] 数学表达式求值〔模拟、栈〕

刚学栈时写过求解表达式的值的题目，但是当时会的太少了，代码很不好看. 今天 review 了一遍，用简单的 C++17 语法写了段面向对象的代码. 这个表达式类读入无空格的原始字符串，处理成 vector<any> 存储的中缀表达式，利用栈转换为后缀表达式，再利用栈求值. 支持正整数的加减乘除四则运算及乘方运算，支持括号.
正常表达式转换成前/后缀表达式用到了一个对于优先级的单调栈，网上对此有很多介绍，暂时不注释了. 代码跟这个题对应.

#include <bits/stdc++.h>

#define IOS_SPEED std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::string;
using std::any;
using std::any_cast;
using std::pow;
using std::vector;
using std::stack;
using std::unordered_map;

unordered_map<char, int> level = {{'(', 0}, {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'^', 3}};

inline int compute(int left, char op, int right){
    switch(op){
        case '+': return left+right;
        case '-': return left-right;
        case '*': return left*right;
        case '/': return left/right;
        case '^': return pow(left, right);
    }
    return -1;
}

class expression{
    public:
        string text;
        vector<any> midex;
        vector<any> sufex;
        expression(string &T): text(T), midex({}), sufex({}){};
        void extract();
        void convert();
        int value();
        void wipe();
};

void expression::extract(){
    auto cur = text.begin();
    while(cur!=text.end()){
        if(*cur<'0'||*cur>'9'){
            midex.push_back(*cur); ++ cur;
        }
        else{
            int num_val = 0;
            while(1){
                if(cur==text.end()) break;
                if(*cur<'0'||*cur>'9') break;
                num_val *= 10; num_val += *cur-'0';
                ++ cur;
            }
            midex.push_back(num_val);
        }
    }
}

void expression::convert(){
    stack<char> signs;
    for(auto &i: midex){
        if(i.type()==typeid(int))
            sufex.push_back(i);
        else{
            auto cur = any_cast<char>(i);
            if(cur=='(')
                signs.push('(');
            else if(cur==')'){
                while(signs.top()!='('){
                    sufex.push_back(signs.top()); signs.pop();
                }
                signs.pop();
            }
            else{
                if(signs.empty()||level[cur]>level[signs.top()])
                    signs.push(cur);
                else{
                    while(!signs.empty()&&level[cur]<=level[signs.top()]){
                        sufex.push_back(signs.top()); signs.pop();
                    }
                    signs.push(cur);
                }
            }
        }
    }
    while(!signs.empty()){
        sufex.push_back(signs.top()); signs.pop();
    }
}

int expression::value(){
    extract();
    convert();
    stack<int> process;
    for(auto &i: sufex){
        if(i.type()==typeid(int))
            process.push(any_cast<int>(i));
        else{
            int temp_top = process.top();
            process.pop();
            process.top() = compute(process.top(), any_cast<char>(i), temp_top);
        }
    }
    int answer = process.top();
    process.pop();
    return answer;
}

void expression::wipe(){
    text.clear(); midex.clear(); sufex.clear();
}

void interface(){
    IOS_SPEED;
    string input; cin >> input;
    expression expr(input);
    cout << expr.value() << "\n";
    expr.wipe();
}

int main()
{
    int cases;
    IOS_SPEED; cin >> cases;
    for(int i=0; i<cases; i++) interface();
    return 0; 
}

补:

1. 具体需求下用std::variant更贴切，但是std::any更爽！
2. 求后缀表达式的值可以不借用一个另外的栈来完成，替换方案是将后缀表达式expression::sufex的类型设为std::deque. 将expression::value()的遍历语句改为

    for(auto it = sufex.begin(); it!=sufex.end(); ++ it){
        if(it->type()!=typeid(int)){
            char opr = any_cast<char>(*it);
            int left = any_cast<int>(*(it-2)), right = any_cast<int>(*(it-1));
            sufex.erase(it-2, it);
            *it = compute(left, opr, right);
        }
    }

即可.