POJ1472 Instant Complexity 模拟

相当于表达式计算一般，用递归进行处理，将BEGIN视作是一个LOOP，每次进入LOOP则进行多条语句处理，知道遇到END位置，结束这个LOOP。

代码如下：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <queue>
#include <vector>
#include <stack>
#include <list>
#include <set>
using namespace std;

struct EXP {
    int a[11];
    EXP () {
        memset(a, 0, sizeof (a));
    }
    EXP mul(int x) {
        EXP ret;
        if (x == -1) {
            for (int i = 1; i <= 10; ++i) {
                ret.a[i] = a[i-1];    
            }
        } else {
            for (int i = 0; i <= 10; ++i) {
                ret.a[i] = x * a[i];    
            }    
        }
        return ret;
    }
    EXP add(int x) {
        EXP ret = *this;
        ret.a[0] += x;
        return ret;
    }
    EXP add(EXP x) {
        EXP ret = *this;
        for (int i = 0; i <= 10; ++i) {
            ret.a[i] += x.a[i];    
        }
        return ret;
    }
};

EXP cal() {
    EXP ret;
    char op[20], num[20]; 
    while (1) {
        scanf("%s", op);
        if (!strcmp(op, "LOOP")) {
            scanf("%s", num);
            if (num[0] == 'n') {
                ret = ret.add(cal().mul(-1));
            } else {
                ret = ret.add(cal().mul(atoi(num)));
            }
        } else if (!strcmp(op, "OP")) {
            scanf("%s", num);
            ret = ret.add(atoi(num));
        } else return ret;
    }
}

int main()
{
    int T, ca = 0;
    char coat[20];
    bool first, zero;
    EXP ret;
    scanf("%d", &T);
    while (T--) {
        first = zero = true;
        scanf("%s", coat);
        ret = cal();
        printf("Program #%d\n", ++ca);
        printf("Runtime = ");
        for (int i = 0; i <= 10; ++i) {
            if (ret.a[i]) zero = false;
        }
        if (zero) {
            puts("0\n");
            continue;    
        }
        for (int i = 10; i >= 0; --i) {
            if (ret.a[i]) {
                if (ret.a[i] == 1) {
                    if (first) {
                        if (i) {
                            if (i == 1) {
                                printf("n");
                            } else {
                                printf("n^%d", i);
                            }
                        } else { 
                            printf("1");
                        }
                        first = false;
                    } else {
                        if (i) {
                            if (i == 1) {
                                printf("+n");
                            } else {
                                printf("+n^%d", i);
                            }
                        } else { 
                            printf("+1");
                        }
                    }
                } else { // ret.a[i] != 1
                    if (first) {
                        if (i) {
                            if (i == 1) {
                                printf("%d*n", ret.a[i]);
                            } else {
                                printf("%d*n^%d", ret.a[i], i);
                            }
                        } else {
                            printf("%d", ret.a[i]);
                        }
                        first = false;
                    } else {
                        if (i) {
                            if (i == 1) {
                                printf("+%d*n", ret.a[i]);
                            } else {
                                printf("+%d*n^%d", ret.a[i], i);
                            }
                        } else {
                            printf("+%d", ret.a[i]);
                        }
                    }
                }
            }    
        }
        puts("\n");
    }
    return 0;
}