73分求条
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <unordered_set>
#include <sstream>
using namespace std;
struct Loop {
char var;
string x, y;
bool is_active;
};
int parseComplexity(const string& s) {
if (s == "O(1)") return 0;
size_t pos = s.find('^');
if (pos != string::npos) {
return stoi(s.substr(pos + 1, s.size() - pos - 2));
}
return 1; // O(n)
}
int calculateLoopComplexity(const string& x, const string& y) {
if (x == "n" && y == "n") return 0;
if (x == "n") return 0;
if (y == "n") return 1;
int xi = stoi(x), yi = stoi(y);
return (xi <= yi) ? 0 : -1;
}
void processProgram(int L, const string& expected, vector<string>& lines) {
stack<Loop> loopStack;
unordered_set<char> activeVars;
int max_power = 0;
int current_power = 0;
bool has_error = false;
for (int i = 0; i < L; ++i) {
string line = lines[i];
if (line[0] == 'F') {
istringstream iss(line.substr(1));
char var;
string x, y;
iss >> var >> x >> y;
if (activeVars.count(var)) {
has_error = true;
}
activeVars.insert(var);
int loop_complexity = calculateLoopComplexity(x, y);
Loop newLoop{var, x, y, loop_complexity >= 0};
loopStack.push(newLoop);
if (newLoop.is_active) {
current_power += loop_complexity;
max_power = max(max_power, current_power);
}
} else if (line[0] == 'E') {
if (loopStack.empty()) {
has_error = true;
continue;
}
Loop top = loopStack.top();
loopStack.pop();
activeVars.erase(top.var);
if (top.is_active) {
current_power -= calculateLoopComplexity(top.x, top.y);
}
}
}
if (!loopStack.empty()) {
has_error = true;
}
if (has_error) {
cout << "ERR" << endl;
return;
}
int expected_power = parseComplexity(expected);
cout << ((max_power == expected_power) ? "Yes" : "No") << endl;
}
int main() {
int t;
cin >> t;
while (t--) {
int L;
string complexity;
cin >> L >> complexity;
vector<string> lines(L);
cin.ignore();
for (int i = 0; i < L; ++i) {
getline(cin, lines[i]);
}
processProgram(L, complexity, lines);
}
return 0;
}