2016河南ACM省赛－A－表达式求值

描述

假设表达式定义为：
1. 一个十进制的正整数X是一个表达式。
2. 如果X和Y是表达式，则X + Y， X * Y也是表达式；优先级＊高于＋。
3. 如果X和Y是表达式，则函数Smax(X, Y)也是表达式，其值为：先分别求出X，Y值的各位数字之和，再从中选最大值。
4. 如果X是表达式，则(X)也是表达式。
例如：

表达式 12*(2+3)+Smax(333,220+280) 的值为69。

请你变成，对给定的表达式，输出其值。

标准输入
第一行：表示要计算的表达式个数（1≤T≤10）
接下来有T行：每行是一个字符串，表示待求的表达式，长度≤1000

标准输出
对于每个表达式，输出一行，表示对应表达式的值。

样例

标准输入	标准输出
3	（此空格请忽略）
12+2*3	18
12*(2+3)	60
12*(2+3)+Smax(333,220+280)	69

注：表达式中出现的所有正整数≤1000，求出的所有表达式的值小于10^6.

题解

一道简单直观的字符串处理问题，需要用到栈，这里我使用的是双栈，一个数据栈，一个字符栈，另外需要着重注意的是Smax函数，这个函数是Smax(a,b)的形式，所以我们忽略掉Smax四个字符，直接处理检索到的“(”“,”“)”，也就是说将这个函数中的括号和其他括号统一规则处理，而将逗号和加号、乘号划为一类来处理。注意优先级问题即可。

代码C++

#include <iostream>
#include <algorithm>
#include <stack>
#include <string>

using namespace std;

string s;
stack<int> stnum;
stack<char> stopt;

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        cin >> s;
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] >= '0' && s[i] <= '9')
            {
                int num = s[i] - '0';
                i++;
                while (s[i] >= '0' && s[i] <= '9' && i < s.length())
                {
                    num *= 10;
                    num += s[i] - '0';
                    i++;
                }
                //cout << num << '\n';
                stnum.push(num);
                if (i >= s.length())
                {
                    break;
                }
            }
            if (s[i] == '(')
            {
                stopt.push(s[i]);
            }
            else if (s[i] == '*')
            {
                stopt.push(s[i]);
            }
            else if (s[i] == 'S')
            {
                stopt.push('(');
                i += 4;
            }
            else if (s[i] == ',')
            {
                int num = stnum.top();
                stnum.pop();
                while (stopt.top() != '(')
                {
                    if (stopt.top() == '+')
                    {
                        num += stnum.top();
                        stnum.pop();
                    }
                    else if (stopt.top() == '*')
                    {
                        num *= stnum.top();
                        stnum.pop();
                    }
                    stopt.pop();
                }
                stnum.push(num);
                stopt.push(',');
            }
            else if (s[i] == '+')
            {
                int num = stnum.top();
                stnum.pop();
                while (!stopt.empty() && stopt.top() != '(' && stopt.top() != ',')
                {
                    if (stopt.top() == '+')
                    {
                        num += stnum.top();
                        stnum.pop();
                    }
                    else if (stopt.top() == '*')
                    {
                        num *= stnum.top();
                        stnum.pop();
                    }
                    stopt.pop();
                }
                stnum.push(num);
                stopt.push('+');
            }
            else if (s[i] == ')')
            {
                int num = stnum.top();
                stnum.pop();
                while (stopt.top() != '(')
                {
                    if (stopt.top() == '+')
                    {
                        num += stnum.top();
                        stnum.pop();
                    }
                    else if (stopt.top() == '*')
                    {
                        num *= stnum.top();
                        stnum.pop();
                    }
                    else if (stopt.top() == ',')
                    {
                        int ans=0,ans1=0;
                        while(num)
                        {
                            ans += num%10;
                            num/=10;
                        }
                        while(stnum.top())
                        {
                            ans1+=stnum.top()%10;
                            stnum.top()/=10;
                        }
                        num=max(ans,ans1);
                        stnum.pop();
                    }
                    stopt.pop();
                } 
                stnum.push(num);
                stopt.pop();
            }
        }

        int num = stnum.top();
        stnum.pop();
        while (!stopt.empty())
        {
            if (stopt.top() == '+')
            {
                num += stnum.top();
                stnum.pop();
            }
            else if (stopt.top() == '*')
            {
                num *= stnum.top();
                stnum.pop();
            }
            stopt.pop();
        }

        cout << num << '\n'; 
    }

    return 0;
}