给出了他自己算出的时间复杂度，可他的编程老师实在不想一个一个检查小明的程序，于是你的机会来啦！下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。 A++ 语言的循环结构如下：
F i x y
循环体
E
然后判断 i 和 y 的大小关系，若 i 小于等于 y 则进入循环，否则不进入。每次循环结束后i都会被修改成 i +1，一旦 i 大于 y 终止循环。 x 和 y 可以是正整数（x 和 y 的大小关系不定）或变量 n。n 是一个表示数据规模的变量，在时间复杂度计算中需保留该变量而不能将其视为常数，该数远大于 100。 E表示循环体结束。循环体结束时，这个循环体新建的变量也被销毁。
的概念。
输入描述:
输入文件第一行一个正整数 t，表示有 t(t≤ 10) 个程序需要计算时间复杂度。
每个程序我们只需抽取其中 F i x y和E即可计算时间复杂度。注意：循环结构允许嵌套。
接下来每个程序的第一行包含一个正整数 L 和一个字符串，L 代表程序行数，字符串表示这个程序的复杂度，O(1)表示常数复杂度，O(n^w) 表示复杂度为 n *w，其中 w 是一个小于 100 的正整数（输入中不包含引号），输入保证复杂度只有 O(1) 和 O(n^w) 两种类型。
接下来 L 行代表程序中循环结构中的 F i x y 或者 E。 程序行若以 F 开头，表示进入一个循环，之后有空格分离的三个字符（串）i x y，其中 i 是一个小写字母（保证不为 n ），表示新建的变量名，x 和 y 可能是正整数或 n ，已知若为正整数则一定小于 100。 程序行若以 E开头，则表示循环体结束。</pre>
输出描述:
输出文件共 t 行，对应输入的 t 个程序，每行输出Yes或No或者ERR，若程序实际复杂度与输入给出的复杂度一致则输出 Yes，不一致则输出No，若程序有语法错误（其中语法错误只有: ①F 和 E 不匹配 ②新建的变量与已经存在但未被销毁的变量重复两种情况），则输出ERR。
注意：即使在程序不会执行的循环体中出现了语法错误也会编译错误，要输出ERR。</pre>
示例1
输入
8
//------
2 O(1)
F i 1 1
E
//------
2 O(n^1)
F x 1 n
E
//------
1 O(1)
F x 1 n
//------
4 O(n^2)
F x 5 n
F y 10 n
E
E
//------
4 O(n^2)
F x 9 n
E
F y 2 n
E
//------
4 O(n^1)
F x 9 n
F y n 4
E
E
//------
4 O(1)
F y n 4
F x 9 n
E
E
//------
4 O(n^2)
F x 1 n
F x 1 10
E
E
//------
输出
Yes
Yes
ERR
Yes
No
Yes
Yes
ERR</pre>
说明
第一个程序 i 从1 到 1 是常数复杂度。
第二个程序 x 从 1 到 n 是 n 的一次方的复杂度。
第三个程序有一个F开启循环却没有E结束，语法错误。
第四个程序二重循环，n 的平方的复杂度。
第五个程序两个一重循环，n 的一次方的复杂度。
第六个程序第一重循环正常，但第二重循环开始即终止（因为 n 远大于 100，100 大于 4）。
第七个程序第一重循环无法进入，故为常数复杂度。
第八个程序第二重循环中的变量 x 与第一重循环中的变量重复，出现语法错误②，输出ERR。</pre>
备注:
对于 30% 的数据：不存在语法错误，数据保证小明给出的每个程序的前 L/2 行一定为以
F开头的语句，第 L/2+1 行至第 L 行一定为以E开头的语句，L≤ 10，若 x,y 均为整数，x 一定小于 y，且只有 y 有可能为n。
对于 50% 的数据：不存在语法错误，L≤ 100，且若 x,y 均为整数，x 一定小于 y，且只有 y 有可能为n。
对于 70% 的数据：不存在语法错误，L≤ 100。
对于 100% 的数据：t≤ 10,L≤ 100。若 x,y 均为整数，x 一定小于 y，且只有 y 有可能为n。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<sstream>//
#include<algorithm>
#include<cmath>
#define inf 0x3f3f3f3f
#define maxn 10000
typedef long long ll;
using namespace std;
typedef pair<char,int>PCI;
const int N = 110;
int tt;
PCI stk[N];//存储当前嵌套的所有循环
//first每一层变量名
//second存储当前这层总共的计算量，如果为-1则当前这一层无法到达
int get_number(string str)//字符串转化为整数
{
int res = 0;
for(int i=0;i<str.size();i++) res = res*10 + str[i]-'0';
return res;
}
int get_time(string str)//提取 str 中 n的次数
{
if(str == "O(1)") return 0;
int t=str.find('^');//
string num = str.substr(t + 1);
num.pop_back();
return get_number(num);
}
bool has(char c)//判断当前栈中是否已经存在变量c
{
for(int i=1;i <= tt; i++)
if(stk[i].first == c)
return true;
return false;
}
int get_cmp(string x,string y)//判断for(i,x,y)的循环次数是 n 的几次
{
if(x=="n")
{
if(y == "n")
return 0;
return -1;
}
if(y == "n") return 1;
int a = get_number(x),b = get_number(y);
if(a <= b) return 0;
return -1;
}
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
string str;
cin>>n>>str;
int tm = get_time(str);//
int max_cmp = 0;
bool error = false;
tt=0;
string line;
getline (cin,line);///读掉行末换行
///相当于getchar();
for(int i=0;i<n;i++)
{
getline(cin,line);///
if(!error)
{
if(line == "E")
{
if(tt) tt--;
else error = true;
}
else
{
stringstream sin(line);///
string F,i,x,y;///
sin >> F >> i >> x >> y;
if(has(i[0])) error = true;
else
{
int cmp = get_cmp(x,y);//
if(!tt)
stk[++tt] = make_pair(i[0], cmp);
else
{
int computation = -1;//当前这一层无法到达
if(stk[tt].second >= 0 && cmp >= 0)
computation = stk[tt].second + cmp;
stk[++tt] = make_pair(i[0],computation);//
}
max_cmp = max(max_cmp, stk[tt].second );
}
}
}
}
if(tt) error = true;
if(error) printf("ERR\n");
else if(tm == max_cmp) printf("Yes\n");
else printf("No\n");
}
return 0;
}
网友评论