河南省第4回acm省試合C:式求値逆ポーランド式

タイトル:
https://acm.zzuli.edu.cn/zzuliacm/problem.php?id=1457
タイトル:
Description
Dr.Kongが設計したロボットカードは、加減法演算をマスターした後、最近、関数min(20,23)の値が20、add(10,98)の値が108であることを知っているなど、簡単な関数の評価を学んだ.訓練を経て、Dr.Kongが設計したロボットカードは、ネストされたより複雑な表現を計算することもできます.仮定式は、以下のように簡単に定義することができる:1.正の10進数xは式である.2.xおよびyが式である場合、関数min(x,y)も式であり、その値はx,yの最小数である.3.xとyが式である場合、関数max(x,y)も式であり、その値はx,yの最大数である.4.xとyが式である場合、関数add(x,y)も式であり、その値はx,yの和である.例えば、式max(add(1,2)、7)の値は7である.プログラムを作成して、与えられた式のセットについて、Dr.Kongが正しい答えを算出するのを助けて、カードの計算の正誤を校正してください.Input
最初の行:Nは計算する式の個数(1≦N≦10)を表し、次にN行があり、各行は1つの文字列であり、求められる値を表す式(式には余分なスペースはなく、各行は300文字を超えず、式に現れる10進数は1000を超えない.)Output
出力にはN行があり、各行に1つの式の値が対応しています.Sample Input 3 add(1,2) max(1,999) add(min(1,1000),add(100,99))
Sample Output 3 999 200
考え方:
与えられた文字列を接尾辞式に変換し,add(x,y)をx op y,min,max同理に変換する.逆ポーランド式で解きます

#include 
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const int N = 1010;

int precedence(char ch)
{
    if(ch == '>' || ch == ' || ch == '+') return 1;
    else return 0;
}
void reverse_polish(char s[], char sta[])
{
    char ts[N];
    int k = 0, top = 0;
    ts[top++] = '@';
    for(int i = 0; s[i]; i++)
    {
        if(s[i] == '(') ts[top++] = s[i];
        else if(s[i] == ')')
        {
            while(ts[top-1] != '(') sta[k++] = ts[--top];
            --top;
        }
        else if(s[i] == '>' || s[i] == ' || s[i] == '+')
        {
            while(precedence(ts[top-1]) >= precedence(s[i])) sta[k++] = ts[--top];
            ts[top++] = s[i];
        }
        else if(s[i] >= '0' && s[i] <= '9')
        {
            while(s[i] >= '0' && s[i] <= '9') sta[k++] = s[i++];
            i--;
            sta[k++] = ' ';
        }
    }
    while(ts[top-1] != '@') sta[k++] = ts[--top];
    sta[k++] = '\0';
}
int Operator(int num1, int num2, char ch)
{
    int res;
    if(ch == '+') res = num1 + num2;
    else if(ch == ') res = min(num1, num2);
    else if(ch == '>') res = max(num1, num2);
    return res;
}
void solve(char s[])
{
    int ts[N];
    int top = 0;
    for(int i = 0; s[i]; i++)
    {
        if(s[i] >= '0' && s[i] <= '9')
        {
            int num = 0;
            while(s[i] >= '0' && s[i] <= '9') num = num * 10 + s[i] - '0', i++;
            i--;
            ts[top++] = num;
        }
        else if(s[i] != ' ')
        {
            int num1 = ts[--top], num2 = ts[--top];
            ts[top++] = Operator(num2, num1, s[i]);
        }
    }
    printf("%d
", ts[0]);
}
int main()
{
    char str[N], s[N], sta[N];
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%s", str);
        for(int i = 0; str[i]; i++)
        {
            if(str[i] == ',')
                for(int j = i-1; j >= 0; j--)
                {
                    if(str[j] == 'n')
                    {
                        str[i] = ';
                        str[j] = str[j-1] = str[j-2] = '?';
                        break;
                    }
                    else if(str[j] == 'x')
                    {
                        str[i] = '>';
                        str[j] = str[j-1] = str[j-2] = '?';
                        break;
                    }
                    else if(str[j] == 'd')
                    {
                        str[i] = '+';
                        str[j] = str[j-1] = str[j-2] = '?';
                        break;
                    }
                }
        }
        memset(s, 0, sizeof s);
        int k = 0;
        for(int i = 0; str[i]; i++)
            if(str[i] != '?') s[k++] = str[i];
        //printf("%s
", s);
        reverse_polish(s, sta);
        solve(sta);
    }
    return 0;
}