题目链接：https://nanti.jisuanke.com/t/A1990
题目大意：

给你一个字符串其中包含+, -, *, '(', ')',数字(正整数)，'d'(优先级最高)。xdy表示投掷x次y面的骰子。

现在问你这个表达式可能的最大值和最小值是多少？
图片说明

思路：对一个xdy我们维护一个[L, R]最小值：x。最大值：x*y。把表达式求值的板子改一下就AC了。

#include<bits/stdc++.h>
using namespace std;

struct Interval {
    int L, R;
    Interval() {}
    Interval(int a, int b) : L(a), R(b) {}
    void Print() {
        printf("[%d,%d]\n", L, R);
    }
};
Interval operator + (const Interval &a, const Interval &b) {
    return Interval(a.L + b.L, a.R + b.R);
}
Interval operator - (const Interval &a, const Interval &b) {
    return Interval(a.L - b.R, a.R - b.L);
}
Interval operator * (const Interval &a, const Interval &b) {
    int mn = min(min(a.L * b.L, a.L * b.R), min(a.R * b.L, a.R * b.R));
    int mx = max(max(a.L * b.L, a.L * b.R), max(a.R * b.L, a.R * b.R));
    return Interval(mn, mx);
}
Interval f(const Interval &a, const Interval &b) {
    assert(a.L >= 0 && b.L >= 1);
    return Interval(a.L, a.R * b.R);
}


char Precede(char a,char b) //得到a对b的优先级
{
    char op[8][8]=
    {//   +   -   *   /   (   )   #    d
        {'>','>','<','<','<','>','>','<'},// +
        {'>','>','<','<','<','>','>','<'},// -
        {'>','>','>','>','<','>','>','<'},// *
        {'>','>','>','>','<','>','>','<'},// /
        {'<','<','<','<','<','=','0','<'},// (
        {'>','>','>','>','0','>','>','>'},// )
        {'<','<','<','<','<','0','=','<'},// #
        {'>','>','>','>','<','>','>','>'} // d
    };
    int x,y;
    switch(a)
    {
        case '+': x=0; break;
        case '-': x=1; break;
        case '*': x=2; break;
        case '/': x=3; break;
        case '(': x=4; break;
        case ')': x=5; break;
        case '#': x=6; break;
        case 'd': x=7; break;
    }
    switch(b)
    {
        case '+': y=0; break;
        case '-': y=1; break;
        case '*': y=2; break;
        case '/': y=3; break;
        case '(': y=4; break;
        case ')': y=5; break;
        case '#': y=6; break;
        case 'd': y=7; break;
    }
    return op[x][y];
}
Interval Calculation(Interval num1,Interval num2,char op)//计算
{
    switch(op)
    {
        case '+':
            return num1+num2;
        case '-':
            return num1-num2;
        case '*':
            return num1*num2;
        case 'd':
            return f(num1, num2);
    }
}
int main()
{
    string s;
    while(cin >> s)
    {
        if (s.find("+") == string::npos && s.find("-") == string::npos &&
            s.find("*") == string::npos && s.find("/") == string::npos&& s.find("d") == string::npos)
        {//单独的一个数字
            cout << s << " "<<s<<endl; continue;
        }
        s += '#';//表示结束
        stack<Interval> opnd;
        stack<char> optr;
        optr.push('#');
        int num = 0, i = 0;
        bool flag = false;
        while (s[i] != '#' || optr.top() != '#')
        {
            if (isdigit(s[i]))
            {
                flag = true;
                num = num * 10 + (s[i] - '0');
                i++;
                continue;
            }
            else
            {
                if (flag)
                {
                    opnd.push(Interval{num, num}); num = 0; flag = false;
                }
                switch(Precede(optr.top(),s[i]))
                {
                    case '<':
                        optr.push(s[i]);
                        i++;
                        break;
                    case '=':
                        optr.pop();
                        i++;
                        break;
                    case '>':
                        char  op = optr.top(); optr.pop();
                        Interval num1 = opnd.top(); opnd.pop();
                        Interval num2 = opnd.top(); opnd.pop();
                        Interval ans = Calculation(num2, num1, op);
                        opnd.push(ans); break;
                }
            }
        }
        cout << opnd.top().L<<" "<< opnd.top().R<< endl;
    }
    return 0;
}
/*
1+2*(2+3)/5
*/