問題#
関数 f が与えられ、f は最初に x の初期値を受け取ります。f にはいくつかの命令があり、命令は三種類に分かれます：
for n - ループ
end - 各ループの終了符号。各ペアの for n と end の間のコードは n 回実行されます。すべての for n 命令が一つの end 命令とペアになることを保証します。
add - x を 1 増加させます。
すべての操作が完了した後、x が戻り値として返されます。
途中の計算で、x が $2^{32}?1$ を超える可能性がある場合、その時は OVERFLOW!!! と出力してください。
さて、f (0) の値を出力してください。
考え方#
表面的にはこの問題はスタックを使う必要がありますが、私は配列を使うことにしました。
f[i] は現在第 i 層のループにいることを示し、ループ本体内で実行される回数を表します。
f[i] = f[i - 1] * n
オーバーフローが発生するポイントは、ループの深さが過剰な時と加算が過剰な時ですが、非常に深いループの中には加算文がない場合もあるので、ここでフラグを立てて判定します。
自分がやりすぎているのではないかと感じています。。。。。。
コード#
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstdlib>
using namespace std;
const long long over = ((long long)1 << 32) - 1;
int n, h;
long long x;
long long cnt = 0;
vector<long long> f;
int main (void) {
f.push_back(1);
scanf("%d", &n);
char t[4];
bool flag = 0;
for (int i = 1; i <= n; ++i) {
scanf("%s", t);
if (t[0] == 'f') {
++cnt;
f.resize(cnt + 1);
scanf("%d", &h);
if (over / h < f[cnt - 1]) {
flag = 1;
}
f[cnt] = f[cnt - 1] * h;
}
else if (t[0] == 'a') {
if (flag) {
printf("OVERFLOW!!!\n");
exit(0);
}
else {
int tmp = x;
x += f[cnt];
if (x > over || x < tmp) {
printf("OVERFLOW!!!\n");
exit(0);
}
}
}
else {
flag = 0;
--cnt;
}
}
printf("%I64d\n", x);
return 0;
}