题意分析

这段代码用于解析一种特定格式的伪代码，并计算其时间复杂度（用多项式表示）。输入的程序由 LOOP、OP、END 等关键字构成，输出该程序的时间复杂度（如 O(n^2 + 3n + 5)）。

解题思路

1. 使用栈模拟嵌套结构：
   • 遇到 LOOP 或 OP 时，将其对应的多项式（如 n 或 5）压栈。
   • 遇到 END 时，弹出栈顶元素，计算当前块的时间复杂度：
     • 如果是 OP，累加操作次数。
     • 如果是 LOOP，将内部操作次数乘以循环次数（n 或常数）。
2. 多项式表示：
   • 用数组 num[11] 存储多项式系数，num[i] 表示 n^i 的系数。
   • 重载 + 和 * 运算符，实现多项式加法和乘法。
3. 输出优化：
   • 从高次到低次输出多项式，避免 +0 或 1*n 等冗余形式。

完整代码

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <sstream>
#include <algorithm>
#include <stack>  // Added missing header
using namespace std;

struct Polynomial {
    map<int, int> coeffs;  // exponent -> coefficient
    
    void add_term(int exp, int coeff) {
        coeffs[exp] += coeff;
    }
    
    Polynomial operator*(const Polynomial& other) const {
        Polynomial result;
        for (const auto& term1 : coeffs) {
            for (const auto& term2 : other.coeffs) {
                result.add_term(term1.first + term2.first, term1.second * term2.second);
            }
        }
        return result;
    }
    
    Polynomial operator+(const Polynomial& other) const {
        Polynomial result = *this;
        for (const auto& term : other.coeffs) {
            result.add_term(term.first, term.second);
        }
        return result;
    }
    
    string to_string() const {
        if (coeffs.empty()) return "0";
        
        vector<pair<int, int>> terms(coeffs.begin(), coeffs.end());
        sort(terms.rbegin(), terms.rend());  // Sort by exponent descending
        
        stringstream ss;
        bool first = true;
        
        for (const auto& term : terms) {
            if (term.second == 0) continue;
            
            if (!first) {
                ss << (term.second > 0 ? "+" : "-");
            } else if (term.second < 0) {
                ss << "-";
            }
            
            int abs_coeff = abs(term.second);
            if (abs_coeff != 1 || term.first == 0) {
                ss << abs_coeff;
            }
            
            if (term.first > 0) {
                ss << "*n";
                if (term.first > 1) {
                    ss << "^" << term.first;
                }
            }
            
            first = false;
        }
        
        return ss.str();
    }
};

Polynomial parse_program(istream& in) {
    string token;
    Polynomial result;
    stack<Polynomial> multipliers;
    multipliers.push(Polynomial());  // Start with multiplier 1
    multipliers.top().add_term(0, 1);
    
    while (in >> token) {
        if (token == "BEGIN") {
            continue;
        } else if (token == "END") {
            if (multipliers.size() > 1) {
                multipliers.pop();
            }
        } else if (token == "LOOP") {
            in >> token;
            Polynomial loop_mult;
            if (token == "n") {
                loop_mult.add_term(1, 1);
            } else {
                loop_mult.add_term(0, stoi(token));
            }
            multipliers.push(multipliers.top() * loop_mult);
        } else if (token == "OP") {
            in >> token;
            int op_time = stoi(token);
            Polynomial op_poly;
            op_poly.add_term(0, op_time);
            result = result + (multipliers.top() * op_poly);
        }
    }
    
    return result;
}

int main() {
    int k;
    cin >> k;
    cin.ignore();  // Ignore newline
    
    for (int i = 1; i <= k; ++i) {
        string line;
        stringstream program_stream;
        
        // Read entire program
        while (getline(cin, line)) {
            program_stream << line << " ";
            if (line.find("END") != string::npos && 
                count(line.begin(), line.end(), 'E') == 1) {
                break;
            }
        }
        
        Polynomial runtime = parse_program(program_stream);
        
        cout << "Program #" << i << endl;
        cout << "Runtime = " << runtime.to_string() << endl << endl;
    }
    
    return 0;
}