表达式求值

模板:

/*
2
1.000+2/4=
((1+2)*5+1)/4=
--------
1.50
4.00
*/
const int N = 1000 + 20;
stack<char> st_ch;
stack<double> st_num;
void calc1()
{
    char ch = st_ch.top();
    while (ch != '(')
    {
        double num1 = st_num.top();
        st_num.pop();
        double num2 = st_num.top();
        st_num.pop();
        switch (ch)
        {
        case '+':
            num2 += num1;
            break;
        case '-':
            num2 -= num1;
            break;
        case '*':
            num2 *= num1;
            break;
        case '/':
            num2 /= num1;
            break;
        }
        st_num.push(num2);
        st_ch.pop();
        ch = st_ch.top();
    }
}
void calc2()
{
    char ch = st_ch.top();
    while (ch == '*' || ch == '/')
    {
        double num1 = st_num.top();
        st_num.pop();
        double num2 = st_num.top();
        st_num.pop();
        switch (ch)
        {
        case '*':
            num2 *= num1;
            break;
        case '/':
            num2 /= num1;
            break;
        }
        st_num.push(num2);
        st_ch.pop();
        ch = st_ch.top();
    }
}
int main()
{
    //freopen("in.txt", "r", stdin);
    string str;
    int t;
    cin >> t;
    while (t--)
    {
        cin >> str;
        int len = str.size();
        st_ch.push('(');
        string str_num = "";
        for (int i = 0; i < len; i++)
        {
            if (isdigit(str[i]) || str[i] == '.')
            {
                str_num += str[i];
                continue;
            }
            if (str_num != "")
            {
                double num = atof(str_num.c_str());
                st_num.push(num);
                str_num = "";
            }
            switch (str[i])
            {
            case '+':
            case '-':
                calc1();
                st_ch.push(str[i]);
                break;
            case '*':
            case '/':
                calc2();
                st_ch.push(str[i]);
                break;
            case '(':
                st_ch.push('(');
                break;
            case ')':
            case '=':
                calc1();
                st_ch.pop();
                break;
            }
        }
        printf("%.2lf\n", st_num.top());
        st_num.pop();
    }
    return 0;
}

/*
3
add(1,2)
max(1,999)
add(min(1,1000),add(100,99))
-----
3
999
200
*/
char str[maxn];
char chang(char a,char b)
{
    if(a=='a')
        return '+';
    else if(b=='a')
        return '>';
    else
        return '<';
}
int cal(int a,int b,char c)
{
    if(c=='+')
        return a+b;
    else if(c=='>')
        return max(a,b);
    else
        return min(a,b);
}
int main()
{
    int T;
    scanf("%d",&T);
    stack<char> s1;
    stack<int> s2;
    while(T--)
    {
        int w,v;
        char c;
        scanf("%s",str);
        while(!s1.empty()) s1.pop();
        while(!s2.empty()) s2.pop();
        int len=strlen(str);
        for(int i=0; i<len; i++)
        {
            if(str[i]=='a'||str[i]=='m')
                c=chang(str[i],str[i+1]);
                s1.push(c);
                i+=2;
            }
            else if(str[i]<='9'&&str[i]>='0')
            {
                int num,l;
                sscanf(&str[i],"%d%n", &num, &l);
                s2.push(num);
                i=i+l-1;
            }
            else if(str[i]==')')
            {
                w=s2.top(),s2.pop();
                v=s2.top(),s2.pop();
                c=s1.top(),s1.pop();
                w=cal(w,v,c);
                s2.push(w);
            }
        }
        printf("%d\n",s2.top());
    }
}

/*
3
12+2*3
12*(2+3)
12*(2+3)+Smax(333,220+280)
---
18
60
69
*/
char s[1005];
map<char, int> mp;
stack<char> s2; //符号
stack<int> s1;  //数字
int Smax(int a)
{
    int b = 0;
    while (a)
        b += a % 10, a /= 10;
    return b;
}
void solve(int li)
{
    int a, b, c, d;
    while (!s2.empty() && mp[s2.top()] < li)
    {
        if (s2.top() == ',')
        {
            c = s1.top();
            s2.pop();
            s1.pop();
            continue;
        }
        a = s1.top();
        s1.pop();
        b = s1.top();
        s1.pop();
        if (s2.top() == '*')
            s1.push(a * b);
        if (s2.top() == '+')
            s1.push(a + b);
        s2.pop();
    }
    if (li == 2)
    {
        if (s2.top() == '<')
        {
            d = s1.top();
            s1.pop();
            a = Smax(c), b = Smax(d);
            s1.push(a > b ? a : b);
        }
        s2.pop();
    }
}

int main()
{
    freopen("in.txt", "r", stdin);
    mp['*'] = 0;
    mp['+'] = 0;
    mp[','] = 1;
    mp['<'] = 2;
    mp['('] = 2;
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%s", s);
        int len = strlen(s);
        for (int i = 0; i < len; i++)
        {
            if (isdigit(s[i]))
            {
                int t = 0;
                while (isdigit(s[i]))
                {
                    t *= 10;
                    t += s[i] - '0';
                    i++;
                }
                i--;
                s1.push(t);
            }
            else if (s[i] == ')')
                solve(2); //如果是右括号，处理到一个出现 '<' 或者 '('
            else if (s[i] == '+')
                solve(1), s2.push('+'); //如果是+号，将栈顶的 * 和 + 处理干净
            else if (s[i] == 'S')
                s2.push('<'), i += 4;
            else
                s2.push(s[i]); //'('  ','  '*' 直接入栈
        }
        solve(10); //处理干净剩余的操作符
        printf("%d\n", s1.top());
        while (!s1.empty())
            s1.pop(); //其实不清空问题不大，但每做一次运算，内存消耗就会增加
    }
    return 0;
}